15
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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.

Further reading:

  • "On the augmented Lagrangian dual for integer programming", by Natashia Boland, Andrew C. Eberhard. Published in Math. Program. 2015, DOI:10.1007/s10107-014-0763-3

    Page 1:
    "... for nonlinear, nonsmooth optimisation there have been a number of strong duality schemes proposed in the last 10 years. The augmented Lagrangian dual has been of particular interest in this area. In convex optimisation, algorithms to solve the augmented Lagrangian dual were found to be more robust, and converged under less stringent assumptions, than their standard Lagrangian dual predecessors [29]. Early application of the augmented Lagrangian in IP [30] was aimed at producing better dual bounds at the root node of the branch-and-bound tree. ... One of the challenges for applying the augmented dual in IP computational methods is that the augmented Lagrangian term destroys the natural separability properties of the Lagrangian dual. However this can be overcome by the use of an approach known as the alternating direction method of multipliers [4, 9], which is enjoying recent attention in the literature. Thus the augmented Lagrangian dual for IP warrants further attention. In this paper, we contribute to the theory of the augmented Lagrangian dual for IP so as to provide insight into how it obtains better bounds than the standard Lagrangian dual.".

  • Wikipedia - Augmented Lagrangian method (Software)

  • "Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers", (Jul 26 2011), by Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato and Jonathan Eckstein

  • "Douglas-Rachford splitting and ADMM for nonconvex optimization: tight convergence results", (Nov 9 2018), by Andreas Themelis, Panagiotis Patrinos

  • COIN|OR DIP - Discrete Integer Programming software

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.