On the Path-Width of Integer Linear Programming
Copyright policy )On the Path-Width of Integer Linear Programming
We consider the feasibility problem of integer linear programming (ILP). We show that solutions of any ILP instance can be naturally represented by an FO-definable class of graphs. For each solution there may be many graphs representing it. However, one of these graphs is of path-width at most 2n, where n is the number of variables in the instance. Since FO is decidable on graphs of bounded path- width, we obtain an alternative decidability result for ILP. The technique we use underlines a common principle to prove decidability which has previously been employed for automata with auxiliary storage. We also show how this new result links to automata theory and program verification.
In Proceedings GandALF 2014, arXiv:1408.5560
- National Institute for Nuclear Physics Italy
- University of Southampton United Kingdom
- School of Electronics and Computer Science, University of Southampton United Kingdom
- University of Paris France
- Gran Sasso Science Institute Italy
FOS: Computer and information sciences, Computer Science - Logic in Computer Science, automata, Formal Languages and Automata Theory (cs.FL), Computer Science - Formal Languages and Automata Theory, Formal languages and automata, Computational Complexity (cs.CC), integer linear programming, first-order logic on graphs, Decidability of theories and sets of sentences, QA1-939, Automata; Bounded path-width; First-order logic on graphs; Integer linear programming, Integer programming, QA75.5-76.95, bounded path-width, 004, Logic in Computer Science (cs.LO), Computer Science - Computational Complexity, Language theory and automata; models of concurrent systems; multistack pushdown automata; visibly pushdown automata, Electronic computers. Computer science, Graph theory (including graph drawing) in computer science, Mathematics
FOS: Computer and information sciences, Computer Science - Logic in Computer Science, automata, Formal Languages and Automata Theory (cs.FL), Computer Science - Formal Languages and Automata Theory, Formal languages and automata, Computational Complexity (cs.CC), integer linear programming, first-order logic on graphs, Decidability of theories and sets of sentences, QA1-939, Automata; Bounded path-width; First-order logic on graphs; Integer linear programming, Integer programming, QA75.5-76.95, bounded path-width, 004, Logic in Computer Science (cs.LO), Computer Science - Computational Complexity, Language theory and automata; models of concurrent systems; multistack pushdown automata; visibly pushdown automata, Electronic computers. Computer science, Graph theory (including graph drawing) in computer science, Mathematics
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).4 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!