# Family of hard instances for Gomory's cutting plane algorithm

Is there a variant of integer programs for which Gomory's cutting plane algorithm demonstrably takes a superpolynomial number of iterations?

Is there a variant of integer programs for which Gomory's cutting plane algorithm demonstrably takes a superpolynomial number of iterations?

Yes

Definitions:

"Superpolynomial time
An algorithm is said to take superpolynomial time if $$T(n)$$ is not bounded above by any polynomial. Using little omega notation, it is $$\omega (n^c)$$ time for all constants $$c$$, where $$n$$ is the input parameter, typically the number of bits in the input. For example, an algorithm that runs for $$2^n$$ steps on an input of size $$n$$ requires superpolynomial time (more specifically, exponential time).".

"Exponential time
An algorithm is said to be exponential time, if $$T(n)$$ is upper bounded by $$2^{poly(n)}$$, where $$poly(n)$$ is some polynomial in $$n$$. More formally, an algorithm is exponential time if $$T(n)$$ is bounded by $$O(2^{{n}^{k}})$$ for some constant $$k$$. Problems which admit exponential time algorithms on a deterministic Turing machine form the complexity class known as EXP." and "The exponential time hypothesis implies $$P \ne NP$$.".

In "An Exponential Lower Bound on the Length of Some Classes of Branch-and-Cut Proofs" (May 21 2002), by Sanjeeb Dash (IBM), preliminary version in: IBM Research Report RC22575 (.PDF), Sept 2002:

"Abstract
Branch-and-cut methods are among the most important techniques for solving integer programming problems. They can also be used to prove that all solutions of an integer program satisfy a given linear inequality. We examine the complexity of branch-and-cut proofs in the context of 0-1 integer programs. We prove an exponential lower bound on the length of branch-and-cut proofs which use 0-1 branching and lift-and-project cuts (called simple disjunctive cuts by some authors), Gomory-Chvátal cuts, and cuts arising from the $$N_0$$ matrix-cut operator of Lovász and Schrijver. A consequence of the lower-bound result in this paper is that branch-and-cut methods of the type described above have exponential running time in the worst case.".

...

On page 10:

"4 Interpolation and Cutting-Plane Proofs
The problem of determining if a system of linear inequalities $$Ax \le b$$ has a 0-1 solution is NP-complete. Therefore, every algorithm which finds a 0-1 solution, or provides a certificate that no 0-1 solution exists, is expected to have super-polynomial time complexity. In fact, many believe that polynomial-size certificates of infeasibility (in the encoding size of $$A, b$$) do not always exist; this is the same as saying that $$NP \ne coNP$$. This question is far from being solved. However there has been progress in studying various restricted classes of certificates – formally, proofs in some proof system – and in showing exponential worst case complexity (size) for some classes. Achieving this goal for all proof systems would show that $$NP = coNP$$, and therefore that $$P \ne NP$$. (Note that exponential length branch-and-cut proofs have exponential size; we will focus on the lengths of such proofs).

...

We will be interested only in infeasible 0-1 integer programs; we will use the phrase “integer program” to mean a problem without an objective function where we want to find 0-1 solutions of linear inequality systems.".

More recently, "Theoretical challenges towards cutting-plane selection" (May 7 2018), by Santanu S. Dey and Marco Molinaro, on page 4:

"Finite Cutting-plane Algorithms. One natural question is: can we solve an MILP in finite time using solely cuts from a given family without branching or any other operation? Gomory gave the first finitely convergent cutting-plane algorithm for pure integer programs [131], using CG cuts. There have been very few results since then on finite cutting-plane algorithms, see [181] and references therein. See [68] for a polynomial-time cutting-plane algorithm for matching, [69] for a finite cutting-plane algorithm for bounded MILPs, and [104] for a finite cutting-plane algorithm for general MILPs. There are also lower bounds on the length of cutting-plane proofs (length of sequence of cuts needed to prove optimality or infeasibility) [73]. For example, generalizing previous work of Pudlák [189], Dash [98] presents exponential lower bounds for proofs via branch-and-cut procedures that use L&P and CG cuts.".

For a practical example read: "Applied Integer Programming - Modeling and Solution", by Der-san Chen, Robert G. Batson, and Yu Dang

Page: 120

"The difficulty of cutting stock problem is that the number of possible cutting patterns n is usually too huge to enumerate them all. For example, with a roll of width 20 in. and demand for 40 different widths ranging from 20-80 in., the number of cutting patterns can exceed 100 million (Gilmore and Gomory, 1961). The number of cutting patterns is multiplied when there are multiple standard widths to be cut from. Therefore, the IP model of a cutting stock problem is rarely solved exactly. In practice, its LP relaxation is solved by using Dantzig-Wolfe decomposition principle through a column generation technique.".

But generally one would prefer a Lagrangian over Dantzig-Wolfe for column generation.