A Bit-Scaling Algorithm for Integer Feasibility in UTVPI Constraints

DOI10.1007/978-3-319-44543-4_25zbMath1478.68198OpenAlexW2529628685MaRDI QIDQ2819515

K. Subramani and Vahan Mkrtchyan, Piotr J. Wojciechowski

Publication date: 29 September 2016

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-44543-4_25

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Integer programming (90C10) Nonnumerical algorithms (68W05) Combinatorics in computer science (68R05)

Related Items

Reachability in choice networks ⋮ Optimal length cutting plane refutations of integer programs ⋮ On integer closure in a system of unit two variable per inequality constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A combinatorial certifying algorithm for linear feasibility in UTVPI constraints
• Weakly-relational shapes for numeric abstractions: Improved algorithms and proofs of correctness
• The octagon abstract domain
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• 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
• Scaling Algorithms for the Shortest Paths Problem
• Frontiers of Combining Systems
• Logic for Programming, Artificial Intelligence, and Reasoning