https://hal.inria.fr/hal-02387299Wolf, PetraPetraWolfTrier UniversityOn the Decidability of Finding a Positive ILP-Instance in a Regular Set of ILP-InstancesHAL CCSD2019Deterministic finite automatonRegular languagesRegular intersection emptiness problemDecidabilityInteger linear programming[INFO] Computer Science [cs]Ifip, HalMichal HospodárGalina JiráskováStavros Konstantinidis2019-11-29 16:36:102022-11-22 10:34:072019-11-29 17:01:49enConference papershttps://hal.inria.fr/hal-02387299/document10.1007/978-3-030-23247-4_21application/pdf1The regular intersection emptiness problem for a decision problem P ($$ int_{\mathrm {Reg}} $$(P)) is to decide whether a potentially infinite regular set of encoded P-instances contains a positive one. Since $$ int_{\mathrm {Reg}} $$(P) is decidable for some NP-complete problems and undecidable for others, its investigation provides insights in the nature of NP-complete problems. Moreover, the decidability of the $$ int_{\mathrm {Reg}} $$-problem is usually achieved by exploiting the regularity of the set of instances; thus, it also establishes a connection to formal language and automata theory. We consider the $$ int_{\mathrm {Reg}} $$-problem for the well-known NP-complete problem Integer Linear Programming (ILP). It is shown that any DFA that describes a set of ILP-instances (in a natural encoding) can be reduced to a finite core of instances that contains a positive one if and only if the original set of instances did. This result yields the decidability of $$ int_{\mathrm {Reg}} $$(ILP).