Cutting-Plane method

The second very prominent solution strategy for mixed-integer problems is the so called cutting-plane approach. It shares the idea of solving a series of continuously relaxed problems with the previously discussed branch-and-bound approach. However, instead of generating a tree of sub-problems which partition the feasible region, the cutting-plane approach refines a single so called master problem until an integral feasible solution is found. The solution process starts with the relaxation of the original problem, i.e.

Q0 ←relaxed(P), and iteratively adds inequality constraints, Qi+1 ←Qi∧Cutnew ≤0, until an integral feasible solution is found as shown below:

Algorithm: Cutting-Plane approach Input: P ∈M ILP

Output: optimal feasible solution (x,y)∈Rⁿ×Z^m or INFEASIBLE

01: i←0 // iteration counter

02: Q₀ ←relaxed(P) // initialization 03: repeat

The name of the method stems from the fact that the inequality constraints are called cuts. For the sake of simplicity in this chapter we will restrict to the case of linear integer and mixed-integer programs and postpone the discussion of extensions to the nonlinear case to later on.

Originally this approach was indeed developed for Integer-Linear Programs (ILPs), where the feasible region of the relaxed problem is a polyhedron. From this linear point of view, adding a new valid cut is equivalent to cutting away a part of the feasible region which does not contain any integer-feasible point (cf. Figure 4.3). If this process con-verges to an integer-feasible point this is obviously the global optimum, since valid cuts always preserve the feasible region of the ILP. The cuts are typically constructed in such a way that especially the current non-integral optimal solution of the relaxed problemQ_i is cut off inQ_i+1. Consequently, the optimal solution of the relaxed problem changes in each step and progress of the algorithm is guaranteed. Since the relaxed problem is more and more restricted, the objective function, i.e. the current lower bound, monotonically increases. However, it should be mentioned that the number of required iterations till convergence can get enormous.

The most important ingredient of a cutting-plane approach is the generation of “strong”

valid cuts, i.e. inequalities that push the solution of the relaxed problem as much as possible towards the optimal integer-feasible solution without removing it from the fea-sible set. Again there is no general approach which is optimal for all problem instances.

Accordingly, many different cut generation heuristics, leading to different classes of cuts, were developed in the past. State-of-the-art algorithms often apply a greedy strategy to select from all available cuts. Additionally, the cut selection strategy can typically be tuned by means of several parameters, in order to optimize the performance w.r.t. the intended class of problems. In the following, we will discuss the very general class of Gomory cuts (GC), which is the basis for many other classes of cuts.

Gomory cuts: The main idea of Gomory cuts is straightforward and builds on the idea of integer rounding. We start with the following ILP, given in normal form:

minimize c^Ty

First notice that each linear combination of the above inequalities with positive coef-ficients, i.e. α^TAy ≤ α^Tb with α ∈ Rⁿ+, is a valid inequality for the ILP as well. For

example, if y₁−y₂ ≤2 and y₃ ≤ 4, then of course y₁−y₂+y₃ ≤6. Now, since y_i ≥0, the value of the left-hand side of the equation can be further reduced by rounding down the coefficients leading to Pm

i=1bα^TA_icy_i ≤α^Tb. After this operation the left-hand side is always an integer such that the fractional part of the right-hand side is meaningless and can be rounded off as well. Altogether we end up with the following Gomory cut:

Pm

i=1bα^TA_icy_i ≤ bα^Tbc. It can be shown that this simple procedure is powerful enough to generate all valid inequalities for an ILP [Chv73]. Since this class of Gomory cuts is huge - every linear combination with positive coefficients generates a Gomory cut - the next question consists in, how can a “good” cut from this class be found efficiently? In practice, Gomory cuts are mostly applied in combination with the Simplex algorithm. It turns out that in this setting the generation of well behaved Gomory cuts is very cheap, since adequate linear combinations of the constraints can be taken from the usual Sim-plex tableau without any modification. These linear combinations are guaranteed to cut off the current non-integral solution.

The presented form of Gomory cuts is only applicable in case of pure integer prob-lems, however, the described concept can be generalized to mixed-integer Gomory cuts (MIGC). More details on Gomory cuts, as well as mixed-integer Gomory cuts and many other cuts can be found in [MMWW02, Rus06].

Extension to nonlinear problems: The above cutting-plane approach is applicable in the case of linear programs only. However, exploiting the insight that every convex function can be approximated arbitrarily accurate by local linearizations, i.e. , a set of tangential hyperplanes, the above algorithm can be easily generalized to nonlinear convex programming. The idea of iteratively refined linearizations works for the nonlinear convex objective as well as for the convex feasible region described by the nonlinear convex constraints as illustrated in Figure 4.4. The resulting algorithms building on top of this idea, known asExtended Cutting-Plane Method [WP94] andOuter-Approximation [DG86], alternatingly solve the linearized mixed-integer problem (the approximation resulting from the current set of cuts) and refine the linearization (add further cuts to improve the approximation) until an approximate solution within a given tolerance to the optimal one is found. Solutions to the linearized problem could e.g. be found by the above cutting-plane method for mixed-integer linear programs.

f(x)

x P₁

P₂

P₃

P4

x²+x² ≤1

(a) (b)

Figure 4.4.: Linear approximation of convex nonlinear objective functions and feasi-ble regions: (a) A convex nonlinear objective function can be arbitrarily accurate ap-proximated by a set of tangential hyperplanes Pi. Thus the minimization of f(x) can be replaced by the minimization of the linear function y subject to linear constraints dist(Pi,(x, y)) ≥ 0 ∀i which induce the green contour. (b) The same is possible for nonlinear convex feasible regions. The difference between the unit circle and its lin-earization is shown in green. This deviation can be arbitrarily reduced by adding more hyperplanes.