12
$\begingroup$

Consider the following simple integer program

$$\begin{array}{ll} \text{maximize} & 3 x_1 - x_2\\ \text{subject to} & 3x_1 - x_2 \leqslant 3 \\ & -5x_1 - 4x_2 \leqslant -10 \\ & 2x_1 + x_2 \leqslant 5 \\ & x_1, x_2 \geqslant 0 \\ & x_1, x_2 \in \Bbb{Z}\end{array}$$

When trying to solve this IP with the simplex algorithm and Gomory cutting planes, I did 3 iterations and gave up. However, by enumerating possible solutions (that's only 5 points), I easily found the solution.

I would like to know if there's a general solution to the slow convergence of Gomory cutting.

$\endgroup$
  • 5
    $\begingroup$ I wrote a couple of papers with Arrigo Zanette and #maestro (Egon Balas) about this topic: essentially, you must use lexicographic simplex if you want to have a convergent method (the point being that only the combination of Lex-simplex and Gomory mimics enumeration). Of course, for most cases using a direct enumeration scheme such as Branch and Bound/Cut is much more effective. $\endgroup$ – Matteo Fischetti Jun 7 '19 at 17:10
13
$\begingroup$

The slow convergence of the Gomory cuts was well-known and source of frustration for the field up until the 90s. It seemed that Gomory cuts would be a cute idea, but not one that would lead to any real computational success.

Then work by Balas, Ceria, Cornuejols, and Natraj rekindled interest in the area, and Gomory cuts became very important in real computation. Cornuejols wrote up a nice reminiscence of this. Lots of papers followed (I particularly like Letchford and Lodi, available here, but there are others).

Let me give one result for better Gomory cuts. This result was in Gomory's original paper:

If you have a row of the simplex tableau of the form $$x_j + \sum_{i\in Q} \alpha_i x_i = x_j^*$$ where $Q$ is the set of non-basic variables

then the Gomory cut is $$\sum_{i\in Q} f(\alpha_i) x_i \ge f(x_j^*)$$

where $f(x)$ is the fractional part of $x$. So an example of a Gomory cut might be

$$0.2 x_1 + 0.3x_2 \ge 0.1$$

You can multiple this constraint by any integer $t$ and use fractional parts to get a different cut:

$$\sum_{i\in Q} f(t\alpha_i) x_i \ge f(tx_j^*)$$

Multiplying the above example by 9 gives

$$0.8x_1+0.7x_2 \ge 0.9$$

which is stronger, meaning some values that satisfy the original Gomory cut don't satisfy this constraint ($x_1= .5, x_2=0$ for instance).

None of this is particular useful for solving instances by hand. Anything small enough to do by hand would generally be done better by, for instance, enumerating points, as given in the original question.

Added I suppose in the example being solved, if the right-hand-side of any constraint generated is less than 0.5, it would be worthwhile to see if strengthening it via the above speeds up convergence.

$\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.