A certifying algorithm for lattice point feasibility in a system of UTVPI constraints

DOI10.1007/s10878-017-0176-3zbMath1394.90499OpenAlexW2759459399MaRDI QIDQ1702822

Piotr J. Wojciechowski, K. Subramani and Vahan Mkrtchyan

Publication date: 1 March 2018

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-017-0176-3

zbMATH Keywords

UTVPI constraintsdifference constraintscertificatesrounding scheme

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items

On the parallel complexity of constrained read-once refutations in UTVPI constraint systems ⋮ Integer feasibility and refutations in UTVPI constraints using bit-scaling ⋮ Polynomial time algorithms for optimal length tree-like refutations of linear infeasibility in UTVPI constraints ⋮ On integer closure in a system of unit two variable per inequality constraints

Uses Software

• LEDA

Cites Work

• Unnamed Item
• Unnamed Item
• A combinatorial certifying algorithm for linear feasibility in UTVPI constraints
• The octagon abstract domain
• The intractability of resolution
• Shortest paths algorithms: Theory and experimental evaluation
• Fourier-Motzkin elimination and its dual
• Incremental Satisfiability and Implication for UTVPI Constraints
• 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
• An Improved Tight Closure Algorithm for Integer Octagonal Constraints
• Frontiers of Combining Systems
• Logic for Programming, Artificial Intelligence, and Reasoning
• Computer Aided Verification