Gomory cuts have the property that they can be generated for any integer program. Their weakness is their downfall: they do not seem to cut off much more than the linear programming solution in practice. An alternative approach is to generate cuts that are specially designed for the particular application. We saw that in a simple form in the lockbox problem, where we used the constraints because they were stronger than . In this section, we examine the symmetric traveling salesperson problem.
Recall that there is no good, compact formulation for the TSP. Earlier, we generated a formulation as follows:
Recall that in the second set of constraints (called subtour elimination constraints) there are many, many constraints. One approach is to initially ignore these constraints and simply solve the problem over the first set of constraints. Suppose we have a six node problem as shown in Figure 6.
Figure 6: Six node traveling salesperson problem
This problem can be formulated as follows (ignoring subtour constraints):
Solving the LP relaxation in LINGO gives:
model min = 4 * x12 + 4 * x13 + 3 * x14 + 4 * x23 + 2 * x25 + 3 * x36 + 4 * x45 + 4 * x46 + 4 * x56; x12 + x13 + x14 = 2; x12 + x23 + x25 = 2; x13 + x23 + x36 = 2; x14 + x45 + x46 = 2; x25 + x45 + x56 = 2; x36 + x46 + x56 = 2; @bnd(0,x12,1); @bnd(0,x13,1); @bnd(0,x14,1); @bnd(0,x23,1); @bnd(0,x25,1); @bnd(0,x36,1); @bnd(0,x45,1); @bnd(0,x46,1); @bnd(0,x56,1); end OPTIMUM FOUND AT STEP 9 SOLUTION OBJECTIVE VALUE = 20.00 VARIABLE VALUE REDUCED COST X12 0.5000000 0.0000000E+00 X13 0.5000000 0.0000000E+00 X14 1.000000 -1.000000 X23 0.5000000 0.0000000E+00 X25 1.000000 -2.000000 X36 1.000000 -1.000000 X45 0.5000000 0.0000000E+00 X46 0.5000000 0.0000000E+00 X56 0.5000000 0.0000000E+00This solution, while obviously not a tour, actually satisfies all of the subtour elimination constraints. At this point we have three choices:
Figure 7: Arc Set for Comb Inequality
It is fairly easy to convince yourself that no tour can use more than 4 of these arcs. This is an example of a broad class of inequalities called comb inequalities. This means that the inequality stating that the sum of the x values on these arcs is less than or equal to 4 is a valid inequality (it does not remove any feasible solution to the integer program). Our solution, however, has 4.5 units on those arcs. Therefore, we can add a constraint to get the following formulation and result:
model min = 4 * x12 + 4 * x13 + 3 * x14 + 4 * x23 + 2 * x25 + 3 * x36 + 4 * x45 + 4 * x46 + 4 * x56; x12 + x13 + x14 = 2; x12 + x23 + x25 = 2; x13 + x23 + x36 = 2; x14 + x45 + x46 = 2; x25 + x45 + x56 = 2; x36 + x46 + x56 = 2; x12 + x13 + x23 + x14 + x25 + x36 < 4; @bnd(0,x12,1); @bnd(0,x13,1); @bnd(0,x14,1); @bnd(0,x23,1); @bnd(0,x25,1); @bnd(0,x36,1); @bnd(0,x45,1); @bnd(0,x46,1); @bnd(0,x56,1); end OPTIMUM FOUND AT STEP 11 SOLUTION OBJECTIVE VALUE = 21.00 VARIABLE VALUE REDUCED COST X12 0.0000000E+00 0.0000000E+00 X13 1.000000 0.0000000E+00 X14 1.000000 0.0000000E+00 X23 1.000000 0.0000000E+00 X25 1.000000 -1.000000 X36 0.0000000E+00 0.0000000E+00 X45 0.0000000E+00 0.0000000E+00 X46 1.000000 0.0000000E+00 X56 1.000000 0.0000000E+00So, we have the optimal solution.
This method, perhaps combined with branch and bound if the solution is still fractional after all known inequalities are examined, has proven to be a very practical and robust method for solving medium-sized TSPs. Futhermore, many classes of inequalities are known for other combinatorial optimization problems. This approach, seriously studied only for the last ten years or so, has greatly increased the size and type of instances that can be effectively solved to optimality.