Cutting Planes :: SAS/OR(R) 13.1 User's Guide: Mathematical Programming

Cutting Planes

The feasible region of every linear program forms a polyhedron. Every polyhedron in n-space can be written as a finite number of half-spaces (equivalently, inequalities). In the notation used in this chapter, this polyhedron is defined by the set ${\mathcal Q}= \{ x \in \mathbb {R}^ n \mid Ax \leq b, l \leq x \leq u\}$ . After you add the restriction that some variables must be integral, the set of feasible solutions, ${\mathcal F}= \{ x \in {\mathcal Q}\mid x_ i \in \mathbb {Z}\; \forall i \in {\mathcal S}\}$ , no longer forms a polyhedron.

The convex hull of a set X is the minimal convex set that contains X. In solving a mixed integer linear program, in order to take advantage of LP-based algorithms you want to find the convex hull, $\textrm{conv}({\mathcal F})$ , of ${\mathcal F}$ . If you can find $\textrm{conv}({\mathcal F})$ and describe it compactly, then you can solve a mixed integer linear program with a linear programming solver. This is generally very difficult, so you must be satisfied with finding an approximation. Typically, the better the approximation, the more efficiently the LP-based branch-and-bound algorithm can perform.

As described in the section Branch-and-Bound Algorithm, the branch-and-bound algorithm begins by solving the linear programming relaxation over the polyhedron ${\mathcal Q}$ . Clearly, ${\mathcal Q}$ contains the convex hull of the feasible region of the original integer program; that is, $\textrm{conv}({\mathcal F}) \subseteq {\mathcal Q}$ .

Cutting plane techniques are used to tighten the linear relaxation to better approximate $\textrm{conv}({\mathcal F})$ . Assume you are given a solution $\bar{x}$ to some intermediate linear relaxation during the branch-and-bound algorithm. A cut, or valid inequality ( $\pi x \leq \pi ^0$ ), is some half-space with the following characteristics:

The half-space contains $\textrm{conv}({\mathcal F})$ ; that is, every integer feasible solution is feasible for the cut ( $\pi x \leq \pi ^0, \forall x \in {\mathcal F}$ ).
The half-space does not contain the current solution $\bar{x}$ ; that is, $\bar{x}$ is not feasible for the cut ( $\pi \bar{x} > \pi ^0$ ).

Cutting planes were first made popular by Dantzig, Fulkerson, and Johnson (1954) in their work on the traveling salesman problem. The two major classifications of cutting planes are generic cuts and structured cuts. Generic cuts are based solely on algebraic arguments and can be applied to any relaxation of any integer program. Structured cuts are specific to certain structures that can be found in some relaxations of the mixed integer linear program. These structures are automatically discovered during the cut initialization phase of the MILP solver. Table 7.15 lists the various types of cutting planes that are built into the MILP solver. Included in each type are algorithms for numerous variations based on different relaxations and lifting techniques. For a survey of cutting plane techniques for mixed integer programming, see Marchand et al. (1999). For a survey of lifting techniques, see Atamturk (2004).

Table 7.15: Cutting Planes in the MILP Solver

Generic Cutting Planes	Structured Cutting Planes
Gomory mixed integer	Cliques
Lift-and-project	Flow cover
Mixed integer rounding	Flow path
Mixed lifted 0-1	Generalized upper bound cover
Zero-half	Implied bound
	Knapsack cover

You can set levels for individual cuts by using the CUTCLIQUE=, CUTFLOWCOVER=, CUTFLOWPATH=, CUTGOMORY=, CUTGUB=, CUTIMPLIED=, CUTKNAPSACK=, CUTLAP=, CUTMILIFTED=, CUTMIR=, and CUTZEROHALF= options. The valid levels for these options are listed in Table 7.14.

The cut level determines the internal strategy that is used by the MILP solver for generating the cutting planes. The strategy consists of several factors, including how frequently the cut search is called, the number of cuts allowed, and the aggressiveness of the search algorithms.

Sophisticated cutting planes, such as those included in the MILP solver, can take a great deal of CPU time. Usually, additional tightening of the relaxation helps speed up the overall process because it provides better bounds for the branch-and-bound tree and helps guide the LP solver toward integer solutions. In rare cases, shutting off cutting planes completely might lead to faster overall run times.

The default settings of the MILP solver have been tuned to work well for most instances. However, problem-specific expertise might suggest adjusting one or more of the strategies. These options give you that flexibility.

The Mixed Integer Linear Programming Solver

Cutting Planes