
On the Power and Limitations of Branch and Cut
The Stabbing Planes proof system was introduced to model the reasoning c...
read it

Automating Cutting Planes is NPHard
We show that Cutting Planes (CP) proofs are hard to find: Given an unsat...
read it

Complexity of cutting planes and branchandbound in mixedinteger optimization
We investigate the theoretical complexity of branchandbound (BB) and c...
read it

Stabbing Planes
We introduce and develop a new semialgebraic proof system, called Stabb...
read it

QRAT Polynomially Simulates Merge Resolution
Merge Resolution (MRes [Beyersdorff et al. J. Autom. Reason.'2021] ) is ...
read it

Indistinguishable binomial decision tree of 3SAT: Proof of class P is a proper subset of class NP
This paper solves a long standing open problem of whether NPcomplete pr...
read it

Separation of bounded arithmetic using a consistency statement
This paper proves Buss's hierarchy of bounded arithmetics S^1_2 ⊆ S^2_2 ...
read it
On the Complexity of Branching Proofs
We consider the task of proving integer infeasibility of a bounded convex K in ℝ^n using a general branching proof system. In a general branching proof, one constructs a branching tree by adding an integer disjunction 𝐚𝐱≤ b or 𝐚𝐱≥ b+1, 𝐚∈ℤ^n, b ∈ℤ, at each node, such that the leaves of the tree correspond to empty sets (i.e., K together with the inequalities picked up from the root to leaf is empty). Recently, Beame et al (ITCS 2018), asked whether the bit size of the coefficients in a branching proof, which they named stabbing planes (SP) refutations, for the case of polytopes derived from SAT formulas, can be assumed to be polynomial in n. We resolve this question by showing that any branching proof can be recompiled so that the integer disjunctions have coefficients of size at most (n R)^O(n^2), where R ∈ℕ such that K ∈ R 𝔹_1^n, while increasing the number of nodes in the branching tree by at most a factor O(n). As our second contribution, we show that Tseitin formulas, an important class of infeasible SAT instances, have quasipolynomial sized cutting plane (CP) refutations, disproving the conjecture that Tseitin formulas are (exponentially) hard for CP. As our final contribution, we give a simple family of polytopes in [0,1]^n requiring branching proofs of length 2^n/n.
READ FULL TEXT
Comments
There are no comments yet.