On integer closure in a system of unit two variable per inequality constraints

DOI10.1007/s10472-020-09703-5zbMath1466.90053OpenAlexW3088895994MaRDI QIDQ2023870

Yanyan Li

Publication date: 3 May 2021

Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10472-020-09703-5

zbMATH Keywords

relaxationshortest pathsDijkstra's algorithmUTVPI constraintsinteger closure

Mathematics Subject Classification ID

Integer programming (90C10) Deterministic network models in operations research (90B10)

Related Items (1)

Integer feasibility and refutations in UTVPI constraints using bit-scaling

Cites Work

• Unnamed Item
• Unnamed Item
• A combinatorial certifying algorithm for linear feasibility in UTVPI constraints
• Optimal length tree-like refutations of linear feasibility in UTVPI constraints
• Weakly-relational shapes for numeric abstractions: Improved algorithms and proofs of correctness
• The octagon abstract domain
• A certifying algorithm for lattice point feasibility in a system of UTVPI constraints
• A polynomial time algorithm for read-once certification of linear infeasibility in UTVPI constraints
• Fourier-Motzkin elimination and its dual
• An Optimal Algorithm for Computing the Integer Closure of UTVPI Constraints
• A Bit-Scaling Algorithm for Integer Feasibility in UTVPI Constraints
• Incremental Satisfiability and Implication for UTVPI Constraints
• Two Variables per Linear Inequality as an Abstract Domain
• Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality
• Parametric dispatching of hard real-time tasks
• On deciding the non‐emptiness of 2SAT polytopes with respect to First Order Queries
• Frontiers of Combining Systems
• Logic for Programming, Artificial Intelligence, and Reasoning

This page was built for publication: On integer closure in a system of unit two variable per inequality constraints