|
Article Excerpt
The comb inequalities are a well-known class of facet-inducing inequalities for the traveling salesman problem, defined in terms of certain vertex sets called the handle and the teeth. We say that a comb inequality is simple if the following holds for each tooth: Either the intersection of the tooth with the handle has cardinality one, or the part of the tooth outside the handle has cardinality one, or both. The simple comb inequalities generalize the classical 2-matching inequalities of Edmonds [Edmonds, J. 1965. Maximum matching and a polyhedron with 0-1 vertices. J. Res. Nat. Bur. Standards 69B 125-130] and also the so-called Chvatal comb inequalities. In 1982, Padberg and Rat [Padberg, M. W., M. R. Rat. 1982. Odd minimum cut-sets and b-matchings. Math. Oper. Res. 7 67-80] gave a polynomial-time separation algorithm for the 2-matching inequalities, i.e., an algorithm for testing if a given fractional solution to an LP relaxation violates a 2-matching inequality. We extend this significantly by giving a polynomial-time separation algorithm for a class of valid inequalities which includes all simple comb inequalities.
Key words: traveling salesman problem; cutting planes; separation MSC2000 subject classification: Primary: 90C57; secondary: 68W40, 90C27 OR/MS subject classification: Primary: Programming, networks/graphs; secondary: traveling salesman, cutting planes/facets History: Received May 21, 2002; revised June 9, 2004 and October 18, 2005.
1. Introduction. The famous symmetric traveling salesman problem (STSP) is the NP-hard problem of finding a minimum cost Hamiltonian cycle (or tour) in a complete undirected graph. The most successful optimization algorithms at present (e.g., Padberg and Rinaldi [32] and Applegate et al. [1]) are based on an integer programming formulation of the STSP due to Dantzig et al. [9], which we now describe.
Let G be a complete graph with vertex set V and edge set E. For each e [member of] E, let [c.sub.e] be the cost of traversing edge e. For any S [subset] V, let [delta](S) (respectively, E(S)) denote the set of edges in G with exactly one end vertex (respectively, both end vertices) in S. Then, for each e [member of] E define the 0-1 variable [x.sub.e] taking the value one if e is to be in the tour, zero otherwise. Finally, let x(F) for any F [subset] E denote [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] Then, the formulation is:
Minimize [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
subject to:
x ([delta]({i})) = 2 [for all] i [member of] V, (1) x (E(S)) [less than or equal to] [absolute value of S] - 1 [for all] S [subset] V: 2 [less than or equal to] [absolute value of S] [less than or equal to] [absolute value of V] - 2 (2) [x.sub.e] [greater than or equal to] [for all] [member of] E, (3) x [member of] [X.sup.[absolute value of E]] (4)
The equations (1) are called degree equations. The inequalities (2) are called subtour elimination constraints (SECs) and the inequalities (Equation 3) are simple non negativity conditions. Note that an SEC with [absolute value of S] = 2 is a mere upper bound of the form [x.sub.e] [less than or equal to] 1 for some edge e.
The convex hull in [R.sup.[absolute value of E]] of vectors satisfying Equations (1)--(4) is called a symmetric traveling salesman polytope. The polytope defined by Equations (1)-(3) is called a subtour elimination polytope. These polytopes are denoted by STSP(n) and SEP(n), respectively, where n := [absolute value of V]. Clearly, STSP(n) [??] SEP(n) and containment is strict for n [greater than or equal to] 6.
The polytopes STSP(n) have been studied in great depth and many classes of valid and facet-inducing inequalities are known; see the surveys by Junger et al. [18] and Naddef [23]. Here, we are primarily interested in the comb inequalities of Grotschel and Padberg [14, 15], which are defined as follows. Let t [greater than or equal to] 3 be an odd integer. Let H [subset] V and [T.sub.j] [subset] V for j = 1, ....., t be such that [T.sub.j] [intersection] H [not equal to] [empty set] and [T.sub.j]\H [not equal to] [empty set] for j = 1, ... , t, and also let the [T.sub.j] be vertex disjoint. (See Figure 1 for an illustration.) The comb inequality is:
[FIGURE 1 OMITTED]
The set H is called the handle of the comb and the [T.sub.j] are called teeth.
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5)
Comb inequalities induce facets of STSP(n) for n [greater than or equal to] 6 (Grotschel and Padberg [14, 15]). The validity of comb inequalities in the special case where |[T.sub.j] [intersection] H| = 1 for all j was proved by Chvatal [6]. For this reason, inequalities of this type are sometimes referred to as Chvatal comb inequalities. If, in addition, |[T.sub.j]\H| = 1 for all j, then the inequalities reduce to the classical 2-matching inequalities of Edmonds [10].
In this paper we are concerned with a class of inequalities which is intermediate in generality between the class of comb inequalities and the class of Chvatal comb inequalities. For want of a better term, we call them simple comb inequalities, although the reader should be aware that the term simple is used with a different meaning in Padberg and Rinaldi [31] and with yet another meaning in Naddef and Rinaldi [25].
DEFINITION 1.1. A comb (and its associated comb inequality) will be said to be simple if, for all j, either |[T.sub.j] [intersection] H| = 1 or |[T.sub.j]H| = 1 (or both).
So, for example, the comb shown in Figure 1 is simple because |[T.sub.1] [intersection] H|, |[T.sub.2]\H|, and |[T.sub.3] [intersection] H| are all equal to one. Note, however, that it is not a Chvatal comb because |[T.sub.2] [intersection] H| equals two.
For a given class of inequalities, a separation algorithm is a procedure which, given a vector [x.sup.*] [member of] R[absolute value of e] as input, either finds an inequality in the class which is violated by [x.sup.*] or proves that none exists (see Grotschel et al. [16]). In the context of separation for the STSP, it is helpful to define the edge set [E.sup.*] := {e [member of] E: [x.sup.*.sub.e] > 0} and the associated support graph [G.sup.*] = (V, [E.sup.*]). It is also useful to define m = |[E.sup.*]|, the number of variables which are positive at [x.sup.*].
A desirable property of a separation algorithm is that it runs in polynomial time. In 1982, Padberg and Rao [30] gave the first polynomial-time separation algorithm for the 2-matching inequalities. The algorithm is rather complicated and time-consuming, involving the computation of a minimum-weight odd cut in an expanded graph. Recently, Letchford et al. [22] gave a faster and simpler algorithm which, using the preflow push maximum flow algorithm of Goldberg and Tarjan [13] as a subroutine, runs in O(n[m.sup.2] log([n.sup.2]/m)) time.
In Padberg and Grotschel [29, p. 341], it is conjectured that there also exists a polynomial-time separation algorithm for the more general comb inequalities. This conjecture is still unsettled, and in practice many researchers resort to heuristics for comb separation (see, for example, Padberg and Rinaldi [31], Applegate et al. [1], and Naddef and Thienel [26]). Nevertheless, some progress has recently been made on the theoretical side.
In chronological order:
* Carr [5] showed that for a fixed value of t, the separation problem for comb inequalities with t teeth reduces to solving O([n.sup.2t]) maximum flow problems, which takes O([n.sup.2t+l] m log([n.sup.2]/m)) time using the preflow push algorithm.
* Fleischer and Tardos [11] gave an O([n.sup.2] log n) algorithm for detecting maximally violated comb inequalities. (A comb inequality is maximally violated if it is violated by 1/2, which is the largest violation possible if [x.sup.*] [member of] SEP(n).) However, this algorithm only works when [G.sup.*] is planar.
* Caprara et al. [4] showed that the comb inequalities are contained in a more general class of inequalities 1/2}-cuts in O([n.sup.2]m) time. called {0, 1/2}-cuts, and showed how to detect maximally violated {0,
* Letchford [19] defined a different generalization of the comb inequalities called domino parity inequalities, and showed that the associated separation problem can be solved in O([n.sup.3]) time when [G.sup.*] is planar.
* Caprara and Letchford [3] showed that if the handle H is fixed, then the separation problem for a class of inequalities including all {0, 1/2 }-cuts, called split cuts, can be solved in polynomial time. They did not analyse the running time, but the order of the polynomial is likely to be very high.
In this paper, we make another step forward in this line of research by proving the following theorem:
THEOREM 1.1. There is a polynomial time separation algorithm for a class of valid inequalities containing all simple comb inequalities (provided that [x.sup.*] [member of] SEP(n)).
This is a significant extension of the Padberg-Rao [30] result. As in Letchford [19], the proof is based on some results of Caprara and Fischetti [2] concerning {0, 1/2}-cuts, together with arguments which enable one to restrict attention to a small (polynomial-sized) collection of candidate teeth.
The structure of the paper is as follows. In [section]2, we summarize the results given in Caprara and Fischetti [2] about {0, 1/2}-cuts and show how they relate to the simple comb inequalities. In [section]3, we analyse the structure of candidate teeth. In [section]4, we describe a simple version of the separation algorithm and analyse its running time, which turns out to be very high at O([n.sup.9] log n). In [section]5, we show that the running time can be reduced to O([n.sup.2][m.sup.2]log([n.sup.2]/m)). Conclusions are given in [section]6.
NOTE. An extended abstract of this paper appeared in the 2002 IPCO proceedings (Letchford and Lodi [21]). However, the abstract gives a running time of O([n.sup.3][m.sup.3] log n). Here, we describe an improved run time of O([n.sup.2][m.sup.2] log([n.sup.2]/m)). Moreover, we correct a minor error in Letchford and Lodi [21] by showing that our separation algorithm detects not only violated simple comb inequalities, but also inequalities in a slightly extended class.
2. Simple comb inequalities as {0, 1/2}-cuts. As mentioned above, we will need some definitions and results from Caprara and Fischetti [2]. We begin with the definition of {0, 1/2 }-cuts:
DEFINITION 2.1. Given an integer polyhedron [P.sub.I]: = conv{x [member of] [Z.sup.q.sub.+] : Ax [less than or equal to] b}, where A is a p x q integer matrix and b is a column vector with p integer entries, a {0, 1/2 }-cut is a valid inequality for [P.sub.1] of the form
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (6)
where the multiplier vector [lambda] [member of] [{0, 1/2}.sup.p] is chosen so that Ab is not integral.
(Actually, Caprara and Fischetti [2] give a more general definition, applicable when variables are not necessarily required to be nonnegative, but the definition given here is more appropriate for our purposes. Also, note that an equation can easily be represented by two inequalities.)
Define the ith inequality in the system Ax[less than or equal to] b to be used if [[lambda].sub.i] = 1/2. The nonnegativity inequality for a given variable [x.sub.j] is used if the jth coefficient of the vector [lambda]A is fractional. (Rounding down the coefficient of [x.sub.j] on the left-hand side of Equation (6) is equivalent to adding one half of the nonnegativity inequality -[x.sub.j] [less than or equal to] 0.) Using this terminology, we have:
PROPOSITION 2.1. Let [x.sup.*] [member of] [R.sup.q.sub.+] be a point to be separated. Then, a given {0, 1/2 }-cut is violated by [x.sup.*] if and only if the sum of the slacks of the inequalities used, computed with respect to [x.sup.*], is less than one.
Under the (reasonable) assumption that A[x.sup.*] [less than or equal to] b, all slacks are nonnegative and Proposition 2.1 also implies that the slack of each inequality used must be less than one.
Using this, Caprara and Fischetti [2] show that the separation problem for {0, 1/2}-cuts is strongly NP-hard in general but polynomially solvable in certain special cases. One of these special cases is of...
|
