Optimal length cutting plane refutations of integer programs

DOI10.1016/J.DISOPT.2023.100806MaRDI QIDQ6957165zbMATH OpenFDO

Authors K. Subramani, Piotr Wojciechowski

Publication date 16 July 2025

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DISOPT.2023.100806

zbMATH Keywords

cutting planesinference rulesinteger programsoptimal lengthread-once refutation

Mathematics Subject Classification ID

Complexity of proofs (03F20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Abstract computational complexity for mathematical programming problems (90C60)

Cites work

• A Bit-Scaling Algorithm for Integer Feasibility in UTVPI Constraints
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• A note on monotone real circuits
• Algorithms and Computation
• Automating cutting planes is NP-hard
• Automating resolution is NP-hard
• Cones of Matrices and Set-Functions and 0–1 Optimization
• CPBPV: a constraint-programming framework for bounded program verification
• Cutting-plane proofs in polynomial space
• Edmonds polytopes and a hierarchy of combinatorial problems. (Reprint)
• scientific article; zbMATH DE number 6829289 (Why is no real title available?)
• scientific article; zbMATH DE number 751135 (Why is no real title available?)
• scientific article; zbMATH DE number 1860652 (Why is no real title available?)
• In between resolution and cutting planes: a study of proof systems for pseudo-Boolean SAT solving
• Lower bounds for cutting planes proofs with small coefficients
• Lower bounds for resolution and cutting plane proofs and monotone computations
• On finding short resolution refutations and small unsatisfiable subsets
• On Interpolation and Automatization for Frege Systems
• On the approximability of the maximum common subgraph problem
• On the automatizability of resolution and related propositional proof systems
• On the complexity of approximating the independent set problem
• On the complexity of cutting-plane proofs
• Optimal length cutting plane refutations of integer programs
• Optimal length resolution refutations of difference constraint systems
• Outline of an algorithm for integer solutions to linear programs
• Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes
• Resolution Is Not Automatizable Unless W[P] Is Tractable
• Restricted cutting plane proofs in Horn constraint systems
• The complexity of optimization problems
• Tools and Algorithms for the Construction and Analysis of Systems
• Verifying integer programming results

This page was built for publication: Optimal length cutting plane refutations of integer programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6957165)