P O L Y H E D R A L STUDIES O N SCHEDULING AND ROUTING PROBLEMS By Yaoguang Wang B. Sc. Shanghai Fudan University M. Sc. Shanghai Jiao Tong University A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY in THE FACULTY OF GRADUATE STUDIES COMMERCE AND BUSINESS ADMINISTRATION We accept this thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA June 1991 (c) Yaoguang Wang, 1991 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department of Ow^e^- The University of British Columbia Vancouver, Canada Date DE-6 (2/88) T c ^ \ ? > m/ Bt*o'Â»ej>s /W/^.^jf^-f,^ Abstract During the last decade, there have been major advances in solving a class of largescale real world combinatorial optimization problems. Such problems are formulated as Travelling Salesman Problems (TSP), some involving up to thousands of cities. These achievements, mainly due to the use of so called polyhedral techniques, have established the importance of the polyhedral study for various combinatorial optimization problems. This thesis studies polyhedral structures of two well known combinatorial problems: (i) precedence constrained single machine scheduling and (ii) TSP, both Symmetric TSP (STSP) and Asymmetric TSP (ATSP). These problems are of both theoretical interest and practical importance. Better knowledge of the polyhedral descriptions of these problems may facilitate the polyhedral study of more complex scheduling and routing problems. For the scheduling problem, we present two classes of facetial inequalities, which suffice to describe the linear system of the scheduling problem when the precedence constraints are series-parallel. We also propose a cutting plane procedure based on these facet cuts. The computational results show the procedure yields feasible schedules with relative deviations from the optimum less than 0.25% on the average and less than 1% in the empirical worst case. For TSPs, we explore a Hamiltonian path approach to the polyhedral study. We propose various facet extension techniques for deriving large classes of facets from known facets. In the STSP case, we propose new clique lifting results. In the A T S P case, we develop a Tree Composition method, which generates all non-spanning clique tree facetial inequalities. 11 Table of Contents Abstract ii List of Tables v List of Figures vi Acknowledgement 1 2 3 vii Introduction 1 1.1 Preliminaries 2 1.2 Precedence constrained single machine scheduling 4 1.3 Travelling Salesman Problems 7 Single M a c h i n e Scheduling: P o l y h e d r a l Structure 11 2.1 Introduction 11 2.2 Definitions and preliminaries 12 2.3 Three classes of valid inequalities 17 2.4 Structure of the precedence constrained scheduling polyhedra 21 2.5 Facet Lifting 32 2.6 Proofs of the four lemmata 36 Single M a c h i n e Scheduling: P o l y h e d r a l C o m p u t a t i o n s 41 3.1 41 3.2 Introduction A cutting plane procedure 42 iii 4 5 3.2.1 Initial Formulation 43 3.2.2 Cutting Planes and Separation Algorithms 44 3.2.3 Heuristics for the Upper Bounds 49 3.2.4 The Cutting Plane Procedure 50 3.3 Computational Experience 51 3.4 Computational Results for 280 problems 60 Hamiltonian Path and Symmetric Travelling Salesman Problem 67 4.1 Introduction 67 4.2 Definition and Notation 70 4.3 Polyhedral Equivalence: HPP v.s. STSP 72 4.4 Clique-Lifting 80 4.5 Simple Conditions for Node-Cloning 89 Symmetric Inequalities for Asymmetric Travelling Salesman Polytopes 97 5.1 Introduction 5.2 Definitions and Notation 5.3 The ATS Polytope and its Projection 5.4 97 - Symmetric Facet-defining Inequalities 101 104 108 5.5 Composing Symmetric Inequalities 115 5.6 Proofs of the Main Results in Section 5.4 121 5.7 Proofs of the Main Results in Section 5.5 129 Bibliography 138 Appendices 145 A Generating the Sample of 280 scheduling problems 145 iv List o f Tables 3.1 Data for the 10-job example 52 3.2 Cutting planes and the corresponding solutions 52 3.3 Data for the 30-job problem 53 3.4 Solutions from the cutting plane procedure 54 3.5 The optimal schedule and the relevant solutions 55 3.6 A summary of the results for 280 problems 57 3.7 Computational results with respect to P values 58 3.8 Computational results for n = 30,40 60 3.9 Computational results for n = 50,60 61 3.10 Computational results for n = 70,80 62 3.11 Computational results for n = 90,100 63 3.12 Computational results for n = 110,120 64 3.13 Computational results for n â€” 130,140 65 3.14 Computational results for n = 150,160 66 A.l Seeds for the instances with n = 30,40,50,60,70,80,90,100 152 A.2 Seeds for the instances with n = 110,120,130,140,150,160 153 v List of Figures 4.1 Equivalent envelope inequalities 75 4.2 Facet-defining bipartition inequalities 83 4.3 Facet-defining binested inequalities 94 5.1 An ATSP Regular Star Inequality 109 5.2 Symmetric facets and their projections 112 5.3 A 9-node ATSP Chain Inequality 113 5.4 A Tree Composition 118 5.5 A Path Tree obtained from the Tree Compositions 120 5.6 c-tight paths 122 5.7 c-tight paths for the Chain Inequality 128 vi Acknowledgement First, I wish to express my sincere gratitude to Professor Maurice Queyranne for introducing me to the area of scheduling and for his effort in effectively guiding me at every stage of my thesis research. I have benefitted a great deal from his assistance. I gratefully acknowledge the partial financial support from his NSERC Operating Grant. Also, I wish to thank Professor D. Naddef, who gave an inspiring seminar on the travelling salesman problems during his visit in UBC; Professors L.A. Wolsey, C.N. Potts, and Van de Velde, who generously provided their test examples and computer programs for a computational study in my thesis. I am very grateful to Professors E. Balas, F. Granot, D. Granot, R. Israel, D.G. Kirkpatrick and S.T. McCormick for their valuable efforts in examining and correcting the manuscript. I greatly appreciate the financial support from Canada International Development Agency for my doctoral studies. Finally, special thanks are due to my wife Liqun, my parents Meixian and Zufu, for their every effort in taking a good care of my two children and me during difficult times. vii Chapter 1 Introduction Over the past decade, we have witnessed major advances in solving a class of largescale real world combinatorial optimization problems. Such problems are formulated as Travelling Salesman Problems (TSP), some involving up to thousands of cities, see Padberg and Rinaldi [49], and Kolata [31]. These achievements are largely due to the use of so called polyhedral techniques, which employ polyhedral descriptions of the underlying problems. The successes have motivated in recent years extensive studies on polyhedral structures and computations for various combinatorial optimization problems. The present thesis studies polyhedral structures of two well known combinatorial problems, namely, precedence constrained single machine scheduling in Chapter 2, and TSP, both Symmetric TSP (STSP) and Asymmetric TSP (ATSP) in Chapters 4 and 5, respectively. These problems are of both practical importance and theoretical interest, because (a) they are very simple, yet fundamental, versions of machine scheduling and vehicle routing problems, which often arise in production and distribution management; (b) they are strongly NP-hard, see Garey and Johnson [22]. Better knowledge of the polyhedral descriptions of these problems may thence facilitate the polyhedral study of more complex scheduling and routing problems. To test the facetial results derived in Chapter 2, we perform polyhedral computations for the precedence constrained single machine scheduling problem. Chapter 3 introduces a cutting plane procedure which uses effective cuts (i.e., facet-defining inequalities) derived in Chapter 2. Computational results show that the solution procedure 1 Chapter 1. 2 Introduction consistently yields feasible solutions with a guaranteed high accuracy over a broad range of instances. The procedure generates feasible schedules with percent deviation from the optimum less than 0.25% on the average and less than 1% in the empirical worst case. The rest of the chapter is organized as follow. Section 1.1 briefly reviews terminology and notation used for the polyhedral methods. Sections 1.2 and Section 1.3 summarize the motivations and main results in this thesis for the scheduling problem and Travelling Salesman Problems, respectively. Preliminaries 1.1 In this section, we briefly review the terminology and notation which are necessary for our exposition. For a more detailed treatment of the theory of combinatorial polyhedra, we refer to Grotschel and Padberg [28]. Let R denote the real line and if* the n-dimensional real vector space. For x , â€¢ â€¢ â€¢, x G 1 R and Ai, â€¢ â€¢ â€¢, A* G R, the vector x G i f with x = Xix + â€¢ â€¢ â€¢ + n 1 1 XkX k k is called a linear combination of the vectors x , â€¢ â€¢ â€¢, x . If in addition, Ai + â€¢ â€¢ â€¢ + A* = 1 (resp., all A,- are 1 nonnegative and A H k \- Xk = 1), then x is called an affine (resp., convex) combination of the vectors x , â€¢ â€¢ â€¢, x . 1 k If 0 ^ S C i f , then the set of all convex combinations of finitely many vectors in S is called the convex hull of S and is denoted by conv(5). A nonempty set S C i f is called linearly (resp., affinely) independent, if for every 1 finite set {x , x , â€¢ â€¢ â€¢, x } 1 \x k k 2 = 0 and Ai H k C S, the equations Aix + 1 h XkX k = 0 (resp., A i x H 1 h h Xk = 0) imply A, = 0, i â€” 1, â€¢ â€¢ â€¢, k; otherwise 5 is called linearly (resp., affinely) dependent. The rank (resp., affine rank) of a set S G R 71 is the cardinality of the largest linearly (resp., affinely) independent subset of S, and the dimension of S, denoted by dim(5'), is Chapter 1. Introduction 3 the affine rank of S minus one. A set S C RJ is called full-dimensional 1 if dim(S') = n. The notion of affine rank or independence is useful in the theory of polyhedra because it is invariant under translations of the origin. To keep notation to a minimum, we denote by ax the scalar product of any vectors a,x â‚¬ RJ . A set H â‚¬ RJ is said to be a half space if there exist a vector a 6 RJ and a 1 1 1 scalar a (z R such that H = {x 6 RJ : ax < a }. Then H is the halfspace defined by the 1 0 0 inequality ax < ao. An inequality ax < ao is called valid with respect to a set S C if S is contained in the halfspace defined by ax < ao. A valid inequality ax < a for S 0 is called tight, or supporting, if ax = a for some x 6 S. An inequality ax < ao for S is 0 called an implicit equation if ax = ao holds for all x Â£ S. A polyhedron is the intersection offinitelymany halfspaces. A bounded polyhedron is called a polytope. For any polyhedron V C RJ , there exist an (m,n)-matrix A and a 1 vector b â‚¬E Râ„¢ such that V can be represented in the form V = {x <E R n : Ax < b). A subset F of a polyhedron V is called a face of "P if there exists a supporting inequality ax < ao with respect to V such that F = {x G V : ax = a }. We say that the 0 inequality ax < a defines F or is face-defining for V. A /aceÂ£ F of V is any face of V 0 with dimF = dimP â€” 1. A valid inequality aa; < ao is facet-defining, or facet-inducing, if the induced face F = {x Â£ V : ax = ao} contains exactly dimV affinely independent points. A valid inequality fx < fo for V is said to dominate cx < Co if any x Â£ V satisfying cx = Co also satisfies fx = fo. Any two valid inequalities fx < fo and cx < Co are equivalent w.r.t. V if they dominate each other. It is well-known (e.g., [28]) that two valid inequalities for V are equivalent iff one can be obtained by multiplying the other with a positive scalar and adding a linear combination of the implicit equations for V. Chapter 1. Introduction 4 The polyhedral technique is a Linear Programming (LP) approach to combinatorial optimization problems. The feasible solution set to any combinatorial problem can be represented as a collection of points in an appropriate space i f . To apply the polyhedral method, we first need to study the polyhedral structure, i.e., a linear description, of the convex hull V of the feasible solution set. We then devise cutting plane procedures using known valid inequalities which define faces (of high dimension, preferably facets) of V as cutting planes. The procedures often yield very tight lower (resp., upper) bounds if it is a minimization (resp., maximization) problem. Such bounds can then be used in subsequent Branch and Bound or Branch and Cut procedures if an exact optimum is sought. 1.2 Precedence constrained single machine scheduling We consider the following single machine nonpreemptive scheduling problem. Each of n jobs, available for processing at time zero, is to be processed without interruption on a single machine. Associated with each job j is its processing time pj and its linear deferral (delay) cost rate Wj [53], both of which are independent of job sequencing. The machine can process only one job at a time. Precedence constraints may be assumed between jobs. A schedule is specified by the job completion times Cj. A schedule is feasible if it satisfies all precedence constraints. Our objective is to find a feasible schedule so as to minimize the total weighted completion time, i.e., the sum of the deferral costs WjCj. In a production process, such costs WjCj may measure the cost of work-in-process inventory for each job For the treat- ment of other objectives for single machine scheduling, such as minimizing makespan, weighted tardiness, the number of late jobs, etc., interested readers are referred to an excellent survey by Lawler et al [36]. Chapter 1. Introduction 5 When there are no precedence constraints, the problem can be solved, in 0(n log n) computational steps, by sequencing jobs in nonincreasing order of ratios Wj/pj [54]. Special precedence relations, such as rooted trees, parallel chains, etc., were considered by Sidney [53]. Lawler [33] considered series-parallel precedence relation which subsumes all previous special cases, and derived an elegant 0(nlog n) optimization procedure. With general precedence constraints, the problem becomes strongly NP-hard even if the weights or processing times are assumed to be zero or one [33,37]. This indicates that the existence of a polynomially bounded optimization algorithm is highly unlikely. For the problems with general constraints, Potts [50] summarized various solution methods up to 1985, and presented an integer programming formulation, where a Branch and Bound solution procedure is applied using lower bounds from a Lagrangian Relaxation. Recently, Van de Velde (1990) proposed a dual decomposition method based on another Lagrangian Relaxation [56]. These methods have difficulties in solving large problems because of weak lower bounds. The reported computational results for these methods involve problems of size only up to 100 jobs. Balas [3] pioneered the study of scheduling polyhedra on a closely related job shop scheduling problem, allowing for multiple machines, release dates and sequence-dependent changeover times. In his work, precedence constraints only arise between jobs processed on different machines. Balas gives some fundamental results about scheduling polyhedra and partial characterizations thereof. Queyranne [52] studied single machine scheduling polyhedra, and derived the class of facet-defining inequalities for the scheduling polyhedra without precedence constraints. He also proposed an 0(n log n) separation algorithm for this class of inequalities. Other polyhedral studies of scheduling problems explored alternate formulations. Dyer and Wolsey [16] used a mixed-integer programming formulation for the single machine problem with release dates. They also compared alternate relaxations in terms of Chapter 1. Introduction 6 the resulting lower bounds for that problem. Sousa and Wolsey [55] used a large-scale 0-1 programming formulation for the single machine problem with release dates, deadlines and a general separable objective function. More recently, Wolsey [57] considered extended mixed-integer programming formulations, and derived very tight lower bounds, for the precedence constrained scheduling problem. His formulations involve 0(n ) vari2 ables, mostly binary, and 0(n ) or 0(n ) 2 3 constraints. In this thesis, we consider a formulation of the precedence constrained single scheduling problem involving only n variables, one per job. In C h a p t e r 2, we propose three classes of facet denning inequalities for the scheduling problem. We show that two classes suffice to define the scheduling polyhedra when the constraints are series-parallel. The first class, introduced by Queyranne [52], consists of inequalities that result from parallel composition, and are thus called parallel inequalities. The inequalities in the second class result from series compositions and are called series inequalities. In C h a p t e r 3, we develop a cutting plane algorithm for the scheduling problem. The Cutting plane methods, based on facet defining inequalities, have proven to be highly successful in solving large scale TSP problems [49]. In contrast, the cutting plane approaches have not been well explored in the area of scheduling [56]. This motivates the present computational study. The proposed algorithm includes separation procedures for the above facet cuts. The separation for the class of parallel inequalities takes 0(n log n) computational steps. The separation for a subclass of series inequalities, called simple series inequalities, requires 0(n ) 2 computational steps. The algorithm is tested on an IDM 386/25 Personal Computer. We use a random sample of several hundred problems with up to several hundreds of jobs. The computational results show that this algorithm consistently yields tight lower bounds and feasible schedules with maximum percent deviations from the optimum less than 0.25 % on the average, and less than 1 % in the empirical worst case. Chapter 1. Introduction 7 These results indicate that the polyhedral approach has potential for solving large-size constrained scheduling problems. These tight bounds can be used for other optimization procedures, such as Branch and Bound or Branch and Cut methods if an optimal schedule is sought. The ultimate goal of this research will be to apply similar polyhedral techniques to more complex scheduling problems. 1.3 Travelling Salesman Problems Travelling Salesman Problems (TSPs) arise when seeking a shortest tour, starting from a home city, visiting each given city exactly once and then returning to the home city. If the travel distance (or cost) from one city to another equals the return distance, the problem is called a Symmetric Travelling Salesman (STS) problem; otherwise it is an Asymmetric Travelling Salesman (ATS) problem. For more than a century, TSP has been one of the most well-known mathematical problems and is notoriously difficult. TSPs are of both theoretical interest and practical importance. They are known to be so-called strongly JVP-hard, see Garey and Johnson [22]. Therefore the existence of a polynomial optimization algorithm is highly unlikely. On the other hand, many practical problems in production and distribution can be formulated as TSPs. For example, such problems arise in the fabrication of circuit boards, where lasers must drill tens to hundreds of thousands of holes in a board. Deciding an optimal order to drill these holes is a travelling salesman problem. TSPs also represent the simple versions of vehicle routing problems. Kearny [30] reported that annual distribution costs in the United States are about 400 billion dollars. We refer to [35] for a thorough discussion of, and motivation for, the study of Travelling Salesman problems. For convenience, we consider STS and ATS problems in complete graphs on any given node set V. A feasible solution to the STS (resp., ATS) problem is a Hamiltonian 8 Chapter 1. Introduction circuit C on V , uniquely determined by its corresponding 0-1 incidence vector y , where c = 1 if edge e is used in C and zero otherwise. The STS polytope STSP(V) ATS polytope ATSP(V')) (resp., is the convex hull of all incidence vectors of feasible solutions to the STS (resp., ATS) problem on V. In addition to being interesting mathematical objects in themselves, these poly topes are worthy of study because corresponding valid linear inequalities, in particular those that are facet-defining, play an important role in formulating and solving Travelling Salesman problems. There have been major advances in solving many large scale real world Travelling Salesman problems over the past decade. The most notable one is the resolution of the 2392-city problem by Padberg and Rinaldi [49]. (See also Kolata [31] for a recent report on some ongoing work.) They developed an effective Branch and Cut procedure which uses some simple families of facet defining inequalities, namely the subtour elimination constraints and simple clique tree inequalities. Their success has motivated extensive study of polyhedral structure of TSP. For more details, we refer to Grotschel and Padberg [28]. To establish facetial results for a given polyhedron, indirect proofs (or polyhedral proofs) [28] are often used. Such proofs are particularly effective if the polyhedron is full dimensional, because an inequality defining any given facet is unique up to a positive multiple. However, this is not the case for TSPs. Since every solution to TSPs satisfies degree constraint equations, i.e., the restrictions that the travelling salesman enters each city and leaves it exactly once, the resulting polytopes are far from being full dimensional. This considerably complicates indirect proofs for TSP polyhedral results [27,28], [29]. In recent years, two major research directions have been followed for the polyhedral study of TSPs. The first one is to reformulate TSPs by relaxing the degree constraints: the monotone relaxation [28] (resp., graphical relaxation [13],[10]) assumes that each city is visited at most once (resp., at least once). The resulting polytopes contain Chapter 1. Introduction 9 TS polytopes as faces, and have full dimension. The second approach employs cliquelifting [27],[38],[41], [6] for extending TSP facets, and composition [41] techniques for extending STSP facets. Using these approaches, large classes of facet defining inequalities have been obtained. However, the derivations of these results still require very complicated and lengthy proofs, see [27,28], [29], [41]. The primary motivation for the present work is twofold. First, as the search for TSP facets becomes increasingly difficult, a simple, alternate approach is proposed. Second, while new TSP facets emerge from time to time, stronger but easily applicable facet generating operations are of particular interest. This thesis explores a projective approach to the polyhedral study of Travelling Salesman (TS) problems. Suppose that we ignore the visit of the home city, and seek a shortest path that visits each city exactly once with arbitrary (and distinct) initial and final cities. This is called a Shortest Hamiltonian Path (SHP) problem. The associated polytope, the Hamiltonian Path (HP) Polytope, is the convex hull of incidence vectors of all Hamiltonian paths. First, we observe that there is a one-to-one correspondence between solutions of TSP and those of HP problems. Next, we note that in the SHP problem, all degree constraints are relaxed, because the end cities are not fixed in advance. These observations lead to a projective approach to the polyhedral study of TSPs. More precisely, we show that an HP polytope is a projection of a TS polytope. Two important properties are: (a) near-full dimensionality. HP polytopes are of full dimension minus one; (b) polyhedral equivalence: the polyhedral structures of the HP polytope and the STS polytope are isomorphic. Property (a) greatly facilitates the study of HP polytopes, and property (b) enables one to directly transfer facetial results from HP polytopes to TS polytopes. In C h a p t e r 4, we study Symmetric Travelling Salesman (STS) polytopes. Using the projective approach, we first derive various Clique-Lifting techniques to extend known STS facets. We then demonstrate how these lifting results generalize previous results. Chapter 1. Introduction 10 Finally, we show that all facets with 0 â€” 1 coefficients are clique-liftable with respect to any node. In Chapter 5, we study Asymmetric Travelling Salesman (ATS) polytopes. As Balas and Fischetti [6] have shown that all ATS facets can be clique-lifted, we consider another type of facet extension technique, facet composition. In particular, we work on symmetric inequalities (i.e., those inequalities ax < a with coefficients satisfying a,v,- = a^,- for all i 0 and j). By this facet composition technique, we show that large known classes of facets of STS polytopes also induce facets of ATS polytopes. On the other hand, all symmetric facet defining inequalities for ATS polytopes are easily shown to induce facets of the STS polytopes [18]. As a result, new facets of STS polytopes can also be derived in this fashion. Chapter 2 Single Machine Scheduling: Polyhedral Structure 2.1 Introduction A set N = {1,2, â€¢â€¢â€¢,n} of jobs is to be processed without interruption on a single machine. All jobs are released at time t = 0. At any instant, the machine can process at most one job. With each job j G N is associated a known positive processing time pj. Precedence constraints are represented by an acyclic digraph G(N) = (N,A(N)), where G A(N) denotes that job i must be processed before job j. We use the job completion times C â€” (C\, â€¢ â€¢ â€¢, C )* to describe schedules of interest. n Thus, by letting I N denote the index set of the jobs in N that can be sequenced first (i.e., those jobs without predecessors), the collection of all feasible schedules can be represented as follows: T(N) = {C G R N Ci - d > : d > P i , Vi G I ; N Vi V Ci - Cj > , Pi Cj - d > P j , V(Â», j) G A(N); Vi, j G N, ijL j, $ A(N)} We note that T(N) is a disjunctive set. Most of the research on this subject to date deals with optimization versions of the job sequencing problem with some objective function /(C) over T(N). For general precedence relations on the job set, the optimization problem has been shown to be iVP-hard, see [33,37]. However, if the precedence constraints are series-parallel and the objective function f(C) admits of a string interchange relation (linear functions are special cases), an optimal sequence can be found in 0(nlog n) time, see Lawler [34]. 11 Chapter 2. Single Machine Scheduling: Polyhedral Structure 12 In this chapter, we study the facial structure of the scheduling polyhedron P(N) defined as follows: P(N) = conv(r(iV)) In the next section, we introduce notation, definitions and preliminary algebraic results. We present some classes of valid inequalities for the scheduling polyhedron P(N) with general precedence constraints in section 2.3, and a partial description of its facial structure in section 2.4. Three classes of valid inequalities used in this description are associated with series composition, parallel composition and induced Z-subgraphs, respectively. The class of inequalities used in Queyranne [52] is a special case of the parallel composition class. In section 2.5, we derive the unique minimal linear system defining P(N), consisting of the first two classes of facet-inducing inequalities, if the precedence constraints are series-parallel. We also show that facet-inducing inequalities of the third class, associated with .2/-induced subgraphs, arise whenever the precedence constraints are not series-parallel. 2.2 Definitions a n d preliminaries Graph G(S) = (S,A(S)) is said to be a subgraph of G(N) induced by S if S C N and A(S) â€” E A(N) : i E S,j E S}. Similarly, we define the collection of all feasible subschedules induced by job set S C N: T(S) = {CeR : s CJ - Ci > d> P j , Vi E I ; Cj -d> s Pi V d - Cj > p u e , Pj Vt,j 6 S, j, A(S); $ A(S)}. Note now that G(S) specifies precedence relations on job set S and the scheduling polyhedron induced by 5" is P{S) = conv(T(S)). Chapter 2. Single Machine Scheduling: Polyhedral Structure 13 Node i has precedence over node j (or job i must be processed before job j), denoted by i â€”â€¢ j, if there is a directed path from i to j in G(N) = (JV, A(N)). Similarly, for any disjoint subsets Si, S2 of JV, Si â€”â€¢ 1S2 iff * â€”* j f Â° all i G S i and j â‚¬ 52. For any S C JV, r A ( S ) is said to be transitively reduced ii G -A('S') implies that (*,./) is the unique directed path from i to j in G(S). For any S C JV, A(S) is said to be transitively closed if {(<,*), (*,i)}CA(5)^(i,i)â‚¬A(5). Note that if Ai(S) and ^ ( 5 ) are two transitively closed arc sets containing A(S), then so is Ai(S) D A ^ S " ) . Therefore, we may define the transitive closure of A(S) as the smallest transitively closed set A(S) satisfying A(S) 3 A(S). Unless otherwise noted, we use A(S) (resp., A(S)) to represent the transitively reduced arc set (resp., the transitive closure) of A(S). A set 5 C iV is said to be Z-inducing if |5| > 4 and there exists a numbering of the nodes in S such that S = { 1 , 2 , 3 , k } and {(1,2), (3,2), (3,4)}. Note that a graph G(N) G A(N) : i,j G {1,2,3,4}} = contains a Z-subgraph if there is a Z- inducing subset S C N. Note also that a graph is series-parallel if and only if it contains no Z-subgraph, see Lawler [34]. Graph G(S) is series-decomposable if there exists a partition (S\,S2) of S such that Si â€”* S2, in which case, we may write S = Si A schedule C G R s S2. is a permutation schedule on S if C G T(S) has no inserted idle times. Subset 5 C iV is an initial set of N if fc â€”> j and j G 5 imply k â‚¬ S. Subset 5 C TV is a terminal set of JV if i â€”> A; and i Â£ 5 imply 6 5. Subset 5 C JV is an intermediate set of JV if z â€”> fc â€”â€¢ j , i G Â£ and j G 5 imply G S. Chapter 2. Single Machine Scheduling: Polyhedral Structure 14 Note that the intersection of any collection of initial (resp., terminal; resp., intermediate) sets is an initial (resp., terminal; resp., intermediate) set. Thus, for any S C JV, let I(S) = C\{I S C / , 7. is initial}, T(S) = f\{T : S C T, T is terminal}, Q(S) = f]{Q : : 5 C Q , Q is intermediate}. We call I(S) (resp., T(S), Q(S)) the smallest initial (resp., terminal, intermediate) set containing 5". The following three propositions establish some properties of the subsets / , T and Q of N. P r o p o s i t i o n 2.1 S C N is an initial set of N iff N \ S is a terminal set of N. P r o p o s i t i o n 2.2 If S C. N is an initial or a terminal set of N, then S is an intermediate set of N. Proofs of Propositions 2.1 and 2.2 are straightforward, and therefore omitted. P r o p o s i t i o n 2.3 Assume 1. Q is an intermediate set of N; and 2. I(Q) is the smallest initial set of N containing Q. Then, Q is a terminal set of I(Q). Proof. By contradiction, suppose that Q is not a terminal set of I(Q), i.e., there exists some j (E Q such that j â€”> k for some k 6 I(Q) \ Q- We claim that ,k has no successors in Q since otherwise assumption (1) implies k G Q which is a contradiction. Let V be Chapter 2. 15 Single Machine Scheduling: Polyhedral Structure the set containing k and all its successors. Thus, I(Q) \ V is another initial set of N containing Q which contradicts assumption (2). â€¢ For S C N, we let as Â£ R be the subvector of a â‚¬ R s in a indexed by S. Let (S\,S2) be a partition of S. a, b Â£ R , we mean that { s For arbitrary vectors u,v Â£ R N N whose components are those Then by C = (as ,bs ), 1 2 where if k Â£ Si] a, k if k Â£ S . and subset S C N, we let bk, 2 Â«(5) = EÂ«iÂ» Â« (s) = E Â« i > a jes jes Define also P r o p o s i t i o n 2.4 Letw k g(S) = ( (S) +p (S))/2, g'(S) = (p(S) -p (S))/2. Â£ R, k = l,...,n. Let a' Â£ R , 2 P 2 2 2 N i = \,..., n = \N\, be n affinely independent vectors satisfying n k \ = o, k=i X and let S = {k : w ^ k w a w (2.1) Vi, 0}. Then, 1. There are precisely s = \S\ affinely independent vectors in {a* : i = l,...,n}; and s 2. There are precisely I = \V\ + 1 affinely independent vectors in {ay : i = l,...,n} for allV CN such that S Â£ V. Chapter 2. Single Machine Scheduling: Polyhedral Structure 16 Proof. (1) Let M be an n by n + 1 matrix whose ith row is ((a*)', 1); Ms be an n by s + 1 submatrix of M whose ith row is ((a )', 1); and My be an n by / submatrix of M whose s iih row is ((ay)', 1). ( 2.1) implies that the rank of M is n (denoted by r(M) = n). Thus, there is a unique (up to multiples) solution to the system Mx = 0, (2.2) namely, by ( 2.1), the solution ' Wk, *2 = < â€” W o , . 0, if k G S; if k = n + 1; otherwise. Since r(Ms) < s implies that r(M) < n and r(Ms) > s implies that xÂ° does not solve ( 2.2), we must have r(Ms) = s. Hence, (1) follows. (2) Obviously, r(Mv) < /. We claim that r(Mv) > / since otherwise we have Myz = 0 for some z ^ 0. Using this z, we can construct another solution, linearly independent of xÂ°, to ( 2.2) which is a contradiction with ( 2.1). Hence, (ii) follows. â€¢ C o r o l l a r y 2.5 The facet-inducing inequalities for a full dimensional polyhedron P C R N are unique up to some positive multiples. Proof. Since P C R N is full dimensional, there exists no equation satisfied by all points x e P C R . The result then follows from Theorems 2.5 and 2.6 in Pulleyblank [51]. â€¢ N Proposition 2.4 and Corollary 2.5 are used in Section 4 for proving that certain valid inequalities are facet-inducing. Chapter 2. Single Machine Scheduling: 2.3 Polyhedral Structure 17 Three classes of valid inequalities To make the cutting plane method a success, valid inequalities, especially those inducing facets, play a key role. In this section, we present some classes of valid inequalities for P(N). Of particular interest are those valid inequalities which, under certain conditions, are facet-inducing. Proposition 2.7 and Proposition 2.8 give three classes of valid inequalities which play an important role in the sequel. We begin with Proposition 2.6 which gives a necessary condition for an inequality to be valid for P(N). Proposition 2.6 If is a valid inequality for P(N), then w(N) > 0. Proof. Suppose that w(N) < 0. Let C â‚¬ P(N) be a schedule and y E R, and let C = C + yl, where 1 G RJ is a vector of one's. 1 Clearly, C (E P(N) for all y > 0. But ^ k â‚¬ N w Ck < w for y sufficiently large, which produces a contradiction. k 0 â€¢ We call a valid inequality for P(N) a positive-sum (resp., zero-sum) valid inequality if w(N) > 0 (resp., w(N) = 0). We now present three classes of valid inequalities for P{N). The first class was introduced in Queyranne [52]. The other two are new, arising from the precedence constraints. Proposition 2.7 (i) For all S C JV, p*C(S)>g(S) (2.3) Chapter 2. Single Machine Scheduling: Polyhedral Structure 18 is a valid inequality for P(N). Moreover, inequality (2.3) is tight if S is an initial set of N. (ii) For any Si C JV, S2 Q N such that Si â€”> S2, F(S U S) = 2 - (S2)p * C(Si) + p(Si)p * C(S ) P 2 -p(S )g(Si) 2 is a valid inequality of P(N). - p(Si)g(S2) + (S2)p (Si) 2 P > 0 (2.4) Moreover, inequality (2.4) is tight if S = Si U S2 is an intermediate set of N. Proof. It follows from Theorem 3.1 of Queyranne [52] that (2.3) is a valid inequality for P(N). Next, observe that if S is initial, then any permutation schedule in T(N) with sequence (S, N \ S) is tight for (2.3). This completes the proof for (i) (ii) Note that for any C G T(N), there exists a time t such that (a) all jobs indexed by Si are completed before or at time t, and (b) all jobs indexed by S2 start after or at time t. Using the results in (i), we have (a) implies P(S2) Â£ " G+Pi) > 9(Si)p(S ), 2 (2.5) t'eSi and (b) implies P(SI) E - 0 > 9(S2) (Si). P (2.6) Adding (2.5) to (2.6) yields (2.4). Next, observe that if S is intermediate, then for some t > 0, there exists a feasible permutation schedule tight for both (2.5) and (2.6), therefore tight for (2.4). â€¢ Suppose now that N is Z-inducing. This structure is used to generate the third class of valid inequalities studied here. Because N is Z-inducing, there exists a numbering of Chapter 2. Single Machine Scheduling: Polyhedral Structure 19 nodes in JV such that G A{N):Vi,j G {1,2,3,4}} = {(1,2),(3,2),(3,4)}. For any Q C {i G JV : {(3, i), (*, 2)} C A(N), {(1, i), (i, 1), (4, i), (Â»,4)} n A(JV) = 0}, let S= {1,2,3,4} ug, S' = S\{3}, S" = S\{2}, = {1,3} U Q, and S = {2,4} U Q . 2 Note that Q may be empty. Proposition 2.8 The following inequalities -p(S')p*C(S' ) + 1 > -P1P2C1 \P({1}UQ)P(S)+P2P3}C2+P3P4C 4 p(S') '({l,2,3}UQ)+P3Pl, (2.7) 9 - b({4}ug)p(5)+p p3]C3-rK^>*c(52) 2 > p(^"M{M}UQ)+ftP2P3 (2.8) are valid for P(N). Moreover, they are tight if S is intermediate. Proof. Define T 3 1 = {C â‚¬ T(JV) : Ci - C > } 3 T(N) = T 31 1 3 = {C G T(JV) : C - Ci > p } â€¢ Clearly, 3 3 r . U C l a i m 1. and T Pl 13 (2.7) is valid for T 3 1 . Proof. Note that the definition of T 3 1 implies that {3} â€” > S'. Using P r o p o s i - tion 2.7(ii) with Si = {3} and S = S', the inequality 2 - P(S') C P3 is valid for T 3 1 3 + p (p * C(S')) > p g(S') 3 (2.9) 3 . Using Proposition 2.7(H) again, but with Si = {1} U Q and S = {2}, 2 the inequality (S)[-piCi P - p * C(Q) +p({l}U Q)C ] > p(S)g'({1,2} U Q) 2 (2.10) Chapter 2. Single Machine Scheduling: Polyhedral Structure 20 is valid for T . The sum of (2.9) and (2.10) yields (2.7). 3 1 This completes the proof for C l a i m 1. C l a i m 2. (2.7) is valid for T . 1 3 Proof. Note that for T , we have {1} -+ {3} -> {Q,2,4}. The following two 1 3 inequalities j * p ( S ' ) ( - C i + C ) > p(S')(P2 2 PM-C +P3 Pl (2.11) + p(Q)), + C ) > p (p2 + p(Q)), 3 a Pl (2.12) 3 directly follow from the induced precedence relation {1} â€”Â» {3} â€”Â» Q â€”Â» {2}. Using Proposition 2.7(h) with Si = {3} and 5*2 = S' , the inequality 2 - P(S' ) 3C 2 P + p * C(5 ) > 2 P3 3 P39 (2.13) (S' ) 2 valid for T . Also, using Proposition 2.7(h) with S\ = Q and S'2 = {2}, the inequality 1 3 - p(S) * C(Q) + (S)p(Q)C P P > (S)g'({2} U Q) 2 (2.14) P is valid for T . The sum of (2.11) to (2.14) yields (2.7). This completes the proof for 1 3 C l a i m 2. C l a i m 1 and C l a i m 2 imply that (2.7) is valid for T(N), and therefore for P{N). Similarly, we can show (2.8) is a valid inequality for P(N) by considering T 2 4 = {C e T(N) : C - C > M i 2 and T 4 2 = {C â‚¬ T(N) :C -C > 2 4 p }. 2 Next, observe that if S is intermediate, then any feasible schedule with uninterrupted subsequence (3,1,Q,4,2) (no idle time, no other jobs in between) is tight for (2.7) and (2.8). The proof is complete. â€¢ We call the inequality (2.3) parallel-inequality, (2.4) series-inequality, and the inequalities (2.7) and (2.8) Z-inequalities, respectively. Chapter 2. Single Machine Scheduling: Polyhedral Structure 2.4 21 Structure of the precedence constrained scheduling p o l y h e d r a In this section, we study the facial structure of P(N). We begin with a discussion of some properties of the faces of P(N). We then show under which conditions the valid inequalities, introduced in the previous section, are facet-inducing for P(N). The proofs of all lemmata in this section are found in section 2.6. L e m m a 2.9 Let n = \N\. A valid inequality Y. w iÂ°i ^ w <> (- ) 2 15 ;eiv is (n â€” bâ€”l)-dimensional face-inducing for P(N), where b = 0 , 1 , 2 , n â€” 1, if and only if there are precisely n â€” b affinely independent feasible schedules C Â£ P(N),j J = l,...,ra â€” b, all tight for (2.15). Note. The above lemma is implicitly assumed in Balas [3], proof of Theorem 4.4. With L e m m a 2.9, we may use solutions or schedules interchangeably in the state- ments about faces of scheduling polyhedra. L e m m a 2.10 Set S is not series-decomposable if and only if there exist at least \S\ affinely independent permutation schedules in T(S). The above two lemmata are used in studying the dimension of the face of P(N). We are now in a position to study the facial structure of P(N). T h e o r e m 2.11 (Face-Lifting T h e o r e m ) Let E^i>Â«)o, Â»es (2.16) where C â‚¬ R , be an (s â€” b â€” 1)-dimensional face-inducing inequality of P(S), where s 0<b<s. Chapter 2. Single Machine Scheduling: Polyhedral Structure 22 (1) If S is an initial set of N, then (2.16) is an (re â€” b â€” l)-dimensional face-inducing inequality for P(N). (2) If S is an intermediate set of N with w(S) = 0, then (2.16) is a zero-sum (re â€” b â€” 1)-dimensional face-inducing inequality for Proof. Let s = \S\ and F S P(N). = 0, for all i G N \ S. Let = {C eP(S):'Â£w C i First, note that since C G T(N) = w }, i SCN. 0 Cs G T(S), any valid inequality for P(S) induces a valid inequality for P{N), and hence so does (2.16): Ylies iCi w C G (2.17) ^ o holds for all w P(N). Next, let P(S) be represented by a minimal linear system, that is, P(S) = {CeR : 5> C,- S M â€¢ > a , h G /}, (2.18) M ies where / is an index set of all facet-inducing inequalities. For face Fs, let I = {hâ‚¬l: = Â°fco,VC E Fs}. e (2.19) Face Fs is an (5 â€” b â€” l)-dimensional face of P(S) if and only if matrix A with rows a^., e h G I , has rank 6 + 1 . As observed before, the inequalities e ^2a Ci>a , hi h0 Vh G I , e are also valid inequalities for P(N). Moreover, these inequalities are tight for all C G FNTherefore, F^ is at most (re â€” b â€” l)-dimensional. We are done if we find (n â€” b) affinely independent schedules in FN. (1) 5" is initial. Since Fs is (s â€” b â€” l)-dimensional, there exist s â€” b affinely independent feasible schedules C G Fs, for all j = 1 , s 3 S â€” b. Chapter 2. Single Machine Scheduling: Polyhedral Structure Let C \ N S G T(N \ S), and u = max{(CJ)jt : k G S,j = l,...,s - 6}. 23 For all j = 1, ...,s - b, let i G S; I (C \s)i + Â«, if ieN\s. N Since S is an initial set of JV, by Proposition 2.1, JV \ S is a terminal set of JV. It follows that C' eT{N),j N = i ...,s-b. 1 Now, define _ f Cjv, if 1 < j < a - 6; + J2k=j+b e*(*), if a - 6 < j < n - b; where 7r is the permutation induced by Cjy. It is easy to verify that C G F^,j â€” 1 , n â€” b , and that they are affinely independent. 7 (2) S is intermediate. Since Fs is (s â€” b â€” 1) dimensional, there are 5 â€” 6 affinely independent schedules, C G Fs, j = 1 , 2 , s â€” b. 3 S Let U = {k : k G JV \ S, 3i G S, k -> Â»}, V = JV \ (5 U U) , and u = Let Cr/ G T(U), C G T(V). v Let mi = max{(Cr/),- : i G U}, m = mi + max{(Cs); : i G 5, j = 1 , s â€” b}. 2 Define the following schedules for P(N). For j = u + 1, u + 2 , M + 5â€” b, ( {Cu)i, iii E U; (C' )i = | rm + (Cs~ h if*eS"; I m + (Cv),-, iii EV. u N 2 For j = 1 , 2 , u , and j = U + s â€” 6 + 1, u + 5 â€” 6 + 2 , n â€” b, n k=a{j) Chapter 2. Single Machine Scheduling: Polyhedral Structure 24 where ir is the permutation induced by C# and (j, if 1 < j < Â«; {j + o, otherwise. It can be easily verified that schedules C 3 N G FN, j = 1 , n â€” b, are affinely inde- pendent. Therefore, we have constructed (n â€” b) affinely independent schedules in FN in either case. Note that if U (or V) is empty, the above proof is simplified. This completes the proof of the lifting theorem. â€¢ We mentioned in the previous section that valid inequalities (2.3), (2.4), (2.7) and (2.8) are tight under certain conditions. We study below the dimension of the face they induce under those conditions. Before showing this, we need some intermediate results. L e m m a 2.12 Let Â£ wC > w k keN k (2.20) 0 be facet-inducing for P(N) and let S be an initial set of N such that for some i G S, W{ ^ 0 and w(S) = w(N). Then w = 0, for allkeN\S. k L e m m a 2.13 Let E kC w k keN > wo (2.21) induce a d-dimensional face of P(N), where 0 < d < n â€” 1, and let Q be the smallest set containing S â€” {i G N : Wi ^ 0}, which is initial ifw(N) > 0/ intermediate ifw(N) = 0. Then, for every schedule C G T(N) tight for (4-5.1), CQ â€” tlq, for some t >0 ifw(N) > 0), is a permutation schedule in T(Q), if any of the following conditions holds: (i) there exists no proper initial set Qo of Q such that w(Qo) = w(N); or (ii) d = n â€” 1. Chapter 2. Single Machine Scheduling: Polyhedral Structure 25 Lemma 2.13 asserts that, under the stated conditions, any schedule C tight for (2.21) has the jobs in Q processed consecutively, that is, without any other jobs (jobs not in Q) or idle time inserted in between. Theorem 2.14 and Theorem 2.16 relate the dimension of a face to the number of series compositions in an appropriate set containing all jobs with nonzero coefficients in the corresponding inequality. In Theorem 2.14, we consider positive-sum inequalities, while in Theorem 2.16, we consider zero-sum inequalities. Theorem 2.14 Let X>,C;>u;o (2-22) be a positive-sum tight valid inequality for P(N). Let S be the smallest initial set containing S = {i G N : Wi ^ 0}. Assume (i) there exists no proper initial set So of S such that w(So) = w(N); and (ii) S = Si â€”> S 2 â€”> â€¢ â€¢ â€¢ â€”* Sb+i, where 0 < b < n â€” 1 is the total number series-compositions in S. Then, FN = { C G P(N) : w * C(S) = w } is at most (n â€” b â€” 1)-dimensional. 0 Proof. Note that b = 0 iff S is not series-decomposable, and thus, (ii) implies that (2.22) is not facet-inducing if b > 0. By condition (i), Lemma 2.13 implies that for any C G T(N) D FN, Cs is a permutation schedule in T(S), and therefore C is tight for all series-inequalities (2.4) induced by the b pairs of sets, (Si - Â» S ), (S - Â» S 3 ) , â€”, (Sb - * S& i), (cf. Proposition 2.7). 2 2 + Assume that we have afiniteP(7V)-defining linear system a^C > a^ , h G / , including 0 (2.22) as the first inequality, and the inequalities (2.4) induced by (S;_i â€”Â» Si) as the i-ih inequality for i = 2 , 6 + 1 . Note now that for all C G FN, a-hC = a , ho h= l,...,b+l. Chapter 2. Single Machine Scheduling: Polyhedral Structure It suffices to show that a^, h = l,...,b+l, 26 are linearly independent. Let A be the matrix whose rows are a/,, h = 1 , 6 + 1. For any y Â£ R e yA t b+1 such that = 0 , we have f N e 0 = y'A^N = y\w(N), 0 , . . , Of = w(N) Vl and therefore y\ = 0 since w(N) > 0. Further, observe that any square submatrix of A e with columns corresponding to exactly one job from each set Si,i = 1, is a diagonal matrix with nonzero diagonal elements. Thus, rows 2 , 6 + 1 of A are linearly e independent, which implies that y = â€¢â€¢â€¢ = J/6+i = 0. It follows that A itself is of rank 2 e 6 + 1 . Therefore, face Fu is of dimension at most (ra â€” 6 â€” 1). the proof is complete. â€¢ The following theorem yields the dimension of the face induced by a parallel inequality (2.3). ^ T h e o r e m 2.15 For any initial set S C N, p*C(S)>g(S) (2.23) is an (n â€” 6 â€” 1)-dimensional face-inducing inequality for P(N), where 0 < 6 < n â€” 1 is the total number of series-compositions in S. Proof. Let 5" = Si â€”> S2 â€”>... â€”> Sb+i- Note that (2.23) satisfies condition (i) of T h e o r e m (n â€” b â€” l)-dimensional. 2.14, and therefore FJV is at most This further implies, by the Face-Lifting T h e o r e m , that Fs = {C G P{S) : p * C(S) â€” g{S)} is at most (s â€” b â€” l)-dimensional. To show that Fs is exactly (s â€” 6 â€” l)-dimensional, we construct s â€” b affinely independent schedules in Fs as follows. By L e m m a 2.10, there exist sjt = \Sk\ affinely independent permutation schedules Ci,h = 1,s k , in T(S ), for k = k 1 , 2 , 6 + 1 . Chapter 2. Single Machine Scheduling: Polyhedral Structure 27 Let s = "lo = 0, ZQ = 1, and s = \S\ = X)Â£ti fc- Recursively define m* = p(Sk) + 5 0 "ijt-i, zjb = Zk-i + Sk-i â€” 1, for k = 1 , 6 + 1 . Define s â€” 6 schedules C> G T(S) as follows: For j = 1 , 2 , s â€” b, k = 1,2,6 + 1, let s k Zk + m -i, if z < j < z + s ; k k 7^+mfc-x, It is easy to verify that C G k fc otherwise. D Fs. Moreover, all C â€” C , j' = 2 , 3 , s â€” 6 are J J 1 linearly independent. This implies that all C s are affinely independent, and therefore J Fs is (s â€” 6 â€” l)-dimensional. Since S is initial, by the Face-Lifting T h e o r e m , FN is (n â€” 6 â€” l)-dimensional. â€¢ We now turn to the dimension of the face induced by a zero-sum inequality. T h e o r e m 2.16 Let X) tvid > w (2.24) 0 be a zero-sum tight valid inequality for P(N). Let S be the smallest intermediate set containing S = {i G N : to,- ^ 0}. Assume that (i) there exists no proper initial set SQ of S such that w(So) â€” 0; (ii) S â€” Si â€”* S2 â€” * ) ' " ) * Sb+i, where 0 < 6 < n â€” 1 is the total number of , â€” series-compositions in S. Then F N = {CE P{N) : w * C{S) = wo} is at most d-dimensional, where d = min{n â€” l,n â€” 6}. Proof. By condition (i), L e m m a 2.13 implies that VC G T(N) flFjv, Cs â€” tls, for some t > 0, is a permutation schedule in T(S), and therefore C is tight for series-inequalities (2.4) induced by the 6 pairs of sets, (Si â€”* S2), (S2 â€”*â€¢ S3), (Sb â€”> Sb+i)- Moreover, it Chapter 2. Single Machine Scheduling: Polyhedral Structure 28 can be easily verified that A (defined the same as in T h e o r e m 2.14) is of rank at least E max{l, 6} (cf. T h e o r e m 2.14.). It follows that FN is at most ^-dimensional. â€¢ The following theorem yields the dimension of the face induced by a series-inequality (2.4). T h e o r e m 2.17 For any Si,S such that Si â€”* S 2 and S = Sil) S 2 2 is an intermediate set of N, F(Si, S ) = 2 -(p(S )) 2 P * C(Si) + (p(Si)) * C(S ) P -piSMSJ 2 - p(Si)g(S ) + (S )p (Si) 2 P 2 2 is a (n â€” b)-dimensional face-inducing inequality for P(N), > 0 (2.25) and b < n â€” 1 is the total number of the series-compositions in S. Proof. Let s = \S\. Note that (2.25) satisfies condition (i) of T h e o r e m 2.16, and therefore FN is at most (n â€”fe)-dimensional,since b > 1. This further implies, by the Face-Lifting T h e o r e m , that F s = {C E P{S) : F(S U S ) = 0} is at most (s - 6)-dimensional. To show that F 2 s is exactly (s â€” 6)-dimensional, we construct s â€” b + 1 affinely independent schedules in Fs as follows. Construct s â€” b affinely independent feasible permutation schedules C G T(S), j = 3 l,...,s â€” b in the same way as we do in T h e o r e m 2.15 and let C'- b+1 Observe that C J = C + 1 l. s G T(S) D Fs, j = 1, ...,s â€” 6 + 1, and we show below that they are affinely independent. For any v G R"~ b+1 such that Â£ j = i s-b+l P* E + 1 Vj = 0 and Ej=i + 1 jC v j = Â°s, we have s-b+1 VjCi = E WW + v*-b+iP(S) = o Chapter 2. Single Machine Scheduling: Polyhedral Structure 29 implying u -6+i = 0, where p* G R" is the processing time vector for job set S. Moreover, s since C ,j = l,...,s â€” 6, are affinely independent, we have Vj = 0,j = l,...,s â€” b, 3 which implies that C ,j â€” 1 , s â€” 6 + 1, are affinely independent. Therefore Fs is J (s â€” 6)-dimensional. Since S is intermediate, by the Face-Lifting T h e o r e m , Ffi is (n â€” fe)-dimensional. T h e o r e m 2.18 below is one of the main results of this chapter. â€¢ It implies that all facet-inducing inequalities other than parallel inequalities (2.3) must be zero-sum inequalities. T h e o r e m 2.18 Let Â£ jeN v>jCj > w (2.26) 0 be a valid inequality of P{N), and S = {i G N : Wi ^ 0} be its support. Then this inequality is positive-sum facet-inducing for P(N), if and only if (i) S is an initial set of N; (ii) S is not series-decomposable; and (iii) (2.26) is a positive multiple of (2.3). Proof. Sufficiency trivially follows from T h e o r e m 2.15. Necessity: Let So be the smallest initial set with W(SQ) = w(S). Since (2.26) is facet-inducing, there exist n affinely independent schedules CÂ° G T(N), j = 1 , n , tight for (2.26). By L e m m a 2.13, V j , C 3 So G T(So) is a permutation schedule. Thus, C ,j = l , . . . , n , are tight for the valid inequality p * C(So) > g(S ). Hence, by 3 0 Corollary 2.5, both (i), i.e., S = S, and (iii) follow. Moreover, by Proposition 2.4, we 0 have s = \S\ affinely independent feasible permutation schedules in {C : j = 1, ...,n}, 3 which, by L e m m a 2.10, implies (ii). The proof is complete. S â€¢ 30 Chapter 2. Single Machine ScheduHng: Polyhedral Structure T h e o r e m 2.19 below characterizes which series-inequalities are facet-inducing for P(N). T h e o r e m 2.19 Let Â£ be a valid inequality for P(N). {ieN: wC > w k k (2.27) 0 Let S be the smallest intermediate set containing S = Wi^O}. Assume S = (SiS ). 2 Then, (2.27) is zero-sum facet-inducing for P(N) if and only if (i) S is an intermediate set of N, i.e., S = S ; (ii) neither S\ nor S is itself series-decomposable; and 2 (iii) (2.27) is a positive multiple of (2.4)Proof. Sufficiency trivially follows from T h e o r e m 2.17. Necessity Since (2.27) is facet-inducing, we have n affinely independent schedules C EF j N = {Ce P(N) : w * C(S) = wo}, j = 1 , n . L e m m a 2.13 implies that V j , C - tjls 6 T(S), for some tj > 0, are permutation 3 S schedules, therefore all C s are tight for the series-inequality defined by (Si â€”> S ). By 3 2 Corollary 2.5, (i) and (iii) follow. We show (ii) holds by contradiction. Suppose (ii) does not hold. Then, b > 2. Further, Using (i) ,(iii), and T h e o r e m 2.17, we derive a contradiction: dim(Fjv) = n â€” b < n â€” 1. The proof is complete. â€¢ Thus, T h e o r e m 2.18 characterizes all positive facet-inducing inequalities for P(N) and T h e o r e m 2.19 characterizes one class of zero-sum facet-inducing inequalities â€” the series-inequalities. The following theorem characterizes another class of zero-sum facet-inducing inequalities â€” the Z-inequalities. Chapter 2. Single Machine Scheduling: Polyhedral Structure 31 Assume that N is Z-inducing. Let S, S[, S' ,S', S", and Q be defined as in Section 2 3, just before Proposition 2.8. Theorem 2.20 Inequalities (2.7) and (2.8) are facet-inducing for P(N) if and only if S is an intermediate set of N. Proof. If either (2.7) or (2.8) is facet-inducing, then by Lemma 2.13, any feasible schedule in T(N) tight for either inequality has the jobs in S processed consecutively without inserted idle times. This implies that S is intermediate. Conversely, since (2.7) and (2.8) are valid for P(N) by Proposition 2.8, it suffices to construct n affinely independent feasible schedules tight for (2.7) and (2.8). Let s = \S\, q = \Q\. Let C â‚¬ T(S) be a feasible permutation schedule with sequence (1,3, 1 2,4). For j = 2,...,q + 2, let C be the permutation schedule with job 1 in the jth-position 3 and the rest of the jobs in the same sequence as in C . Further, let C 1 q+3 permutation schedule with sequence (3,4,1, Q, 2), and C = C s q+A = C + I5. Since C â€” C , j = 2 , s , are linearly independent, schedules C 3 1 independent. Next, we can check that C q+3 be the feasible 1 1 , C , are affinely is tight for all inequalities (2.11), (2.12), (2.13) and (2.14), and all other schedules are tight for (2.9) and (2.10). Therefore, these schedules are tight for (2.7). Finally, since S is intermediate, we can use the Face-lifting Theorem to lift these schedules and construct n affinely independent schedules in T(N) tight for (2.7). The construction of the tight schedules for (2.8) is similar. The proof is complete. â€¢ From Propositions 2.7, 2.8, and Theorems 2.15, 2.17 and 2.20, we have the following corollary. Corollary 2.21 and (1) Parallel inequality (2.3) is face-inducing if and only if S is initial; Chapter 2. Single Machine Scheduling: Polyhedral Structure 32 (2) Zero-sum valid inequalities (2-4), (2.7) and (2.8) are face-inducing if and only if S is intermediate. 2.5 Facet L i f t i n g In this section, we show that, when a job set S results from series or parallel composition of two subsets Si and S'2, all facets of P(S) can be derived. Some facets of P(S) are in fact obtained by lifting the facets of P(S\) or P(S ). These results further lead to a , 2 minimal linear system sufficient for scheduling polyhedra when the precedence constraints are series-parallel. L e m m a 2.22 (Facet-Lowering L e m m a ) Let E mC > w k (2.28) 0 be a facet-inducing inequality for P(S) and let So Q S and So 3 {i â‚¬ N : Wi ^ 0}. Then w * C(So) > Wo is a facet-inducing inequality for P(So), if So is (i) an initial set of S with w(S) > 0; or (ii) an intermediate set of S with w(S) = 0. Proof. Either (i) or (ii) implies that for any C â‚¬ T(So), there exists C G T(S) such that C - tl So W * C(S ) 0 So = C, for some t > 0 (Note, t = 0 if w(S) = w* C{S ) 0 > 0). Thus, V C â‚¬ T(S ), > w . Therefore, (2.28) is also valid for 0 0 P(S ). Further, by 0 Proposition 2.4, we have |So| affinely independent schedules in {C So : j = l,...,s}, tight for w * C(SQ) > WQ, where C ,j â€” 1 , s are s affinely independent schedules in 3 T(S), tight for (2.28). The proof is complete. â€¢ Set S is said to be the parallel composition of S\ and S'2, denoted by S = (5*11152), if S = Si U S2 and neither i â€”â€¢ j nor j â€”> i for all i Â£ Si and j G S'2. The following theorem characterizes all facets resulting from parallel composition. Chapter 2. Single Machine Scheduling: Polyhedral Structure 33 T h e o r e m 2.23 The facet-inducing inequalities for P(S), where S = (S1WS2), are precisely the following: (i) all facet-inducing inequalities for P(Si), (ii) all facet-inducing inequalities for P(S2), and (iii) all parallel inequalities p* C ( / i U J ) > g(Ii U I2), 2 where Ii and I2 are any nonempty initial sets of S\ and S2, respectively. Proof. Since S\,S2, and iiU/2 are initial set of 5, any of (i), (ii) ( by the Face-Lifting T h e o r e m ) , and (iii) (by T h e o r e m 2.18) is sufficient to define a facet of P(S). Conversely, let ^w C >w k kes k (2.29) 0 be facet-inducing for P(S) and S = {i E Â£ : Wi / 0}. If S C Si (resp., S C S2), by the Facet-Lowering L e m m a , (2.29) has representation (i) ( resp., (ii)). If both S fl Si and S D S2 are nonempty, we claim that w(S) > 0 since otherwise w(S) = 0 implies, by L e m m a 2.12, that w(Si) < 0 for some i E {1,2}, and (2.29) is not valid since Si is a terminal set of S. Since (5.2.1) is positive facet-inducing, by T h e o r e m 2.18, S is an initial set of S. By Letting I = S fl Si and I = S ("1 5 , (2.29) x 2 2 has representation (iii). The proof is complete. â€¢ The following theorem characterizes all facets resulting from series composition. T h e o r e m 2.24 The facet-inducing inequalities for P{S), where S = (Si â€” > Â£2), are precisely the following: (i) all facet-inducing inequalities for P(Si), (ii) all zero-sum facet-inducing inequalities for P(S2), and Chapter 2. Single Machine Scheduling: Polyhedral Structure 34 (iii) -(p(I))p*C(T)-r(p(T))p*C(I) > (I)g(T) + (T)g(I) - p(I) (T), P 2 P P (2.30) where I and T satisfy the following two conditions: (a) T is a terminal set of Si and I is an initial set of S2; and (b) neither T nor I is itself series-decomposable. Proof First, we need to show any of (i), (ii) and (iii) is sufficient to define a facet of P(S). (1) Since Si is an initial (therefore, intermediate) set of S, by the Face-Lifting T h e o r e m , any facet of P(Si) induces a facet of P(S). (2) Since S is an intermediate set of S, by the Face-Lifting T h e o r e m , any zero-sum 2 facet of P(S ) induces a zero-sum facet of P(S). 2 (3) By T h e o r e m 2.19, the given conditions imply that (2.30) induces a zero-sum facet for P(S). Conversely, let J2 kC >w , kes w k 0 Cei? , 5 (2.31) be facet-inducing for P(S) and let S = {i â‚¬ 5" : Wi ^ 0}. We need to consider only two cases: (I) If (2.31) is a positive-sum facet, then by T h e o r e m 2.18, S is an initial set of 5* and is not series-decomposable which also implies S Q Si. Further, by the Facet-Lowering L e m m a , (2.31) has representation (i). (II) If (2.31) is a zero-sum facet of P(S), then we need to consider the following two cases: (1) neither S H Si nor S D S'2 is empty. Chapter 2. Single Machine Scheduling: Polyhedral Structure 35 Since S = (Si -Â»â€¢ S ), we have S f) S\ â€”â€¢ S fl S . By T h e o r e m 2.19, (2.31) has 2 2 representation (iii) with T = S D Si and I = S C\ S . 2 (2) one of SnSi and S (~)S is empty. Observe that both Si and S are intermediate 2 2 set of S, by the Facet-Lowering L e m m a , (2.31) has one of the representations (i) and (ii). The proof is complete. â€¢ As a straightforward consequence of T h e o r e m 2.23 and T h e o r e m 2.24, we have the following. C o r o l l a r y 2.25 The following is the unique (up to positive multiples) minimal linear system sufficient to define P(N) with series-parallel precedence constraints: (i) p * C(S) > g(S), for all non-series-decomposable initial set S of N; and (ii) -( (S ))p P * C(Si) + (p(Si))p * C(S ) 2 2 >p(S )g(Si)+ (Si)g(S )-p(S ) (Si), 2 P 2 2 2 P for all non-series-decomposable sets Si and S such that S = Si â€”â€¢ S is an intermediate 2 2 set of N. Given a scheduling polyhedron P(N) subject to series-parallel precedence constraints, Corollary 2.25 gives a complete characterization of all facets of P(N). These facets can be generated by repeatedly applying the rules stated in T h e o r e m 2.23 and T h e o r e m 2.24, starting from the leaves (singleton subsets of N) and following the compositions specified by any series-parallel decomposition tree of N (see Lawler [34], for details on the series-parallel decomposition trees). If the precedence relations on the job set are not series-parallel, the facet-inducing inequalities of the scheduling polyhedron P(N) are not all of parallel or series inequalities, as shown by the following theorem. Chapter 2. Single Machine Scheduhng: Polyhedral Structure 36 T h e o r e m 2.26 All facet-inducing inequalities for P(N) are in the form of either (2.3) or (2-4) if and only if G(N) is series-parallel. Proof. Sufficiency follows from Corollary 2.25. Necessity: If G(N) is not series-parallel, it is well known that N is Z-inducing (see Lawler [34]). Let S C N be a minimal intermediate Z-inducing set. Renumber the jobs such that S = { 1 , 2 , 3 , k } , {(ij) â‚¬ A(N) : WiJ e {1,2,3,4}} = {(1,2), (3,2), (3,4)}, and Q = { 5 , k } . Note that Q may be empty.. Since S is a minimal intermediate Z-inducing set, {1,2}, {3,4} and {3,2} U Q are intermediate sets of N. Moreover, for all j G Q, we have (3, j) 6 A(N) and (j, 2) â‚¬ A(N). By T h e o r e m 2.20, Z-inequality (2.7) or (2.8) induced by S is a facet-inducing inequality for P(N). The proof is complete. â€¢ Note that, for series-parallel precedence constraints, facets are uniquely defined by the index set of their nonzero coefficients. However, Theorems 2.20 and 2.26 show that this is never the case when the precedence constraints are not series-parallel. 2.6 Proofs of the four l e m m a t a P r o o f of L e m m a 2.9. Let S = {i : w ^ 0}. and F = {C e P(N) : w * C(S) = w }. t 0 First, F is an (n â€” b â€” l)-dimensional face of P(N) if and only if there are precisely ra â€” b affinely independent points C â‚¬ F, k = 1 , 2 , n â€” b. Let C â‚¬ T(N),j k j =1 , 2 , m be a minimal collection of affinely independent feasible schedules such that each C can k be represented by a positive convex combination of C s. Then, we have Vfc, 3 W = W* 0 C {S) k =J2 hYs kj h hes V j=i C 12 771 nt W = i=i kJ V W * () CJ S > ">(>, Chapter 2. Single Machine ScheduHng: Polyhedral Structure 37 where v j > 0, Vj, and Y^jLi kj = 1? which implies that C G F, j = v k 3 1,m. Thus, C s also span the linear hull of F. Hence, dim(F) = n â€” b â€” 1 if and only if 3 there are precisely n â€” b affinely independent schedules in F. The proof is complete. P r o o f of L e m m a 2.10. â€¢ Let s = \S\. Sufficiency. Suppose S is series-decomposable, i.e. S = Si â€”* S . 2 Let C â‚¬ R , j = 1 , / , 3 s schedules in T(S). be a maximal collection of affinely independent permutation Clearly, all C s are tight for both (2.3) and series-inequality (2.4), 3 whose coefficients are linearly independent. It follows that I < s + \ â€” 2 = s â€” 1. Necessity. Suppose S is not series-decomposable. By induction on \S\. For IS"! = 1, the necessity trivially holds. Suppose it holds for all 151 < s-l. Let S' = S \ {i}, where {i} is a terminal set in S. We have two cases: (1) S' itself is not series-decomposable. Then, by the induction hypothesis, there are 5 â€” 1 affinely independent permutation schedules in T(S'), namely, C ,j 3 = 1, â€” 1. Observe that there exists some terminal set {fc} of S' such that job fc can be sequenced after job i, since otherwise S = (S' â€”> {i}). Define for all j = 1 , s â€” 1, and let C be the permutation schedule in T(S) such that jobfcis sequenced last and the rest of the jobs are sequenced the same order as in C . We easily 1 verify that C 1 , C s are affinely independent permutation schedules in T(S). (2) S' is series-decomposable, i.e., S' = (Si â€”* Â£2). First, observe that Si U {i} is not series-decomposable, since otherwise S i U {i} = (S" â€”> S'") with S'" containing terminal job i, and thus, S = S" â€”> (S'" U S2), a contradiction. Therefore, by the induction hypothesis, there are |Si| + 1 affinely independent Chapter 2. Single Machine Scheduling: Polyhedral Structure 38 permutation schedules in T(ft U {i}), namely, C ^y, j = 1 , | f t | + 1. 3 SiU Let Cs Â£ ^(ft) be any permutation schedule and define 2 i C = f (CkuoyU if h e ft U UCftJfc+pCftuO}), if/* {i}; eft, for; = l,...,|ft| + l . Let 7r be the permutation induced by C . 1 For |ft| + 2 < j < s, let C- be a permutation schedule with job i sequenced at the 7 7r(j)-th position and the rest of the jobs are sequenced in the same order as in C . 1 Observe that no job k G ft has precedence over job i, since otherwise S = ft â€”Â» (ft U {i}), a contradiction. schedules in T(S). C- , j = 1 , 2 , s 7 Therefore, all C , j â€” l,...,s, are feasible permutation 3 Moreover, since C â€” C , j = 2,3,...,3, are linearly independent, 3 1 are affinely independent. In either case, we can construct s affinely independent permutation schedules in T(S). The proof is complete. P r o o f of L e m m a â€¢ 2.12. (1) Since (2.20) is facet-inducing, there are n affinely independent schedules, C E 3 ^(JV"), j = 1 , n , satisfying: Â£ w C{ = k w. 0 (2) We claim that w kC{ = Vj = V, kÂ£S for all j = 1 , n , and prove it by contradiction. Suppose not. Then, there exist some h,l such that Vh > v\. Let . C l _ ( {C' )i, ~ I (Ch\ )i + Â«, s s if i e ft Xiâ‚¬N\S. Chapter 2. Single Machine Scheduling: Polyhedral Structure 39 Since S is an initial set of N, C â‚¬ T(N) for u sufficiently large. Moreover, Â£ keN kCk = vi + w - v < w , w 0 h 0 which contradicts the fact that ( 2.20) is a valid inequality for P(N). From (1), (2), and Corollary 2.5, it follows that wo = v and w = 0 for all k Â£ N\S. k The proof is complete. P r o o f of L e m m a 2.13 â€¢ Let X be any initial set of N and X = N \ X such that X n S ^ 0 and X fl S ^ 0. Observe that X is a terminal set of N, we have w(X) > 0 since otherwise (2.21) is not valid. Using condition (i), it is trivial that w(X) > 0. Using condition (ii), we cannot have w(X) = 0 since otherwise we have w(X) = w(N) and by L e m m a 2.12, = 0, Vi Â£ X. This further implies 3k Â£ S, w = 0, a contradiction. k Therefore, we have w(X) > 0 in either case. Next, by contradiction, suppose 3C Â£ T(N) tight for (2.21) such that CQ â€” HQ, for any t > 0, is not a permutation schedule in T(Q). Then, C represents a feasible schedule such that either there exists some idle time between the completion times of some jobs in Q, or jobs in Q are not sequenced consecutively. Let I(Q) be the smallest initial set containing Q. Let TT be a permutation induced by C. For w(N) > 0, we note that (a) I(Q) = Q, by definition of Q and I(Q); (b) CÂ» i) = ( since otherwise C = C - {C ) -PT(I))^N Â£ T(N), but w * C(N) = n(X wo â€” w(N) < WQ, a contradiction. Hence, there is no idle time before C^i) for w(N) > 0. Define 6(x) = f 1, [0, ifx>0; iix<0. By Proposition 2.3, Q is a terminal set of I(Q). Let M = max{Cjt : k â‚¬ I(Q)} and c Chapter 2. Single Machine ScheduHng: Polyhedral Structure 40 define a schedule C as follows: Ci, iiiÂ£l(Q)\Q; Ci =<Ci + M (l - S(w(N))), iiieQ; c .C,- + 2M , if C ieN\I(Q). Observe that C â‚¬ T(N) and is also tight for (2.21) but has some idle time inserted between the completion times of some jobs in Q. (Note: For w(N) > 0, none of the completion times of jobs in Q change, i.e., CQ = CQ. Nevertheless, if CQ contains any idle time, so does CQ; else some other job is sequenced between jobs in Q and thus, by definition, CQ contains idle time). Since Q is the smallest (intermediate if w(N) = 0; or initial if w(N) > 0) set containing S, there exists an idle time interval (t, t + u), for some t, u > 0 (for w(N) > 0, cf. Note (b) above), such that some jobs in S are processed before t and some jobs in S are processed after t + u. Let X = {Â» e N :Ci <t} X = {i G JV : Â£ , â€¢ > * + u}. Clearly, N = X U X and both S fl X and S D X are nonempty. â€” A Define C = C â€” u Y,izx Â»'e It is clear that C Â£ T(N). Since we have before w(X) > 0, Â£ Wid = w â€” w(X)u < 0 Wo, a contradiction. This completes the proof for the lemma. â€¢ Chapter 3 Single Machine Scheduling: Polyhedral Computations This chapter presents a cutting plane procedure, using facet cuts derived in Chapter 2. In addition, extensive computational results as well as their analysis are provided. 3.1 Introduction For the last thirty-five years, since the work of Smith [54], the single machine scheduling problem has been one of the challenging research topics in combinatorial optimization. The problem with general precedence constraints was shown to be strongly NP-hard by Lawler [33] and Lenstra and Rinnooy Kan [37]. For the series-parallel precedence constraints, an elegant O(nlogn) algorithm was derived by Lawler [33]. A discussion of the algorithms (up to 1985) for the problem with general constraints can be found in Potts [50]. Very tight formulations with 0(n ) 2 binary variables and 0(n ) 3 constraints are studied by Wolsey [57]. A new Lagrangian-based lower bounding method with 0(n) continuous variables (and one Lagrangian multiplier per nonredundant precedence constraint) is introduced in Van de Velde [56]. In spite of these research efforts, one is still unable to solve even medium-sized problems. The reported largest solved problem instances involve no more than 100 jobs, see Potts [50], where Branch-and-Bound methods were used for obtaining optimal solutions. The reason why the methods do not apply to the larger problems may be a combination of (1) the number 0(n ) of binary variables in the integer programming formulations, and 2 (2) weak lower bounds. To a large extent, the present polyhedral approach overcomes 41 Chapter 3. Single Machine Scheduling: Polyhedral Computations 42 both difficulties. In this chapter, a linear programming based cutting plane algorithm is developed for the scheduling problem. The proposed algorithm works on a compact linear formulation with only n variables, one per job. Two families of facet-defining inequalities, the parallel inequalities and the so-called simple series inequalities, are used in the cutting plane procedure. Extensive computational experiments are conducted on an IDM 386/25 Personal Computer with a sample of 280 problems of sizes 30 to 160 jobs. The average computation time for the 160-job problems is less than 20 minutes. The results also show that the percent gap in objective function value between the feasible solution derived from the cutting plane algorithm and the linear programming lower bound is less than 0.25 percent on the average, and less than 1 percent in the empirical worst case. A detailed computational report can be found in Section 3.4. 3.2 A cutting plane procedure The proposed cutting plane algorithm consists of three stages. It begins by solving an initial linear programming (LP) problem. This initial LP formulation defines a polyhedron containing the set of feasible schedules. The second stage is an iterative process: at each iteration, it generates (1) an optimal solution to the current LP relaxation, which serves as a lower bound (LB) ; (2) possibly a valid inequality or a cut, violated by the LP solution; (3) a heuristic schedule which serves as an upper bound (UB). The cuts are successively added to the LP formulation. This process shrinks the feasible region and yields increasingly tighter bounds on the value of the optimal schedules. The iteration terminates when either the current UB equals LB, (hence the corresponding schedule is optimal) or when the LP solution cannot be cut off by any other available cuts. At the third stage, a heuristic is applied to the incumbent schedule for possible improvement Chapter 3. Single Machine ScheduHng: Polyhedral Computations 43 (if it is not proven optimal), and then a final solution report is produced. For a general discussion on cutting plane methods, the reader is referred to the text by Nemhauser and Wolsey [45]. 3.2.1 Initial F o r m u l a t i o n The proper choice of an initial formulation is important in cutting plane algorithms. We first include all the following simple facets (3.1) and (3.2): st. Cj > pj, all {j} initial (3-1) Cj â€” Ci > pj, all nonredundant (3-2) The inclusion of all these facets ensures that the LP solutions obtained from stage 2 induce feasible sequences. Computational experiments have shown that this initial formulation is satisfactory in most cases, except for problem instances with very few precedence relations. From our computational experience, we found that, when only a few precedence constraints are present, the initial formulation yields very weak bounds. As a result, too many cuts, and thus excessive computation time, are needed to reduce the gap between UB and LB. To speed up the computation for these sparsely precedence-constrained problems, we extend the initial formulation by including an additional set of cuts (most of them known to be facet-defining). The set of cuts consists of n â€” 1 parallel inequalities obtained as follows. We first use a heuristic method to find a reasonably good feasible sequence, say, (7r(l),7r(2),...,7r(n)), see Section 3.2.3 for details. Let Si = {7r(l),TT(2), i = 2,3,n. 7r(i)}, Note that these sets Si necessarily induce initial sets. Then, we add to the original initial formulation the following parallel inequalities: P*C(Si)>g(Si), i = \,2,...,n. Chapter 3. Single Machine Scheduling: Polyhedral Computations 44 Recall from Chapter 2 that the inequality induced by set Si is facet-defining, unless the set Si is series-decomposable. The computational experience confirms the effectiveness of this method for sparse precedence constraints. 3.2.2 C u t t i n g Planes and Separation A l g o r i t h m s Two types of cuts are used in the separation routine: parallel cuts and simple series cuts. Recall that the parallel cuts take on the following form: p * C(S) > g(S), where S is a nonempty initial set. (3.3) Queyranne [52] proposed an 0(n logra)separation procedure for the scheduling problem with no precedence constraints. Note that the procedure is still valid for the precedence constrained scheduling problems: the LP solution at each iteration necessarily induces a feasible sequence, because of the inclusion of all non-redundant precedence constraints in the initial formulation. Thus, any set S = {TT(1), â€¢ â€¢ â€¢, 7r(i)} identified by the algorithm below is necessarily an initial set. Parallel C u t Separation: INPUT: Integerra;processing time vector p; completion time vector C. RESULT: a subset S Q {1,..., n} maximizing the violation T(S) = g(S) - p * C(S) of (3.3). begin 1. 2. 3. Sort JV = {1,...,ra} as JV = (TT(1), . . . , 7r(ra)) in nondecreasing order of the Cj coefficients; Let S' := 0; p := 0; 7 ' := 0; 7 := 0; S := 0; For i :â€” 1 torado begin k : = TT(0; S' := S' U {k}; p := p + p \ i := i + Pk(p - C ); if 7 ' > 7 then begin 7 : = 7 ' ; S := S' end end k k end. Note that in steps 2 and 3, p = P(S') and 7 ' = T(S'). Note also that except for Chapter 3. Single Machine Scheduling: Polyhedral Computations 45 the 0(nlog(n)) sort in Step 1, the algorithm runs in linear time. See Queyranne [52] for details. We now relate the lower bound obtained after adding all (relevant) parallel cuts, to the lower bound obtained by Van de Velde [56]. We may write the precedence constrained scheduling problem as follows. Z opt = min st. (3.4) EieJV^jC'i Cj â€” Ci > pj, all nonredundant (3-5) (3.6) CeQ where Q is the set of all feasible schedules. Let B be the arc-node incidence matrix of G = (N,A(N)). Consider the following linear program: LB P = min wC st. (3.7) BC>b (3.8) P * C(S) > g(S), anSCN (3.9) where b is an appropriate right-hand-side, so (3.8) is just (3.5) written in matrix form. As (3.9) is a relaxation of (3.6) (cf. Queyranne [52]), problem (3.7)- (3.9) is a relaxation of problem (3.4)- (3.6). So LBp < Z . opt In effect, LBp is precisely the lower bound obtained by the above cutting plane method after all parallel cuts are exhausted. Van de Velde's lower bound is obtained by relaxing precedence constraints (3.5) with Lagrangian multipliers A,j > 0. For any vector A > 0 of such Lagrangian multipliers, the subproblem in this approach is the following unconstrained scheduling problem min{u;C + X(b - BC) : C G Q} = mm{{w - \B)C : C G Q) - \b, (3.10) which is solved by Smith's rule in 0(n log n) computational steps [54]. The best possible lower bound LBR, which can be obtained using this approach, is the optimum value of Chapter 3. Single Machine Scheduling: Polyhedral Computations 46 the following problem: LB R = max{min{wC + \(b - BC) : C e Q}} (3.11) = max{min{u>C' + \(b - BC) : C â‚¬ conv Q}} (3.12) = max{min{u>C + X(b - BC) : p * C(S) > g(S),VS C JV}} (3.13) = mm{wC : BC > b,p* C(S) > g{S),VS C N} (3.14) where (3.12) follows since the objective function in (3.11) is linear in C; (3.13) follows from Queyranne [52]; (3.14) follows from the Geoffrion's theory of Lagrangian Relaxation [24]. Thus, we have shown the following result: T h e o r e m 3.1 The optimal lower bound in Van de Velde's Lagrangian Relaxation approach is equal to the lower bound LBp obtained by the cutting plane approach using only the parallel cuts. Note that Van de Velde does not solve (3.11) exactly, but only approximately using an ascent method for improving the Lagrangian multipliers. Therefore, his lower bound is generally weaker than LBp. The second type of cuts is a subclass of series cuts, the simple series cuts, where one of the subsets, Si or S in Si â€”> ft, is a singleton. So, simple series cuts are of the form 2 - p{S )C 2 u + p * C(S ) > g(S ), 2 2 where {u} -> S , 2 (3.15) or -p* C(Si) + (Si)C P v > sftSi U {v}), where Si {v}. (3.16) For simplicity, we denote the simple series inequalities by T(Si, S ) < 0, where Si (resp., 2 S ) is singleton if it is the cut (3.15) (resp., (3.16).), and r(Si,S ) denotes the amount 2 by which the cut is violated. 2 47 Chapter 3. Single Machine Scheduling: Polyhedral Computations We now develop an 0(n ) separation procedure for the series cuts. To do so, we 2 rewrite the above inequalities in the following equivalent forms: for (3.15), Â£ (Cj - C ) > </(ft), Pj jes u where {u} - ft, (3.17) 2 and, for (3.16), Â£ where Piitv - ti) > 9(Si), where ft -> {u}. (3.18) = C,- â€” pi is the sÂ£ art time of job i E N, Inequality (3.17) can be viewed as a parallel inequality with respect to redefined "completion times" Cj â€” C and restricted to those jobs j that are successors of given u job u. For inequality (3.18), one may imagine that all jobs in ft start backward from time t , and thus have "completion times" t â€” t,-. Therefore, it is also in the form of a v v parallel cut, restricted to the set of jobs that are predecessors of job v. For convenience, we call {u} â€”â€¢ ft a fan-out structure, and ft â€”â€¢ {v} a fan-in structure. A simple extension of the Parallel Cut Separation leads to a separation procedure for the simple series cuts. For every u â€” 7r(l), 7r(2), â€¢ â€¢ â€¢, 7r(n â€” 2), apply the Parallel Cut Separation to the set of jobs that are successors of u, using Cj â€” C as completion u times. This produces a fan-out structure that maximizes the violation of (3.17). A similar procedure applies to (3.18). In the end, a most violated simple series cut is identified. Thus, finding a most violated simple series inequality of either fan-in or fanout structure requires 0(n ) computational steps. This Simple Series Cut Separation 2 algorithm is described in details on the following page (Recall that A(N) denotes the transitive closure of A(N)). Chapter 3. Single Machine Scheduling: Polyhedral Computations Simple Series C u t Separation: INPUT: Integer n; processing time vector p; completion time vector C. RESULT: Find disjoint subsets Si and S , such that S\ â€” â€¢ 52, one of them is a singleton set, and T(5i, 52) is maximized. 2 begin 1. Sort the job set as N â€” (TT(1), . . . ,7r(n)) in nondecreasing order of the completion times CJ; and as N = (7r'(l),..., 7r'(n)) 2. in nonincreasing order of the start times tj; [ FORWARD SEARCH ] Let 5' := 0; p := 0; 7' := 0; := 0; 5 := 0; 7 l 2 3. F o r h := 1 to n - 2 do For j := h + 1 to n do if (7r(^),7r(j)) â‚¬ A(N) then begin i := n(h); k : = TT(J); 5' := 5' U {k}; p:= P + Pk; i := i + Pk{? ~C + Ci); if 7' > 71 then begin 71 := 7'; 52 := 5', u := i end end; k 4. [ BACKWARD SEARCH ] Let 5' := 0; p := 0; f := 0; 72 := 0; Si := 0; 5. F o r h := n step â€”1 to 2 do For j := h â€” 1 step â€”1 to 1 do if (*(j),K(h)) E A(N) then begin i := ir'(h); k := TT'(J); S' := S' U {k}; p:= p + p ; 7' == i + Pk{p ~ U + h); if 7' > 72 then begin 72 := 7'; Si := S', v := i end end k 6. Retrieve inequality r(Si, S2) < 0 from (3) if 71 > 72 and from (5) otherwise. end. Chapter 3. Single Machine Scheduling: Polyhedral Computations 3.2.3 49 Heuristics for the U p p e r B o u n d s Cutting plane algorithms often allow the easy derivation of good feasible solutions. This is the case for the precedence-constrained scheduling problem studied here. The following heuristic procedures are used in our algorithm. The first heuristic is a procedure for obtaining an initial feasible sequence. Recall that this initial sequence is used to establish a tighter LP formulation than the original one. The heuristic is constructive, starting with the whole job set S = N and the given precedence graph G. Then, repeat the following process until the set S is empty: remove from S an initial job i (relative to current graph G) with largest ratio itf,/p<; update S <â€” S \ {i} and G. The sequence in which the jobs have been removed is, by construction, a feasible sequence. This simple heuristic has proven to be effective when the precedence graph is sparse. In particular, it yields an optimal schedule when A(N) is empty (Smith [54]). There are other heuristics for obtaining feasible schedules, such as Morton and Dharan's Tree Optimal heuristic [39]. Sophisticated heuristics may not be very useful in our algorithm. We briefly tested the Tree Optimal heuristic solution against the feasible schedules induced by the LP solutions at stage 2 on several 100-job problem instances. We found that the cutting plane procedure consistently generated better feasible schedules, and generally used less CPU time, than the Tree Optimal heuristic. The second heuristic derives a feasible sequence from an LP solution by employing a so-called priority rule. At each iteration, that is, when a cut is added, an optimal solution C to the current LP relaxation is obtained. Since all precedence constraints are included in the initial LP formulation, the solution C necessarily induces a feasible sequence in which job i is processed before job j whenever C,- < Cj. We then try to improve the feasible sequence produced by the above heuristic. This Chapter 3. Single Machine Scheduling: Polyhedral Computations 50 involves 1-OPT type interchanges. First, we do a backward search: for i = n â€” 1, ...2,1, find a set S of jobs immediately following, but not constrained by, job i and with largest ratio w(S)/p(S); if the largest ratio w(S)/p(S) is larger than u>,/p,-, then update the sequence by interchanging i and S. We then perform a similar forward search, trying to exchange job j with a set of jobs immediately preceding it. We call this procedure OnePass 1-OPT. A Full 1-OPT is to repeat One-Pass 1-OPT until no further improvement can be made. 3.2.4 T h e C u t t i n g Plane Procedure The whole cutting plane procedure is summarized as follows. Step 0: Read data. Start the timing subroutine. Step 1: Compute the transitive reduction and transitive closure of the precedence digraph. (The former is used for setting up an initial formulation, and the latter for the simple series cut separation.) Step 2: Set up the initial LP formulation and solve this LP problem. Step 3: (a) Generate a heuristic feasible schedule from the current LP solution; store the schedule if its cost is the best found so far; go to Step 5 if UB=LB, where UB is the cost of the best schedule found so far, and LB is the cost of the current LP solution. (b) Apply the Parallel Cut Separation. Go to (d) if a violated parallel cut is found; (c) Apply the Simple Series Cut Separation. Go to Step 4 if no violated series cut is found; (d) Add the violated cut and reoptimize the extended LP to update the LP solution and its cost LB; Go to (a). Step 4: Apply the Full 1-OPT heuristic to the best feasible schedule for final improvement; Step 5: Stop the timing subroutine; Produce a solution report; Halt. Note that Step 3 is an iterative phase, the most time-consuming part of the algorithm. Chapter 3. Single Machine ScheduHng: Polyhedral Computations 51 The algorithm, written in FORTRAN, uses the XMP Linear Programming Library as the LP optimizer in Steps 2 and 3. To facilitate the use of the subroutines in XMP, an equivalent start time formulation is used. Since start times tj = Cj â€” pj, for all j, the formulation replaces all trivial constraints Cj > j by the nonnegativity constraints on P all tj variables. The solution report, however, is presented in terms of completion times for comparison with other solution methods. At the present, the algorithm is coded for problems of size up to 400 jobs. Extending the problem size requires changing only a few statements. 3.3 C o m p u t a t i o n a l Experience In this section, we report our computational results on a fairly large sample of randomly generated problems. We evaluate the algorithm based on the computation time, and the percent gap r = 100(UB â€” LB)/LB. For example, if a feasible schedule C with value UB satisfies r < 0.3, then it is guaranteed, even without knowing the optimal value Z , opt that the schedule cannot deviate from the optimal schedule by more than 0.3 percent, since (UB - ZÂ° )/Z pt opt < (UB - LB) I LB < 0.003. To illustrate how the cutting plane procedure works, we begin with two simple numerical examples. Chapter 3. Single Machine Scheduling: Polyhedral Computations E X A M P L E 1. 52 Consider Potts' 10-job example [50]. Job 1 2 3 4 5 6 7 8 9 6 9 1 3 9 5 7 7 6 2 5 9 6 5 4 9 3 8 i Pi Wi 10 2 5 Table 3.1: Data for the 10-job example The precedence relations can be represented by the following nonredundant arc set A(N) = {(1,6), (1,7), (2,4), (2,5), (3,8), (5,9), (6,10), (7,9), (8,10)}. After solving the initial LP program, which includes all constraints of types (3.1) and (3.2), an LP solution of value 1526 is obtained. In addition, the heuristic gives a feasible schedule of value 1530. Table 3.2 summarizes the execution of the algorithm, where i denotes the iteration index in Step 3, and the second column represents the cut type, "P" for a parallel cut and "SS" for a simple series cut. Cut type 1 1 2 P 3 SS 4 SS SS 5 6 SS i Violated facet cut 6C + 9C + C + 3C + 9C + 7C + 6C9 > 987 X 2 3 4 5 7 9C + C3+ 3Ct > 130 2 -6C1 - 9C 2 - 9C - 7C + 31C > 543 5 7 9 - 6 C 1 - 5C - 7C + I8C10 > 143 6 8 - 6 C 1 - 9C - 7C + 22C > 291 S 7 9 - 5 C - 7C + 12Cio > 59 6 8 LB UB 1526. 1530. 1526.7 1530. 1527.2 1530. 1527.5 1530. 1528.0 1530. 1530. 1530. % Gap 4. 3.3 2.8 2.5 2. 0. Table 3.2: Cutting planes and the corresponding solutions Observe that after adding two parallel cuts and four series cuts, the problem is solved to optimality without any branch and bound. Note also that Potts' lower bound, obtained after sixteen iterations, is 1516, weaker than our initial LP value 1526. Chapter 3. Single Machine Scheduling: Polyhedral Computations E X A M P L E 2. 53 Consider Wolsey's 30-job example [57]. Job i 1 16 2 17 3 18 4 19 5 20 6 21 7 22 8 23 9 24 10 25 11 26 12 27 13 28 14 29 15 30 Pi 57 4 45 44 50 89 73 74 82 43 51 9 94 43 98 56 15 27 52 45 78 68 75 63 9 3 6 1 3 6 7 5 8 7 7 7 8 2 9 5 6 1 8 5 7 2 19 32 4 82 2 Wi 76 80 1 5 9 3 2 5 5 Table 3.3: Data for the 30-job problem The nonredundant precedence relations can be represented by the following arc set. A(N) = { (1,2), ( 3,13), ( 6, 9), ( 8,11), (11,16), (13,17), (15,18), (18,23), (21,29), (24,30), ( 2, 6), ( 4, 7), ( 6,12), ( 9,18), (11,17), (13,19), (15,20), (19,20), (21,30), (25,28), ( 2, 7), ( 4, 9), ( 7, 8), ( 9,25), (12,17), (14,20), (17,18), (19,21), ( 3, 8), ( 5, 8), ( 7,10), (10,12), (12,25), (14,21), (17,22), (22,26), (19,28), (23,24), (26,28), (26,29), ( 3, 9), ( 5,19), ( 7,13), (11,15), (13,16), (14,23), (18,21), (21,27), (24,28), (26,30) } Table 3.4 gives a summary of the solution report for each iteration. The third column represents the cumulative computation time (IDM 386/25). Note that the initial lower bound (LB) is 56,495.18. After five parallel cuts were added, no additional violated parallel cut is found, and the current LB of 119,329.04 is the best possible lower bound LBR that can be obtained by Van de Velde's Lagrangian relaxation approach. The algorithm exhausted all parallel and simple series cuts at iteration 31, with a total of 6 parallel cuts and 25 series cuts. At this point, LB = 121,031.9 and UB = 121,757 with the percent gap below 0.6 percent. The cumulative computation time is 12.74 seconds. Chapter 3. Single Machine Scheduling: Polyhedral Computations Iter Cut type Cumul.time LB UB 123568 0 1 1.37 56495.1757 P 1.53 71642.9524 123568 2 P 3 4 P P 1.81 2.52 103696.0370 116799.2382 121799 121799 119231.7078 5 P 2.85 3.02 121799 121799 6 7 8 SS SS 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 ss ss ss ss SS ss p SS SS SS SS SS SS SS SS SS SS SS SS SS SS ss ss ss 3.35 119329.0365 119422.0401 121799 54 % Gap 118.72310 72.47754 17.45772 4.28065 2.15320 2.06988 1.99039 1.82842 3.68 3.95 4.28 119611.9931 119623.1333 121799 121799 119703.7625 121799 4.66 119867.9137 121799 1.61101 4.99 119959.1578 121799 1.53372 5.32 5.65 5.87 6.31 6.64 6.97 7.30 7.69 8.07 120062.2191 120364.2442 121799 121799 1.44657 1.19201 120425.5471 120638.8663 120674.8199 120811.7984 120848.5473 120881.8021 120904.6679 121799 121799 121799 121799 121799 121757 121757 1.14050 .96166 .93158 .81714 8.40 8.78 120914.2967 121757 121757 9.11 9.50 120932.7068 120941.9816 1.81893 1.75035 .78648 .72401 .70496 .69694 .68161 121757 .67389 120955.3635 121757 .66275 9.88 10.27 120981.0002 121001.3894 121757 121757 .64142 .62446 10.60 10.98 11.53 11.92 12.30 121017.5399 121757 121757 .61104 121026.4292 121031.6281 121031.7969 121031.8770 121757 121757 121757 .60365 .59932 .59918 .59912 Table 3.4: Solutions from the cutting plane procedure Chapter 3. Single Machine Scheduhng: Polyhedral Computations Job Schedule Schedule L P Solution (optimal) (at iter 31) (final) L P Solution (at iter 5) 1 57 57 57.0000 3 2 6 4 107 152 234 107 152 234 107.0000 234.1205 443.1205 57.0000 107.0000 382.1086 527.1086 310 310.1205 361.1205 382.1086 433.1086 413.1205 537.1205 485.1086 527.1086 7 310 361 13 10 12 413 507 522 361 413 599 614 552.1205 542.1086 5 595 486 434.1205 433.1086 8 11 614 712 505 712 453.1205 623.4538 452.1086 550.1086 16 17 22 716 760 769 716 760 769 627.4538 757.1067 766.1067 554.1086 594.1086 603.1086 26 9 25 14 825 907 950 1028 825 907 950 1028 659.1086 1092.1319 1135.1319 1181.1319 15 18 1103 1192 1103 1192 822.1067 963.5766 1006.5766 1041.5766 1116.5766 1205.5766 23 24 1224 1226 1224 1226 1237.5766 1239.5766 1213.1319 1215.1319 19 21 1306 1306 1349 1417 1462 1489 1260.1559 1323.5428 1391.5428 1365.8683 1489.0000 1181.1319 1224.1319 1292.1319 1260.1319 1489.0000 1552 1626 1552.0000 1626.0000 1552.0000 1626.0000 29 28 27 30 20 1349 1417 1462 1489 1552 1626 1092.1319 1181.1319 Table 3.5: The optimal schedule and the relevant solutions 55 Chapter 3. Single Machine Scheduling: Polyhedral Computations 56 At the final upper bound improvement stage, we first applied a Full 1-OPT but failed to improve the upper bound. Then we tried to interchange a 2-job subsequence and its adjacent subsequence (cf. Table 3.5, the interchange of subsequences 5,8 and 10,12), and obtained a feasible schedule with the objective value 121,559, and 113,214 with respect to start times. This has been shown to be optimal by Wolsey [57]. Relative to 121,559, the percent gaps of Van de Velde's lower bound and our lower bound are about 1.9% and 0.47%, respectively. The optimal schedule as well as relevant heuristic and LP solutions are given in Table 3.5. Note that the completion times for the first two jobs and the last three jobs in Table 3.5 are identical for all columns. This may suggest a possible decomposition method for further improving the algorithm. We now test the algorithm on a sample of randomly generated problems of size ra, ranging fromra= 30 to 160 jobs. For each job i, an integer job processing time p,- was obtained from the uniform distribution [1,100], and an integer weight W{ from the uniform distribution [1,10]. The precedence graph G was induced by specifying the probability P with which each arc (i,j) with i < j was included. For each n, we generated two problems for each of the P values .001, .02, .04, .06, .08, .10, .15, .20, .30 and .50. In total, this produces 280 test problems. Table 3.6 presents a summary of the computational results. For each ra, the second column (ACT) and the third column (MCT) provide respectively the average and maximum computation time, in seconds, over 20 problems. The fourth column (OPT) represents the number of problems (out of 20) which were solved to proven optimality (i.e., when LB = UB). In total, 47 out of 280 problems were provably solved to optimality. The fifth column (AGAP) gives the average percent gap. The sixth column (MGAP) gives the maximum percent gaps and the last column gives the value of P for the problem giving this value MGAP. Chapter 3. Single Machine Scheduling: Polyhedral Computations ACT 30 6.94 40 19.50 50 36.08 60 65.00 70 109.46 80 129.68 90 225.16 100 290.33 110 414.27 120 466.18 130 605.82 140 680.39 150 851.16 160 1137.32 n MCT # OPT 14.06 10 75.79 7 72.61 4 133.19 4 214.05 2 246.56 2 562.22 3 530.80 2 1614.70 3 1449.15 2 1888.78 2 1769.81 2 2074.26 2 3513.58 2 AGAP .16 .10 .11 .18 .20 .29 .23 .21 .21 .35 .19 .30 .30 .29 MGAP .95 .74 .62 .54 .61 .53 .95 .51 .88 .96 .49 .87 .67 .66 57 P .10 .30 .15 .15 .15 .10 .10 .20 .10 .06 .15 .08 .08 .15 Table 3.6: A summary of the results for 280 problems Table 3.7 gives a comparison of our computational results with those of Van de Velde (1990). For each value of P, Van de Velde tested his Lagrangian relaxation method on a sample of 45 problems (5 problems each for every n = 20,30, â€¢ â€¢ â€¢, 100). The resulting average percent gaps AGAP V are given in the second column of Table 3.7. We used a sample of 28 problems (2 problems each for every n = 30,40, â€¢ â€¢ â€¢, 160). The third and fourth columns represent the average percent gaps and the maximum percent gaps, respectively, obtained by our cutting plane procedure. Clearly, the cutting plane approach outperforms the Lagrangian approach for all P values in terms of the resulting percent gaps. (If Van de Velde's sample of problems was used, we expect even better results, because problems with n less than 60 tend to yield smaller gaps for our approach, see Table 3.6.) These results are due to: (a) a much tighter bound from the cutting plane procedure, see T h e o r e m 3.1; and (b) a more effective heuristic solution method. The last column provides the number of problems (out of 28) with the feasible solutions proven to be optimal. Chapter 3. Single Machine Scheduling: Polyhedral Computations p AGAP AGAP MGAP # OPT .001 0.007 0 0 28 .02 .04 0.069 0.035 0.467 0.098 0.248 0.329 0.408 0.409 0.303 0.347 0.962 0.872 0.952 0.794 9 4 2 1 .15 .20 0.248 0.675 1.076 1.518 2.024 2.113 0.860 0 0 1 .30 .50 3.733 4.116 0.263 0.154 0.756 0.359 0 2 .06 .08 .10 V 58 Table 3.7: Computational results with respect to P values Potts [50] observed that problems with P between .04 to .1 are more difficult for his approach. For our cutting plane procedure, the problem difficulty may depend on both the gap and the computation time. Our computational results in Table 3.7 show that the percent gaps are not very sensitive to P. Problems with P between .06 to .3 have slightly larger percent gaps (up to 0.96%). On the other hand, more computation time is usually required for problems with P values around .02. In terms of order strength, that is, the ratio of the number of arcs in the transitive closure to the maximum number n(n â€” l)/2 of possible arcs, larger percent gaps tend to occur for problems with order strength between .4 and .8. In Section 3.4, we present the detailed computational results for 280 problems. Computation Times (CT), in seconds, are given in column 7. In column 4, Ord.Sth. denotes the order strength of the precedence graph. Column 5 represents the number of arcs in the transitive reduction of the digraph. Column 6 indicates the number of cuts used in Step 3 of the cutting plane procedure. Note that for almost all of the instances with P â€” 0.001, only one cut has been used. This explains that our heuristic procedure in the initial formulation finds a very good basis when the precedence graph is very Chapter 3. Single Machine Scheduling: Polyhedral Computations 59 sparse. (From the computational experiments, we found that those problems are most time-consuming if no heuristic is used in the initial formulation.) This computational study shows that the cutting plane approach based on facet defining cuts is effective for solving the precedence constrained job sequencing problems. Because of the LP formulation with n variables and tight lower bounds obtained, the algorithm has potential for solving large-scale problems to optimality with the aid of a Branch and Bound or Branch and Cut procedure. To further improve the algorithm, the following are among the possible improvements: â€¢ a better heuristic for feasible schedules, especially for the initial formulation; â€¢ separation routines for more complex facet classes (see Chapter 2); and â€¢ a Branch and Cut procedure at the final stage. Chapter 3. Single Machine Scheduting: Polyhedral 3.4 Computations C o m p u t a t i o n a l Results for 280 problems #Jobs 30 40 Name 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 P .001 .001 .020 .020 .040 .040 .060 .060 .080 .080 .100 .100 .150 .150 .200 .200 .300 .300 .500 .500 .001 .001 .020 .020 .040 .040 .060 .060 .080 .080 .100 .100 .150 .150 .200 .200 .300 .300 .500 .500 Oid.Sth. .00460 .00000 .03678 .03448 .07356 .03218 .06667 .06207 .11954 .14483 .17931 .30575 .38621 .48736 .57701 .55632 .62299 .69425 .88046 .91035 .00000 .00128 .03590 .01795 .09615 .04231 .18718 .14231 .12308 .24359 .30641 .21410 .42180 .53590 .63974 .56923 .78718 .79487 .90256 .93333 # Arcs # Cuts 2 0 11 9 22 10 23 21 29 32 34 42 50 54 52 45 59 54 46 45 0 1 23 12 34 27 55 32 54 52 61 66 73 72 74 83 80 74 62 66 1 1 2 1 2 2 4 7 6 22 24 26 24 24 16 18 29 20 23 20 1 1 9 1 14 10 33 17 45 36 33 28 26 35 36 28 26 27 55 37 CT 2.36 2.42 3.13 2.36 3.57 2.97 3.74 4.95 4.62 8.34 9.01 10.82 10.16 11.09 6.26 9.40 14.06 9.72 10.88 8.90 3.90 3.90 8.63 3.90 11.53 9.01 17.42 17.30 24.00 19.28 18.89 16.53 15.60 22.13 21.36 18.51 16.87 36.69 75.79 28.67 % Gap .00000 .00000 .00000 .00000 .00000 .00000 .00000 .00000 .21058 .03627 .32752 .95170 .34220 .26927 .00000 .08065 .41234 .42745 .12030 .00000 .00000 .00000 .00000 .00000 .00462 .00000 .04461 .09125 .00000 .02760 .07638 .23652 .08634 .14889 .09571 .20624 .02668 .74286 .12927 .00000 Table 3.8: Computational results for n â€” 30,40 Statistic AGAP .1589 ACT 6.938 AGAP .0958 ACT 19.4955 Chapter 3. Single Machine ScheduHng: Polyhedral Computations #Jobs 50 60 Name 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 P .001 .001 .020 .020 .040 .040 .060 .060 .080 .080 .100 .100 .150 .150 .200 .200 .300 .300 .500 .500 .001 .001 .020 .020 .040 .040 .060 .060 .080 .080 .100 .100 .150 .150 .200 .200 .300 .300 .500 .500 Ord.Sth. .00000 .00082 .02122 .03429 .07429 .12408 .13061 .13796 .25633 .22531 .28082 .40082 .54857 .62939 .73714 .70612 .83918 .83347 .95510 .95020 .00113 .00169 .06497 .02260 .06328 .08362 .19209 .22712 .32090 .31808 .49378 .44350 .61582 .62429 .71073 .69661 .84746 .85254 .94237 .94915 # Arcs 0 1 20 28 50 62 67 65 80 76 84 74 108 83 87 99 79 90 67 75 2 3 46 33 64 70 88 96 94 107 118 113 119 120 122 111 106 116 99 89 # Cuts 1 1 1 5 56 43 56 56 42 49 39 47 51 58 55 48 30 58 44 48 1 1 26 40 66 73 55 72 67 52 63 54 48 69 61 84 60 78 60 35 CT 5.71 5.93 6.26 10.10 43.72 29.44 43.28 41.80 30.75 36.74 28.23 36.47 42.62 51.63 49.10 44.10 26.20 63.93 72.61 52.89 8.96 10.16 36.47 64.98 63.39 69.70 50.69 69.04 65.36 53.28 69.32 62.67 56.03 86.34 81.84 112.76 81.94 133.19 79.64 44.16 % Gap .00000 .00000 .00000 .00646 .00000 .06609 .02668 .04592 .09488 .05686 .11125 .15972 .25105 .62363 .29168 .25035 .01573 .11547 .02199 .00095 .00000 .00000 .00000 .00000 .00242 .02342 .11333 .47417 .14805 .16912 .36744 .24633 .53784 .54094 .15449 .22352 .10690 .29882 .01473 .08674 Table 3.9: Computational results for n = 50,60 61 Statistic | AGAP .1069 ACT 36.076 AGAP .1754 ACT 64.996 Chapter 3. Single Machine Scheduling: Polyhedral Computations #Jobs 70 80 Name 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 P .001 .001 .020 .020 .040 .040 .060 .060 .080 .080 .100 .100 .150 .150 .200 .200 .300 .300 .500 .500 .001 .001 .020 .020 .040 .040 .060 .060 .080 .080 .100 .100 .150 .150 .200 .200 .300 .300 .500 .500 Ord.Sth. .00041 .00041 .03064 .02650 .11511 .08861 .17143 .22485 .34576 .31387 .42774 .56522 .64306 .60373 .82650 .76563 .89151 .87992 .95694 .96398 .00158 .00063 .04620 .04620 .06709 .17690 .28196 .22722 .46171 .34240 .36266 .46772 .72468 .70949 .78798 .72089 .91994 .85886 .95285 .95601 # Arcs # Cuts 1 1 43 39 87 94 112 119 147 139 163 138 138 148 132 145 139 140 111 105 5 2 75 60 107 125 168 160 170 170 183 185 174 168 162 206 132 158 122 136 1 1 57 25 103 81 86 76 65 58 79 70 106 66 82 42 78 75 57 40 1 1 46 19 120 95 113 64 71 65 61 78 83 84 83 76 19 83 39 82 CT 12.36 12.03 108.31 105.08 139.84 106.22 108.64 94.86 84.80 68.76 108.86 98.21 169.00 82.71 138.85 97.98 131.76 196.91 214.05 109.91 17.31 16.09 110.13 47.79 221.19 132.75 175.32 117.37 109.24 98.75 99.08 126.77 157.80 165.54 154.67 146.54 70.74 246.56 171.69 208.22 62 % Gap Statistic .00000 .00000 .00975 .46689 .00377 .10148 .01781 .09505 .18851 .34954 .19217 .20274 .61276 .23170 .34946 .40806 .27388 .18546 .09142 .12117 .00000 .00000 .10601 .03868 .00306 .17918 .22464 .36282 .25996 .71447 .15841 .53486 .45760 .41877 .39464 .38601 .75583 .43060 .23316 .08160 AGAP .1951 Table 3.10: Computational results for n = 70,80 ACT 109.46 AGAP .2870 ACT 129.68 Chapter 3. Single Machine Scheduling: Polyhedral Computations #Jobs 90 100 Name 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 P .001 .001 .020 .020 .040 .040 .060 .060 .080 .080 .100 .100 .150 .150 .200 .200 .300 .300 .500 .500 .001 .001 .020 .020 .040 .040 .060 .060 .080 .080 .100 .100 .150 .150 .200 .200 .300 .300 .500 .500 Oid.Sth. .00050 .00050 .03071 .03845 .11261 .10786 .24145 .25368 .36654 .41973 .50737 .56105 .72584 .70212 .81248 .76405 .87965 .87590 .97129 .96404 .00081 .00101 .04525 .03030 .10101 .09677 .23899 .30929 .43495 .45394 .57737 .50202 .73960 .75414 .83778 .79859 .91515 .92222 .96606 .97030 # Arcs # Cuts 2 2 72 87 156 140 177 171 205 182 200 207 216 205 202 207 169 194 129 145 4 5 99 89 162 170 213 209 218 228 239 233 209 218 200 217 188 178 164 157 1 1 140 94 107 102 92 97 70 92 78 74 108 98 103 81 96 114 73 82 1 1 60 99 148 122 106 129 105 110 126 109 126 141 90 126 67 87 56 53 CT 22.36 20.38 562.22 310.38 192.23 206.74 162.97 167.64 131.55 208.00 175.93 161.43 298.19 215.64 244.26 221.79 265.67 321.92 284.40 329.00 24.71 25.65 199.71 530.80 389.54 269.68 222.06 265.18 218.50 243.71 418.37 250.13 372.78 449.40 320.55 381.19 376.02 461.76 232.22 154.68 63 % Gap Statistic .00000 .00000 .00000 .01671 .08633 .13070 .11381 .26182 .47914 .54811 .95225 .35829 .59628 .32440 .18701 .16728 .13002 .20084 .00510 .02184 .00000 .00000 .05779 .01623 .08459 .05475 .17924 .06981 .30606 .25238 .30853 .37136 .43368 .48349 .19209 .51074 .27127 .18564 .12527 .28807 AGAP .2290 Table 3.11: Computational results for n = 90,100 ACT 225.14 AGAP .2095 ACT 290.33 Chapter 3. Single Machine Scheduling: Polyhedral Computations #Jobs 110 120 Name 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 P .001 .001 .020 .020 .040 .040 .060 .060 .080 .080 .100 .100 .150 .150 .200 .200 .300 .300 .500 .500 .001 .001 .020 .020 .040 .040 .060 .060 .080 .080 .100 .100 .150 .150 .200 .200 .300 .300 .500 .500 Ord.Sth. .00050 .00100 .04087 .05588 .26539 .17831 .31793 .32127 .44671 .48791 .66806 .58415 .75113 .75663 .84304 .84871 .90142 .92410 .97448 .96931 .00140 .00084 .05574 .03529 .28123 .23193 .36807 .41583 .52507 .52563 .64160 .62661 .74776 .80924 .84566 .85294 .92031 .91681 .98039 .97521 # Arcs # Cuts 3 6 110 129 201 205 271 266 285 276 241 294 268 256 232 237 223 206 173 162 10 6 154 126 261 236 279 300 304 305 282 304 313 257 258 267 229 239 176 186 1 1 317 222 113 102 94 114 102 97 156 108 109 109 116 132 34 115 86 91 1 119 205 265 124 136 124 111 104 104 111 121 132 50 75 105 52 50 38 68 CT 30.43 30.05 1614.70 813.66 289.51 245.90 233.10 288.90 245.14 256.06 459.94 348.67 308.46 488.46 456.71 397.77 166.75 540.19 570.29 500.76 42.85 768.46 909.18 1449.15 352.18 494.98 389.59 311.48 327.85 567.11 334.94 422.11 475.77 237.55 524.92 463.24 234.37 301.60 183.45 532.78 % Gap .00000 .00000 .00000 .00948 .07890 .05274 .21554 .46806 .19019 .24626 .23973 .88693 .24279 .29757 .40698 .21956 .41074 .04542 .13094 .06043 .00000 .00000 .04924 .00363 .14214 .16975 .96183 .19506 .55736 .40434 .27584 .70647 .68209 .69801 .76291 .33794 .29232 .37252 .22883 .09273 Table 3.12: Computational results for n = 110,120 64 Statistic AGAP .2101 ACT 414.27 AGAP .3466 ACT 466.18 Chapter 3. Single Machine Scheduhng: Polyhedral Computations #Jobs | Name 130 140 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 P .001 .001 .020 .020 .040 .040 .060 .060 .080 .080 .100 .100 .150 .150 .200 .200 .300 .300 .500 .500 .001 .001 .020 .020 .040 .040 .060 .060 .080 .080 .100 .100 .150 .150 .200 .200 .300 .300 .500 .500 OrcLSth. .00143 .00119 .04568 .04770 .17197 .13787 .41145 .42922 .52009 .56947 .68515 .64782 .75826 .79165 .87871 .86094 .94252 .90912 .97865 .96923 .00113 .00082 .05704 .06495 .22354 .19168 .46218 .46578 .54820 .52795 .69239 .68612 .77359 .82867 .84327 .86218 .94132 .93731 .97718 .97811 # Arcs 12 10 168 153 291 274 321 302 344 301 322 329 332 322 265 292 231 288 194 219 11 8 181 199 332 297 326 321 354 368 372 325 354 304 347 312 278 291 225 218 # Cuts 45 13 296 312 145 118 68 76 103 129 130 103 149 115 115 110 123 170 77 76 1 124 304 259 150 139 187 134 153 149 113 152 113 40 154 32 162 59 87 55 CT 264.53 114.96 1726.70 1888.78 445.51 390.14 291.05 300.77 332.69 445.23 527.62 471.09 627.36 407.88 589.68 524.70 1051.00 773.95 485.10 457.75 64.15 1180.68 1769.81 1342.71 571.00 581.77 647.36 525.03 643.45 601.05 567.71 775.33 527.67 217.95 858.60 257.88 1052.65 361.58 593.25 468.07 % Gap .00000 .00000 .03171 .05270 .11493 .06434 .44764 .34043 .25293 .25269 .33697 .37895 .49034 .17745 .15636 .11167 .12904 .17247 .07439 .19034 .00000 .00000 .02924 .07154 .28460 .14907 .31147 .31678 .40014 .87223 .36579 .58323 .09663 .79355 .14770 .86032 .11478 .15913 .13079 .22498 Table 3.13: Computational results for n = 130,140 65 Statistic AGAP .1888 ACT 605.82 AGAP .2956 ACT 680.39 Chapter 3. Single Machine Scheduling: Polyhedral Computations #Jobs 150 160 Name 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 P .001 .001 .020 .020 .040 .040 .060 .060 .080 .080 .100 .100 .150 .150 .200 .200 .300 .300 .500 .500 .001 .001 .020 .020 .040 .040 .060 .060 .080 .080 .100 .100 .150 .150 .200 .200 .300 .300 .500 .500 Oid.Sth. .00107 .00125 .05145 .05414 .20546 .22407 .48054 .41682 .53127 .61494 .69942 .69110 .80143 .83400 .88143 .88608 .93709 .94622 .97888 .98201 .00087 .00126 .06022 .05299 .26832 .24772 .38585 .48884 .58530 .61580 .71069 .73538 .81942 .83561 .89285 .89222 .93789 .93931 .98608 .98019 # Arcs 12 14 223 219 354 326 388 422 437 405 388 389 370 338 326 330 279 280 236 231 11 15 233 220 386 369 474 429 426 423 394 396 406 392 357 345 327 325 223 251 # Cuts 119 125 344 268 151 156 157 117 154 156 105 124 81 151 209 60 51 116 58 46 1 129 289 402 160 150 142 112 111 152 176 107 210 166 75 191 158 86 56 113 CT 1112.90 1194.52 2074.26 1613.16 585.62 537.89 671.85 583.81 692.94 847.50 653.78 682.55 443.47 934.89 1729.00 449.67 430.12 1051.93 296.93 436.44 112.16 2280.40 2005.44 3513.58 633.40 591.05 625.27 738.20 625.88 921.66 950.65 698.43 1544.83 1100.38 628.79 1288.22 1277.35 1132.02 384.31 1694.40 % Gap .00000 .00000 .00365 .00618 .34732 .14711 .49276 .20610 .66706 .63095 .71995 .21691 .38478 .22556 .34891 .58260 .42886 .15777 .14922 .35984 .00000 .00000 .01548 .01715 .20351 .24819 .34809 .54318 .39843 .42387 .72379 .43946 .66236 .34659 .41888 .24187 .19612 .21530 .17023 .16632 Table 3.14: Computational results for n = 150,160 66 Statistic AGAP .3038 ACT 851.16 AGAP .2889 ACT 1137.32 Chapter 4 Hamiltonian Path and Symmetric Travelling Salesman Problem This chapter introduces a Hamiltonian Path (HP) approach for studying symmetric travelling salesman polytopes (STSPs). By studying HP polytopes, we develop general clique-lifting results, all based on simple conditions, for deriving large new classes of STSP facets. These results apply to all known non-trivial STSP facets, and generalize clique-lifting results of Maurras [38], Grotschel and Padberg [27] and Naddef and Rinaldi [41]. 4.1 Introduction Let K(V) â€” (V, E(V')) be a complete undirected graph, where the node set V represents a set of cities. A feasible solution to the Symmetric Travelling Salesman (STS) problem is a Hamiltonian cycle C on V, uniquely determined by its corresponding 0-1 incidence vector y Â£ R ( ') (where y = 1 if edge e is used in C and zero otherwise). This E V e chapter deals with the STS polytope STSP(V), the convex hull of incidence vectors y of all feasible solutions to the STS problem. The facial structure of STS polytopes (STSPs) has been the object of considerable research over the past two decades. We refer to Grotschel and Padberg [28] for an excellent survey (up to 1985). Since then, there have been many advances in studying STS polytopes and in solving large-scale STS problems. Large classes of STSP valid inequalities were proposed by Boyd and Cunningham [7,8], Cornuejols, et al. [13], Fleischmann [19,20,21], Naddef and Rinaldi [41,42,44], Naddef [40]. Some of these inequalities, 67 Chapter 4. Hamiltonian Path and Symmetric Travelling Salesman Problem 68 such as clique-tree [29], chain (introduced in [47], and proven to be facet-defining independently by S. Boyd and M . Hartmann, cf. [8]), ladder [8], crown and path-tree [42,43] inequalities are known to be facet-defining. The study of STSP facets is also of practical importance: Padberg and Rinaldi [49] have successfully demonstrated the use of facetdefining inequalities, such as clique-tree inequalities, in solving large-scale, real-world STS problems (with over 2000 cities) to optimality. For small STS polytopes, Naddef and Rinaldi [43] present a list of inequalities defining 133,707 distinct facets of STSP(V) when | V | = 8, including nonnegativity constraints, sub-tour elimination, ladder, chain, crown, and path inequalities. Boyd and Cunningham [8] have proven that part of this list entirely describes STSP(V) with |V'| < 7. Christof et al [15] use a computer code to derive a complete description of STSP(V) with |V'| = 8, where in addition to Naddef and Rinaldi's list, three classes of new facets are discovered. For the case |V'| = 9, we introduce a new facet in Figure 4.3, illustrating the incompleteness of all the above known facet classes for | V | > 9. This chapter uses a projective approach to the polyhedral study of symmetric travelling salesman problems. Consider the node set V = V \ {h}, where h Â£ V is any given projection node. Let HP(V) denote the Hamiltonian Path Polytope (HPP), i.e., the convex hull of incidence vectors x of all Hamiltonian paths (with free endnodes) on V. Using a one-to-one correspondence between Hamiltonian cycles on V and Hamiltonian paths on V = V \ {h}, we show that HP(V) is a projection of STSP(V) onto the sub- space R ( ) of R ( '\ More importantly, HP(V) exhibits three fundamental properties E V E V for this projective approach: (a) HP(V) is near-full dimensional, with a single implicit equation 52 E(V) ee x e = \V\ â€” 1; (b) a, move from one vertex x Â£ HP(V) to another one may involve only one interchange of components in x, whereas such a move involves at least two interchanges in y â‚¬ STSP(V) (the so-called 2-opt interchange); (c) polyhedral Chapter 4. Hamiltonian Path and Symmetric Travelling Salesman Problem equivalence: the polyhedral structures of HP(V) and STSP(V) 69 are isomorphic. Prop- erties (a) and (b) greatly facilitate the indirect proofs of any facetial results for HP(V), and property (c) implies immediately that the corresponding facetial results also hold for STSP(V). In contrast, additional hard work is required for transferring facetial results, derived from monotone [28] or graphical relaxations [13], to corresponding results for STSP(V). We study extensions of STSP facets by clique-lifting. For A T S polytopes, Balas and Fischetti [6] prove a general clique-lifting result that applies to all nontrivial facets of ATS polytopes. For STS polytopes, it is unknown whether such a powerful lifting result holds. Maurras (1975), Grotschel and Padberg (1979), and Naddef and Rinaldi (1989) present various sufficient conditions for clique-lifting of STSP facets. The early lifting results employs simple conditions (verifiable by inspection or in linear time) but their applications seem restricted. Naddef and Rinaldi's clique-lifting result applies to large classes of known STSP facets, but the condition seems difficult to verify in general (we do not know whether there exists a polynomial-time algorithm to verify their condition). In this paper, we propose a rather general clique-lifting result (with at least two new nodes added) that applies to any nontrivial STSP facet w.r.t. any given node. (In the sequel, "w.r.t." stands for "with respect to".) We also show, by the projective approach, that Naddef and Rinaldi's sufficient condition for node-cloning (i.e., clique lifting with exactly one new node added) is in fact necessary. As the condition is difficult to verify, we propose three simplified node-cloning results, all based on conditions that can be verified either by inspection or by a procedure of time complexity linear in the number of edges. The first result seems applicable to all known nontrivial facets (such as clique-tree, chain, ladder, crown, path and path tree, etc.) w.r.t. any node. The second result generalizes the clique-lifting results in Maurras [38], Grotschel and Padberg [27]. The third result shows that any node can be cloned in any facet-defining rank inequality (i.e., inequality Chapter 4. Hamiltonian Path and Symmetric Travelling Salesman Problem 70 ay < ao with zero-one coefficients). The rest of the chapter is organized as follows. Section 4.2 gives basic terminology and notation. Section 4.3 introduces the projective approach and the polyhedral equivalence of HP(V) and STSP(V'), as well as other related results. In Section 4.4, we propose a clique-lifting result (with clique size greater than two) for all nontrivial STSP facets and prove that Naddef and Rinaldi's clique-lifting condition is necessary. In Section 4.5, we present our simple sufficient conditions for node-cloning. Section 4.6 offers concluding remarks. 4.2 Definition and Notation Our notation and terminology mostly follow those in [6],[28],[41]. (1) . For any node set V with n = |V| > 3, let K(V) = (V,E(V)) denote the complete undirected graph with node set V. Note that |.E(V)| = n ( n â€” l)/2. For any subsets S i and S'2 of V, let E(S 1 : S ) = {(ij) 2 <E E(V) : i â‚¬ S j <E S'2}. ly When S = Si = S'2, denote E(S : S) by E(S), i.e., the collection of all edges in E(V) with both endnodes in S. For any S C V, denote the complete graph on node set S by K(S) = (S, E(S)). For any node v E V, let S(v) = E({v} : V \ {v}) denote the star of v, i.e., the set of all edges in E(V) incident to v. (2) . A partial graph (S, E) is a subgraph of K(S) with E C E(S). The incidence vector of partial graph (V, E) of K{S) is the vector x Â£ R ^ E Xe = 0 otherwise. For any vector ij> G R ^ E 4>(Â£) = such that \e = 1 if e G E and and E C E(S), let X> . e (4.1) Chapter 4. Hamiltonian Path and Symmetric Travelling Salesman Problem 71 A Hamiltonian cycle C on S is a connected partial graph (S, E) such that for all r; G S. \EClÂ£{v)\ = 2, Without risking confusion, a Hamiltonian cycle C with edge set E = : * = l , - , ^ - 1} U {(tty.), Â«â€ž(!))} on node set S = {v\,v } C V may be represented by edge set E alone or, equivalently, s by the circular permutation (u<7(i)...i>o-()) of the nodes. a A Hamiltonian path P on S = {vi,...,v } C V is a connected partial graph (S,E) s such that for some distinct nodes i, j G 5, ( S , Â£ U {*>.?}) defines a Hamiltonian cycle on S. Note that the endnodes of P are not specified in advance, i.e., we consider here paths with free endnodes. Hamiltonian path P may be represented by its edge set {(u,-, u +i) : t i â€” l,...,s â€” 1} or, equivalently, by its corresponding node permutation (vi...v ) with a endnodes v\ and v . Note that if l^l = 1, the first form is an empty set, whereas the a second form reduces to a single node When a path is written in the form (u...vp...q), we always allow u = v or p = q or both. For any node set 5, the STS polytope STSP(S) and HP polytope HP(S) are defined, respectively, as follows. STSP(S) HP(S) = conv {y G R?W : C is a Hamiltonian cycle on 5}, c = conv{x G R p E(S) : P is a Hamiltonian path on 5}. (3). To any inequality cx < CQ with c > 0 and x G R ( \ we associate its support graph: E S G (S) = (5, E ), e c where E = {ee c E(S) : c > 0}. e The complement graph G (S) = (S,E ), where _E = E(S) \ E , is called the zero-graph C w.r.t. cx < CQ. C C c Chapter 4. (4). Hamiltonian Path and Symmetric Travelling Salesman Problem Let ay < ao and cx < Co be two valid inequalities for STSP(S) 72 and HP(S), respectively. We say that C is an a-tight cycle (resp., P is a c-tight path) on 5* if C is a Hamiltonian cycle on S and ay c cx = a (resp., if P is a Hamiltonian path on S and 0 = Co). p 4.3 P o l y h e d r a l Equivalence: H P P v.s. S T S P The STS polytope (STSP) is far from being full dimensional because every Hamiltonian cycle satisfies a degree constraint equation at each node. In contrast, the HP formulation relaxes all degree constraints. This observation suggests that HP(V) be more nearly full dimensional. It leads to the development of a projective approach to the study of travelling salesman problems. A similar projective approach has been used for the equipartition polytope by Conforti, Rao and Sassano [12]. Let V be a node set with |V'| = n+1, and for some fixed node h Â£ V, let V = V'\{h}. Consider two complete undirected graphs: K(V) = {V,E(V)) That is, K(V) is obtained from K(V) edges. Let STSP(V) and K(V) = (V',E(V)). by eliminating node h Â£ V and all incident be the STS polytope defined on K(V), polytope defined on K(V). and HP(V) be the HP Observe that P is a Hamiltonian path on V with endnodes u and v iff C = P U {(h, u), (h, v)} is a Hamiltonian cycle on V. Thus, the incidence vector x RW E p Â£ R() E V is a projection of the incidence vector y c Â£ R ( ) onto subspace E V> of R <y'\ It follows that the polytope HP(V) is a projection of STSP(V). E what follows, we assume that all incidence vectors y on K(V) (j/i,y m , t/m+i,ym'Yi edge set E(V). In are indexed as: y = where the first m = n(n â€” l)/2 elements correspond to the Chapter 4. Hamiltonian Path and Symmetric Travelling Salesman Problem 73 Let An be a node-edge incidence matrix of K(V). Observe that the incidence vectors y c G R ( ') of all Hamiltonian cycles C on V and their projections x E V p GR^ satisfy E the following identity: (u,v)eE(V); 2 - Z eE(v)(A ) x?, e (4.2) (u, t;) G E{h : V). n ve Clearly, the above equation defines an affine transformation from HP(V) to STSP(V). The following result shows that this transformation is affine-rank preserving. L e m m a 4.1 Let B y = [y ,y ] 1 be any matrix such that all column vectors y l cidence vectors of Hamiltonian cycles on K(V'). projection of y into R ( \ 3 vectors in B y j = 1,/. E V Let B x = [x ,x ], 1 l 3 where x are in3 is the Then the number of affinely independent column is equal to the number of affinely independent column vectors in B. x Proof: From equation (4.2), it follows / it aff.rank ( J?â€ž ) = rank > rank = rank \ / > rank V 1 0* 0 1 2 -A Il V\ v \ n B x I = aff.rank a, J where "aff.rank" denotes the affine rank of the column set, "rank" denotes the linear rank, 0 (resp., 1) is a vector of zeroes (resp., ones) and I is an identity matrix, all of conformable dimension. Hence, equality must hold throughout. The dimension of HP(V) could now be derived from that of STSP(V) â€¢ using L e m m a 4.1. In fact, the direct derivation of dim(HP(V)) given below is very simple. Thus, we obtain a much simpler proof than any known proof for dim(5T5'P(V')) (see [28], section 4.1, for two other proofs). Chapter 4. Hamiltonian Path and Symmetric Travelling Salesman Problem T h e o r e m 4.2 The dimension of HP(V) dim(HP(V)) = ^ 74 is: ~ ^ - 1, w/iere n = > 3. (4.3) Proof. Since every Hamiltonian path P on V must satisfy implicit equation x (E(V)) p n â€” 1 for HP(V), = we have dim(#P(V)) < ~ ^ - 1. (4.4) Let /x = /o be any equation satisfied by all incidence vectors x E HP(V). For any distinct e\, e E ^(^) there exists a Hamiltonian cycle C in K(V) containing e\ and e . 2 5 2 Since P = C \ ei and P = C \ e are two Hamiltonian paths in -RT(V), 1 2 2 0 = fx pl - fx = /â€ž - / p2 e i . This shows that / is constant for all e Â£ - E ^ ) , and equation fx = fo must be a multiple e of implicit equation x(E(V)) â€” n â€” 1. â€¢ R e m a r k 4.3 By T h e o r e m 4.2, two valid inequalities cx < CQ and dx < CQ for HP(V) are equivalent iff there exist two scalars a > 0 and /3 such that CQ = aco + (n â€” l)/3 and d â€” ac + 0 for all e 6 ^(V"). This equivalence greatly simplifies indirect proofs of e e facetial results for HP(V). â€¢ C o r o l l a r y 4.4 The dimension of STSP(V) dim(STSP(V')) is: = 1 } - (n + 1). (4.5) Proof. From L e m m a 4.1 and T h e o r e m 4.2, it follows that dim(STSP(V')) = dim(HP{V)) = n ( n ~ ^ - 1= n ( " + X ) - (n + 1). â€¢ Chapter 4. Hamiltonian Path and Symmetric Travelling Salesman Problem 75 R e m a r k 4.5 D. Naddef points out that such dimensionality results are equivalent to characterizations of the constant TSP (see [25], section 2). We therefore also obtain as a corollary a simple proof of the theorem of Berenguer (theorem 1 in Gilmore et al. [25]). â€¢ Closed form representations for inequalities ay < ao are used in the figures hereafter. For each inequality with nonnegative coefficients, a collection of node subsets with positive weights (numbers) are given. Weights are indicated next to the corresponding sets and all set weights of value one are omitted for simplicity. Then, each coefficient a , j equals the total weight of all the subsets which contain both nodes i and j. r7| G) (7) /'' ( _ 2 ~h \ f 2_*_ ( d U U ) < 9 (a) An Envelope (b) /^-normal form (c) Zi'-normal form Figure 4.1: Equivalent envelope inequalities Figure 4.1 presents such representations. For instance, in Fig. 4.1(a), ao = 9, a ^ = 2, a>d'h' = a-dh' = 1 and ahd> = ahh> = o-dd = 0, 1 etc. Now, we turn to relationships between valid inequalities for STSP(V) HP(V). and those for Recall that V \ V = {h}. Consider two inequalities ay < a and ex < Co, 0 defined on STSP(V) a Q = co; and HP(V), a e = c> e 0, respectively, and satisfying: Ve G E(V); and a e = 0, Ve â‚¬ E(h : V). Then, ay < ao is said to have an isolated node h (cf. Fig. 4.1(b)). Inequality ex < Co is the h-restriction of ay < a o , and conversely, ay < a is an extension of ex < Co. Q By L e m m a 4.1 and T h e o r e m 4.2, we have immediately: Chapter 4. Hamiltonian Path and Symmetric Travelling Salesman Problem 76 T h e o r e m 4.6 (Polyhedral Equivalence) For any integer k such that 0 < k < n(n â€” l)/2 â€” 1, the inequality ay < ao with isolated node h defines a k-dimensional face of STSP(V) iff its h-restriction cx <CQ defines a k-dimensional face of HP(V). The above theorem, along with R e m a r k 4.3, provides a projective approach to the study of STS polytopes. This theorem also suggests the following unique representation of an STSP valid inequality w.r.t. a given node h Â£ V. ^ - n o r m a l f o r m . An inequality ay < a for STSP(V) 0 is in normal form w.r.t. a given node h Â£ V (^-normal form, for short) if (Cl) a = 0 for all e Â£ E({h} : V \ {h}); e (C2) a > 0 and a = 0 for some e â‚¬ E(V \ {h}); e (C3) min{a > 0 : e Â£ E(V')} = 1. e Inequality cx < CQ for HP(V) is in normal form if its extension ay < a for 0 {h}), where h STSP(VU V, is infe-normalform. See Figure 4.1 for examples. R e m a r k 4.7 Balas and Fischetti [6] use a similar notion, h-canonical form, to uniquely represent ATSP inequalities. We use this notion here for STSP inequalities with a different scaling in (C3). Such forms can also be obtained by applications of Remark 4.2 of Grotschel and Padberg [27]. â€¢ Any valid inequality ay < a for STSP(V) 0 admits a unique /i-normal form a'y < a' 0 w.r.t. any given node h Â£ V. This can be obtained by the following ^-normalization procedure. ^ - N o r m a l i z a t i o n procedure Input: A valid inequality ay < a for STSP(V), 0 and any given projection node h Â£ V. where \V'\ = 71 + 1, Chapter 4. Hamiltonian Path and Symmetric Travelling Salesman Problem O u t p u t : An equivalent valid inequality a'y < a' for STSP(V) Q 77 in /i-normal form. Step 1: /i-Projection. Adding to ay < a the following linear combination 0 of degree constraints: Â£ -a hy(S(v)) = Â£ v vÂ£V'\{h} -2a vh vev\{h} yields ay < ao. Note that after the projection, a = 0 for all e G 8(h). e Step 2: Shifting. Adding to ay < a the implicit equation Xy(E(V'\{h})) = 0 \(n - 1), for STSP(V), where A = -min{a : e G Â£ ( V \ {h})}, e yields ay < do. Note that after shifting, d = d + A(n â€” 1), a, > 0, and 0 0 d = a + A if e G i5(V \ {/i}) and zero otherwise. Note also that for some e e e(EE(V'\{h}), a = 0. e Step 3: Scaling. The scaling operation is defined by (a',a' ) = (a,a )/7, 0 0 where 7 = min{a > 0 : e G F ( y ) } . e For instance, Fig. 4.1(a) represents inequality ay < a . After the normalization 0 procedures w.r.t. nodes h and h', we obtain its /i-normal form in Fig. 4.1(b) and h'normal form in Fig. 4.1(c), respectively. Observe that in this example, the /i-normal form in Fig. 4.1(b) is obtained by simply complementing set {h, d}: adding to ay < ao the following implicit equations for STSP(V): - y(S(v)) = -2,Vu G {h,d}- y(S(v)) = 2,to G V \ {h,d}. (4.6) Chapter 4. Hamiltonian Path and Symmetric Travelling Salesman Problem 78 To obtain the Zi'-normal form in Fig. 4.1(c), we need two successive set complementations. /i-projected inequality, or /i-projection. Let a'y < a' be the /i-normal form of 0 a V < Â°o for STSP(V), for HP(V and let ex < CQ be the ^-restriction of a'y < a' . Then ex < CQ 0 \ {h}) is an h-projected inequality or h-projection of ay < ao. Two important observations immediately follow from the above procedure. the normalization procedure requires 0(E(V')) First, computational steps. Thus, we obtain a linear time algorithm to check whether or not two valid inequalities define the same face (facet) of STSP(V). Second, the coefficients of the /i-normal form a'y < a' satisfy: 0 a' > 0, a' = 0 for all e G 6(h) and a' = 0 for some e G E(V e e \ {h}). These edges correspond to linearly independent columns of the node-edge incidence matrix of K(V). By Lemma 6.3 in [29], it follows that a'y < a' is in support-reduced form, and therefore 0 o'y < 'o is facet-defining for the monotone STS polytope MTSP(V) a nontrivial facet of if it defines a STSP(V). R e m a r k 4.8 A similar /i-projection technique was also introduced independently by Araque [2] in his polyhedral study of vehicle routing problems (VRP) with single depot and variable fleet size. Consider a VRP with one vehicle and a single depot node h. Then, the coefficients of a in Step 1 of the /i-Normalization procedure satisfy â€”a,j = a hi + uhj â€” aij = sij for all (i, j) G E(V \ {h}), where s,j, as observed by Araque [2], is exactly the saving defined by Clarke and Wright [11]. â€¢ From results in [28] and the polyhedral equivalence, we obtain simple classes of facetdefining inequalities for HP(V). P r o p o s i t i o n 4.9 Let S(v) = E({v} : V \ {v}) for all v G V, and let n = \V\. following is a system of facet-defining inequalities for HP(V), which are equivalent. The where n > 4, no two of Chapter 4. Hamiltonian Path and Symmetric Travelling Salesman Problem (a) x > 0, e 79 Ve G E(V); (b) x(S(v)) < 2, Vu G V; (c) x(E(W)) < \W\ - 1, VW C V and 2 < \W\ < n - 1. Note that for \W\ = n â€” 1, (c) can be restated as the lower degree constraint x(S(v)) > l,{u} = V \ W for HP(V). Accordingly, constraints (b) are called the upper degree constraints. Note also that, for all v G V , the degree constraint x(8(v)) > 1 (resp., x(S(v)) < 2) is equivalent to x vh < 1 (resp., x vh > 0) for STSP(V U {h}), where h Â£ V. For W = {i,j}, (c) is equivalent to the simple upper bound constraint xij < 1 for HP(V). Constraints (b) and (c) are in normal form. The normal form for the nonnegativity constraints (a) is x(E(V) \ e) < n - 1, Ve G E(V). In accordance with the definition of STSP trivial facets, we also define HPP trivial facets. S T S P T r i v i a l Facets. Inequality ay < a defines a trivial facet of STSP(V) 0 if it is equivalent to y > 0 for some e G E(V). (cf. [26,29]) e H P P T r i v i a l Facets. Inequality cx < CQ defines a trivial facet of HP(V) if it is equiv- alent either to x > 0 (with normal form: x(E(V) \ {e}) < |V| â€” 1) for some e e G E(V) or to x(S(v)) < 2 for some v G V. (cf. P r o p o s i t i o n 4.9(a),(b).) The next lemma exhibits an important property of HPP nontrivial facet-defining inequality. This property will be frequently (and sometimes implicitly) used in the proofs of our polyhedral results. L e m m a 4.10 Let cx < CQ be in normal form and define a nontrivial facet of Then HP(V). Chapter 4. Hamiltonian Path and Symmetric Travelling Salesman Problem (1) for every edge e E E(V), 80 there exists a c-tight path P on V such that e G P; and (2) for every node v Â£ V, there exists a c-tight path P on V such that v is one of its endnodes. Proof: (1) follows since otherwise cx < CQ is equivalent to x > 0 for some e E E(V). e (2) holds since otherwise cx < CQ is equivalent to x(S(v)) < 2 for some v EV. 4.4 â€¢ Clique-Lifting In this section, we discuss general clique-lifting results for extending known STSP facets. First, we review related notions and results. Then, we show that any nontrivial STSP facet can be extended to a lifted facet by replacing any node with a clique of size greater than two. Finally, we prove a necessary and sufficient condition for node-cloning (i.e., clique-lifting of size two), extending Naddef and Rinaldi's zero-lifting result in [41]. Definition 4.A(c-Connectedness, adapted from Naddef and Rinaldi [41]). Nodes u,v E V are c-adjacent w.r.t. the valid inequality cx < CQ for HP(V) if there exists a c-tight path P on V such that u and v are the endnodes of P. A subset U C V of nodes is c-connected if for any pair of nodes p,q E U, there exists a c-adjacent node sequence u i , u , . . . , u / E U with U\ = p and u/ = q such that u,- and u , i are c-adjacent 2 for every i = 1 , / + â€” 1. This c-connectedness condition is equivalent to the Partition Condition, ( P C ) for short, as shown below. L e m m a 4.11 (Partition Condition) Let ay < a be a valid inequality for Q and cx < Co be its h-projection for HP(V), statements are equivalent. (1) V is c-connected. where V = V \ {h}. STSP(V) Then the following Chapter 4. Hamiltonian Path and Symmetric Travelling Salesman Problem 81 (2) For every proper partition {U, U'} ofV, there exists a c-tight path (u...u') on V such that u Â£ U and v! Â£ U'. (3) ( P C ) ; For every proper partition {U, U'} ofV, there exists an a-tight cycle C on V containing a 3-node subchain (uhu') with u Â£ U and u' Â£ U'. Proof: If there exists a proper partition {U, U'} violating statement (2), V is clearly not c-connected. Conversely, let (u'...v') be a c-tight path on V and initially let U = {u',v'}. Observe that U is c-connected. Then, repeat the following procedure. (A) Using statement (2), there exists a c-tight path (u...v) on V for some u Â£ U and v Â£ U' = V \ U. Hence, U U {v} is c-connected. Replace U by U U {v}. Repeat (A) until U = V. This shows that statements (1) and (2) are equivalent. Finally, note that by polyhedral equivalence, statements (2) and (3) are equivalent. â€¢ The c-connectedness property plays an important role in deriving our main lifting results. A simple sufficient condition for this property to hold w.r.t. a nontrivial facetdefining HPP inequality ex < CQ is given below. L e m m a 4.12 (Sufficient C o n d i t i o n for c-Connectedness) trivial facet of HP(V) with c>0, Letcx < CQ define a non- and let G (V) be its zero-graph (cf. (3) in Section 2). C Suppose that the set U C V induces a connected subgraph G (U) of G (V). C C Then U is c-connected. Proof: Since cx < Co is nontrivial, for any (u, v) with câ€žâ€ž = 0, there exists a c-tight path (p...uv...q) on V containing (u, v). Thus, (u...pq...v) is also a c-tight path, showing u and v are c-adjacent. Further, since G {U) is connected, there exists a c-adjacent node C sequence connecting any pair of nodes u, v Â£ U, Hence, U is c-connected. Definition 4 . B (Clones, Balas and Fischetti [6]). â€¢ Chapter 4. Hamiltonian Path and Symmetric Travelling Salesman Problem 82 A pair of nodes h and t in V are called clones, or form a clone pair, w.r.t. ay < ao if (Cl) ahv = a, for all v E V \ {h,t}, and tv (C2) aht = m&x{a h + a u vh â€” a uv : u, v E V \ {h, t},u ^ v}. An inequality ay < ao for STSP(V) is called primitive (or simple [41]) if there exists no clone pair. In Figure 4.2, (a) represents a primitive inequality, where in (b), h' and s' (resp., h and s) form a clone pair. Definition 4 . C ( C l i q u e - L i f t i n g , Zero-Lifting and N o d e - C l o n i n g ) . Let ay < a be a valid inequality for STSP(V). 0 For any given h E V, define clique weight Â£ = max{a ih + a jh - ay : i, j E V \ {h}, i ^ j}. Consider any node set S such that S D V = 0. We say that the inequality a*y* < aj for STSP(V U S) is obtained by clique-lifting ofay < a w.r.t. to node h if aj = a + 0 0 and a , u E V, v E V ; a , ueS, Â£, u E S U {/i}, u E 5U{fe}. uv <C= j hv veV\{h}; (4.7) It is a zero-lifting if Â£ = 0. It is called node-cloning if |5| = 1. The facet-defining inequality ay < a is clique-liftable (resp., node-clonable) w.r.t. 0 if the lifted inequality a*y* < a^ is facet-defining for any nonempty S (resp., singleton set S). Clique-Lifting can be viewed as replacing h by the clique ({h} U 5", E({h} U 5")) with clique weight Â£. Fig. 4.2(b) represents the lifted inequality obtained by two successive node-cloning of the inequality in Fig. 4.2(a) w.r.t. nodes h' and h, respectively. Clique-Lifting, equivalent to |5| successive node-clonings on h, yields a valid STSP inequality, as shown by the following two lemmata. Chapter 4. Hamiltonian Path and Symmetric Travelling Salesman Problem 83 15 12 h', s' h, s (b) A lifted bipartition inequality (a) A primitive bipartition inequality Figure 4.2: Facet-defining bipartition inequalities L e m m a 4.13 ( P r o p e r t y of a N o d e - C l o n e d Inequality) Let ay < a be an inequal0 ity for STSP(V), and let nodes h,t be a clone pair w.r.t. ay < ao. If the inequality a*y* < UQ for STSP(V U {5}) is obtained by node-cloning on h, then a\ = a* = a^ . s s t Proof: Since h and t form a clone pair, node-cloning of ay < a w.r.t. h yields 0 a* hs = max{a,fc + a = max{a/ ,max{a + a jh - a lt {j :i,jeV'\ ht hv â€”a {h}, i ^ j} tv : v 6 V \ {h, t}}} = a th Similarly, we show that a* = aht- a s L e m m a 4.14 (Validity of Clique-Lifting) Let ay < a STSP(V), and let the inequality a*y* < any given node h. Then a*y* < 0 be any valid inequality for be obtained by clique-lifting ofay < a w.r.t. 0 is valid for STSP(V U S). Proof: Consider first S â€” {s}. If there exists an a*-tight cycle C* = (usv...r) on V ' U { Â« } such that a*(C*) > aj$, then C = (uv...r) is a Hamiltonian cycle on V with a(C) = a*(C*) - a us - a vs + a uv = a*(C*) - a uh - a vh + a uv > - a* h3 = a, 0 a contradiction. Hence, node-cloning yields a valid inequality. Using induction on |5|, and L e m m a 4.13, the proof is complete. â€¢ Chapter 4. Hamiltonian Path and Symmetric Travelling Salesman Problem 84 Node-cloning or clique-lifting are equivalent to zero-lifting of an STSP inequality by > b in tight triangular form. Recall the definition of this form below. 0 Definition 4 . D ( T T - F o r m , Naddef and Rinaldi [41]). Inequality by > bo is a tight triangular inequality, or in tight triangular form (TT- inequality, or TT-form, for short) if (Tl) for all distinct nodes u,v,w Â£ V, the triangular inequality b uv < b -\-b uw wv holds; and (T2) for any w Â£ V, there exists a pair of nodes u, v Â£ V \ {w} such that b â€” uv bum ~\~ b . ' wv Note that any STSP inequality has a unique (up to positive scaling) TT-representation. P r o p o s i t i o n 4.15 (Characterizations of P r i m i t i v e Inequalities) Let ay < a be 0 any valid inequality for STSP(V). form of ay < ao and G h(V) a For any node h Â£ V, let a y < a Â§ be the h-normal h be its support graph. Then the following statements are equivalent: (a) ay < a is a primitive inequality. 0 (b) There exists no clone pair w.r.t. ay < a . 0 (c) The support graph G h(V) a contains exactly one isolated node h for any h Â£ V. (d) The coefficients of the TT-form by > bo ofay < ao are all positive. Proof: (a) (b) by definition. To prove (b) (c), observe that by the uniqueness property of /i-normal form, there exists a clone pair h,t Â£ V w.r.t. ay < a iff both h 0 and t are isolated nodes in G h(V). a The latter is equivalent to bht = 0, proving (c) (d). â€¢ From this proposition, it follows that node-cloning of ay < a w.r.t. 0 node h is equivalent to zero-lifting of its TT-form by > bo w.r.t. h (or, equivalently, node-cloning of â€”by < â€”bo with weight Â£ = 0). Chapter 4. Hamiltonian Path and Symmetric Travelling Salesman Problem 85 We now present the first main result of this section. T h e o r e m 4.16 ( C l i q u e - L i f t i n g with IS*! > 2) Let ay < ao be any nontrivial facetdefining inequality for STSP(V). of ay < a 0 Then, inequality a*y* < aj obtained by clique-lifting w.r.t. any node h is facet-defining for STSP(V U S), whenever \S\ > 2. Proof. By L e m m a 4.14, a*y* < a* is valid. Let V = V \ {h}. Q Let cx < Co and c*x* < CQ be the ^-projections of ay < a and a*y* < a|J, respectively. 0 By L e m m a 4.13, L e m m a 4.14 and P r o p o s i t i o n 4.15, c*x* < CQ is a valid inequahty for HP(V U S) with c^ = Co; c* = c for all e Â£ E(V) and zero otherwise. Let fx* < f e Q be a facet-defining inequality for HP(V U S) that dominates c*x* < cj. (a) Since cx < CQ is nontrivial, for any distinct nodes i,jES and v Â£ V, let (u...v) be a c-tight path on V and (ij...k) be a Hamiltonian path on S. The Hamiltonian cycle C = (ij...fcu...u) on V U 5" satisfies c*(C) = c^. Observe that C \ (i,j) and C \ (i,v) are c*-tight paths, and hence /,â€¢â€ž = /,_,-. Repeating (a) shows that there exists /3 > 0 such that / = 0 for all e Â£ E(5') U E{S : V). e (b) For any c-tight path P on V, there exists an extended c*-tight path P* on V U S containing P. Using (a), it follows that f = /(P*) = f(P) + p\S\ for all c-tight path P on V. 0 Since cx < Co is facet-defining, there exist two scalars a > 0 and 7 such that f = ac + 7 e for all e Â£ E(V). e Next, since cx < CQ is in normal form, there exists e = (p, q) Â£ iÂ£(V) such that c = 0. Let (u...pq...v) be a c-tight path on V and let (ij...k) be a e Hamiltonian path on S. Comparing the two extended c*-tight paths (ij...ku...pq...v) and (q...vij...ku...p) on V U 5 yields 7 = / p ? = /â€ž,â€¢ = By R e m a r k 4.3, fx* < fo is equivalent to c*x* < CQ. The proof is complete by polyhedral equivalence. â€¢ Chapter 4. Hamiltonian Path and Symmetric Travelling Salesman Problem For any nontrivial facet-defining inequality ay < a for STSP(V) 0 86 in ^-normal form, the above lifting result immediately implies that it also induces a facet of STSP(V U S) for all \S\ > 2. We now turn to node-cloning. The following general node-cloning result is due to Naddef and Rinaldi [41], and an alternate (simpler) proof is provided below for completeness. P r o p o s i t i o n 4.17 (Sufficient C o n d i t i o n for N o d e - C l o n i n g ) Let ay < a 0 nontrivial facet for STSP(V), where V = V'\ {h}. and let cx < CQ be its h-projected inequality for define a HP(V), If the condition P C stated in L e m m a 4.11 is satisfied, then a*y* < UQ, obtained by node-cloning of ay < ao w.r.t. h, is facet-defining for STSP(V Proof: Note first that V is c-connected by L e m m a 4.11. /^-projected inequality of a*y* < aâ€ž and fx* < f U {s}). Now, let c*x* < c^ be an be a facet-defining inequality for 0 HP(V U {s}) that dominates c*x* < cj. If nodes u,v E V are c-adjacent, then there exists a c-tight path (u...v) on V. P = (su...v) yields /â€žâ€ž = f . 2 vs scalar /3 such that 0 = f vs Comparing the c*-tight paths P 1 = (u...vs) and Since V is c-connected, we deduce that there exists some for all v Â£ V. Next, since cx < CQ defines a facet of HP(V) and every c-tight path P = (u...v) on V satisfies: /(P) = / ( P U ( V ))-/ M = /o-ft it follows that for some scalars a > 0 and 7, we have f = ac + 7 for all e 6 E(V). The e e rest of the proof is similar to the last part of the proof of T h e o r e m 4.16: since cx < CQ is in normal form, there exists an edge (p, q) Â£ E(V) with Cp = 0. Let (u...pq...v) be a q c-tight path on V. Comparing the c*-tight paths (u...pq...vs) and (q...vsu...p) on FU{s} yields 7 = f pq = f us = fl. Hence, c*x* < cj is equivalent to fx* < fo. The proof is complete by polyhedral equivalence. â€¢ Chapter 4. Hamiltonian Path and Symmetric Travelling Salesman Problem 87 The next result implies that if node h is a clone to some other node, then ay < ao is node-clonable w.r.t. node h. C o r o l l a r y 4.18 (Lifting of C l o n e Pairs) Let ay < a 0 STSP(V) define a nontrivial facet of with a > 0, and suppose that nodes h and t are clones w.r.t. ay < ao. Then the inequality a*y* < OQ for STSP(V U {s}) obtained by node-cloning of ay < a 0 w.r.t. h (or t) is facet-defining. Proof: Let cx < CQ be the /Vprojected inequality for HP(V) w.r.t. V = V \ {h}. ay < a , where 0 Observe that the support graph G (V) contains an isolated node t, C and thus its complement, the zero-graph G {V) is connected. By L e m m a 4.12, V is C c-connected. The proof is complete by Proposition 4.17. â€¢ As an application of Corollary 4.18, consider Theorem 4.12 (i) in Grotschel and Padberg [27]. As any two nodes in their set Z form a clone-pair, their result follows directly from C o r o l l a r y 4.18. The next theorem shows that Naddef and Rinaldi's node-cloning condition in P r o p o sition 4.17 is also necessary. T h e o r e m 4.19 (Necessary and Sufficient Condition for Node-Cloning) Let ay < a 0 be any nontrivial facet-defining inequality for STSP(V). for STSP(V Let a*y* < aâ€ž be an inequality U {s}) obtained by node-cloning of ay < ao w.r.t. node h. Then a*y* < is facet-defining if and only if the following Partition Condition holds: (PC) for every proper partition {U,U'} of the node set V \ {h}, there exists an a-tight cycle C on V containing a 3-node subchain (uhu ) with u Â£ U and u' â‚¬ U'. 1 Proof: Let cx < Co and c*x* < CQ be the /i-projected inequalities of ay < a and a*y* < a|J, 0 respectively. Let V = V \ {h}. Sufficiency trivially follows from Proposition 4.17. Chapter 4. Hamiltonian Path and Symmetric Travelling Salesman Problem 88 Necessity. Suppose that ( P C ) does not hold. Then by L e m m a 4.11(2), there exists a proper partition {U, U'} of V such that no c-tight path on V exists with one endnode in U and the other in U'. Consider any c*-tight path P* on VU{s}. Note that P* has one of the following forms: (su...v); or (u...psq...v). Observe that c(P* D E(V)) = CQ. For the former form, either u, v â‚¬ U or u, v â‚¬ U'; and for the latter, either u, v, p, q Â£ U or u, v, p, q G U'. (Otherwise P* fl E(V) can be extended to a c-tight path on V with one endnode in U and the other in [/', contradicting the supposition above.) In either case, the incidence vector x* of P* satisfies the equality 2x*(E(U\J{s}))+x*(E(U : U')) = 2\U\. It follows that the incidence vectors of all c*-tight paths P* satisfy this equation, which is linearly independent of two other linearly independent equations: c*x* = cj and x*(E(V U {s})) = \V\ (Note that by Proposition 4.15(c), c* = 0 for all e G E({s} : V) since h,s is a clone pair w.r.t. a*y* < ao). This implies that c*x* < c^, and thus a*y* < aâ€ž (by polyhedral equivalence), is not facet-defining. â€¢ As already observed by Naddef and Rinadi [41], such node-cloning operations are repeatedly applicable. Large classes of STSP facets can be obtained in this fashion. This observation is justified by the following theorem. T h e o r e m 4.20 (Repeated N o d e - C l o n i n g and C l i q u e - L i f t i n g ) Let ay < a be any 0 nontrivial facet-defining inequality for STSP(V). Suppose that: (a) ay < ao is node-clonable w.r.t. node h â‚¬ V; and (b) the inequality a*y* < a^ for STSP(V*), any node t E V obtained by clique-lifting of ay < ao w.r.t. where V* = V U S, is facet-defining. Then a*y* < aj is node-clonable w.r.t. any node in {h,t} U 5". Proof: Since any pair of nodes in {i}L)S' forms a clone pair, by Corollary 4.18, a*y* < aj Chapter 4. Hamiltonian Path and Symmetric Travelling Salesman Problem 89 is node-clonable w.r.t. any node in {t} US. If t = h, then we are done. Else we show that a*y* < is node-clonable w.r.t. h, by verifying condition ( P C ) . Consider any proper partition {U, U'} of V* \ {h}. Define a partition {Q,Q'} of V \{h} corresponding to the following two possible Case (1). If neither U nor U' is contained in S, define Q = U\S and Q' = U'\ S. Case (2). W.l.o.g. assume that SCU, and define Q = {t} and Q' = V'\ {h,t}. By (a),(b) and T h e o r e m 4.19, there exists an a-tight cycle C on V containing subchain (uhu') with u G Q and u' â‚¬ Q' (condition ( P C ) ) . In either case, we obtain an a*-tight cycle C* on V* by replacing node t in C with a Hamiltonian path (t...s) on {t} US so that this C* contains (uh'u ) with u G U and u' G V. (Note that for Case (2), 1 u = t.) Hence condition ( P C ) holds w.r.t. node h. â€¢ The condition of the above theorem is weaker than the condition of Theorem 4.9 in Naddef and Rinadi [41], where it is required that every node in V be node-clonable. Consider a proper subset U C V, and suppose that a nontrivial facet-defining inequality ay < a for STSP(V) 0 STSP(V*) is node-clonable w.r.t. every node in U. Let a*y* < be obtained by repeated clique-lifting of ay < a w.r.t. 0 for every node v G V \ U, such that each such node v is replaced by a clique of size greater than two. By T h e o r e m 4.16, a*y* < is facet-defining. Then T h e o r e m 4.20 implies that a*y* < a% is node-clonable w.r.t. any node in V*, but Theorem 4.9 does not. 4.5 Simple C o n d i t i o n s for N o d e - C l o n i n g As condition ( P C ) may be difficult to verify, we present in this section three simple sufficient conditions for node-cloning. The first one may be checked in linear time and seems to apply to all known STSP facets. The second condition, which is verified by Chapter 4. Hamiltonian Path and Symmetric Travelling Salesman Problem 90 visual inspection, generalizes clique-lifting results in Maurras [38], and Grotschel and Padberg [27]. The third condition allows cloning any node in a facet-defining inequality with 0-1 coefficients (a so-called rank inequality). We do not know of any STSP facet that cannot be lifted, based on these simple conditions. Recall that the zero-graph G is the complement of the support graph G associated c c with an HPP inequality cx < CQ. Let ay < ao be any inequality for STSP(V). Definition 4 . E (Condition B(h,d;u)). The inequality ay < ao is said to satisfy con- dition B(h, d; u) with h,d Â£ V and scalar u> > 1 if ay < ao is in /i-normal form with /i-restriction denoted by cx < Co, and if there exists a partition {h, d, U, U'} of V such that: B l . U={veV'\ {h,d} : c dv > 0} and U' = {v Â£ V \ {h,d} : c dv = 0}; B 2 . if U ^ 0, then c < u for all e Â£ E(d : U) and c > u for all e Â£ E(U). e e Note that ay < a in /i-normal form ensures the existence of a partition {h, d, U, U'} 0 satisfying ( B l ) and U' ^ 0, because a = c = 0 for some e Â£ E(V \ {h}). e e Let ay < ao be a star inequality [21], and let a'y < a' be its /i-normal form w^r.t. any Q node h. Then a'y < a' satisfies condition B(h, d; u>) for some properly chosen d. (The hQ normal forms of the star inequalities are easily obtained by appropriately complementing circles and spikes, cf. equation (4.6) and Figure 4.1.) For instance, Fig. 4.1(a) represents the smallest non-comb star inequality. It is easily verified that the inequality in Fig. 4.1(b) (resp., Fig. 4.1(c)) satisfies condition B(h, d;2) (resp., B(h', d';l)). Thus, the following lifting result applies to all facet-defining star inequalities w.r.t. any node. Other known facet-defining inequalities, such as clique-tree, ladder, chain, and crown inequalities, etc., can also be shown to satisfy condition B(h,d;u>) w.r.t. any node h. In fact, we do not even know of any STSP facet-defining inequality whose /i-normal form Chapter 4. Hamiltonian Path and Symmetric Travelling Salesman Problem 91 violates condition B(h,d;u). The following theorem deals with node-cloning of an STSP facet-defining inequality in ^-normal form w.r.t. the isolated node h. This lifting is a special case of zero-lifting. T h e o r e m 4.21 (1-Node Zero-Lifting T h e o r e m ) Let ay < a defining inequality for STSP(V) a*y* < ag for STSP(V U {s}), satisfying condition B(h,d;u). 0 be a nontrivial facet Then the inequality obtained by node-cloning of ay < ao w.r.t. h, is facet- defining. Proof: Let V = V \ {h}, let cx < CQ denote the ^-restriction of ay < ao. Let {U, U'} be a partition of V \ {h, d} as required in condition B(h, d; oS). First, using ( B l ) , U' 0 {d} induces a connected subgraph of the zero-graph G (V), C and thus by L e m m a 4.12, U' U {d} is c-connected. Next, since cx < Co is nontrivial, for any w G U, there exists a c-tight path on V of the form P = (w...t). If t G U' U {d}, then w is c-adjacent to some node in U' U {d}. Otherwise t G U and P has the form (w...udv...t). This implies that u G U (since otherwise c ud = 0 by ( B l ) and Hamiltonian path P' = (u...wt...vd) satisfies c(P') > Co), and therefore by (B2), we have c ut > Cuj. Hence, (w...ut...vd) is a c-tight path on V and w is c-adjacent to d. It follows that V is c-connected. The proof is complete by Proposition 4.17 and polyhedral equivalence. â€¢ In some applications, it is more convenient to apply node-cloning to an STSP facetdefining inequality, not in /i-normal form. In the sequel, we discuss sufficient conditions for such node-clonings. These conditions can be checked directly by visual inspection, using closed form representations. Definition 4.F (w-regular node). Node h G V is w-regular w.r.t. ay < a if u > 0 0 and there exists a proper partition {h, Q, Q'} of V such that ahv = 0 for all v G Q'. = u for all v G Q and Chapter 4. Hamiltonian Path and Symmetric Travelling Salesman Problem 92 T h e o r e m 4.22 (cj-Regular N o d e - C l o n i n g ) Let ay < a define any nontrivial facet 0 of STSP(V) with a > 0. Suppose that node h is u-regular w.r.t. the partition {h, Q, Q'}. Let V = V \ {h}. Suppose also that one of the following conditions is satisfied. (i) Q = {d}; there exists a node v' G Q' such that ad > = 0 andadv < <*> for all v G Q'\{v' v (ii) For all e G E(Q) ^ 0, a > u; there exists a node d G Q such that ad < UJ for all e v v G V \{d}. (iii) There exists an edge e = (z, j) G E(Q) such that a eeE(Q)UE{Q = 0 and a e e < u for all :Q'). Then the inequality a*y* < aj, obtained by node-cloning of ay < ao w.r.t. node h, defines a facet of STSP{V U {a}). Proof: Let a'y < a' be the /i-normal form of ay < ao and cx < CQ be the /i-restriction of Q a 'y ^ 'o- Note that a*y* < a^ is equivalent to the inequality obtained by node-cloning a of a'y' < a' w.r.t. h. We thus need only prove that a'y' < a' is node-clonable w.r.t. h. 0 0 Note also that V = Q U Q'. Case (i). Note first that clique weight Â£ = a\ = ahd + ah < â€” a<ftv = s U = {v G V \ {d} : c dv Define v > 0} and U' = {v G V \ {d} : c dv = 0}. Then a'y' < a' satisfies 0 condition B(h, d; u>). Case (ii). Note first that clique weight Â£ = a Â£ = ahd + ah â€” ad =u s v v for any v E Q\ {d}. Observe that, in this case, a'y' < a' may be obtained by complementing set Q U {h}, cf. Q equation (4.6). Thus, ' a -u, e a +u, e G E(Q'); a otherwise. e Also observe that (ii) implies a<fâ€ž = (ii), we have that c dv e G E(Q\J{h}); e and thus e dv < w for all u G <5', and c >u e (4.8) = 0, for all v G Q \ {d}. Further by for all e G E(Q'). Hence, condition Chapter 4. Hamiltonian Path and Symmetric Travelling Salesman Problem B(h,d;u) also holds w.r.t. a'y' < a' and a partition {h,d,U,U'}, 0 93 where U C Q'. The proof for Cases (i) a n d (ii) is complete by T h e o r e m 4.21. Case (iii). Note that clique weight Â£ = aÂ£ = a^,- + a^- â€” a,j = 2u>. Also observe that: a (01) ce < u for all e G E(Q); and (02) u < c < 2u for all e G E(Q : Q'), and c >2u e for all e G E(Q'). e (1) We show first that Q is c-connected. It suffices to show that for any proper partition {Z', Z"} of Q, there exists a c-tight path on V with one endnode in Z' and the other in Z". Fix w G Q' and let P = (w...v) be a c-tight path on V. Consider the following two possible cases. (l.a) If v G Q'i then by (02), c ^ > 2u>. Therefore P contains no edge e* with c . < 2u> e (since otherwise c(P U {(w, v)} \ {e*}) > Co). Therefore, by (01), P contains no edge in E(Q), and P has the general form (w'...z'p...qz"...w"), where {u/, tu"} = {w, u}, z' G Z', z" G Z " and p,o G Q'. It follows from (01) and (02) that c i + c ii >2u> w p qw c i + c Â». z p qz Thus (z'...w'p...qw"...z") is a c-tight path with z' G Z ' and z" G Z " . (l.b) If v G assume w.l.o.g. v G Z'. Then P has the general form (w...z"u...v) for some z" G Z " . By (01) and (02), we have c ^ > c Â« for either u eQ or u eQ'. Thus, 2 (Z"...UJU...U) is a c-tight path with v G Z' and 2;" u G Z". (l.a) and (l.b) shows that Q is c-connected. (2) We now show that every node w G Q' is c-adjacent to some node in Q. In doing so, we consider a c-tight path on V: P = (iu...u) as in (1) above. If v G Q, we are done for node w. Otherwise, v G Q', and P has the general form (w...pz...v) for some z G As in (l.a), P contains no edge in E(Q), and thus p G C?'- Hence, by (01) and (02), we have c pv > Cp , implying that (w...pv...z) is a c-tight path on V. 2 From (1) and (2), it follows that V is c-connected. The proof of Case (iii) is complete by Proposition 4.17 and by polyhedral equivalence. â€¢ Chapter 4. Hamiltonian Path and Symmetric Travelling Salesman Problem 94 We first observe that Maurras' clique-lifting result (Prop.l, pp.188, [38]) is a special case of T h e o r e m 4.22(ii) (and also a special case of T h e o r e m 4.24 below). Next, T h e o r e m 4.22 (i) and (ii) generalize Theorem 4.12 (ii) in Grotschel and Padberg [27] (Using Z = {h}). Finally, observe that T h e o r e m 4.22 (iii) implies Theorem 5.10 in [27]. As examples, we apply w-regular node-cloning to two new facets in Fig. 4.2(a) and Fig. 4.3(a). (These inequalities were proven by the authors to be facet-defining, using the projective approach). Applying T h e o r e m 4.22 (ii) and (iii) successively to nodes h and h' in Fig. 4.2(a), we obtain a new STSP facet in Fig. 4.2(b). Applying T h e o r e m 4.22 (i) to node h in Fig. 4.3(a) yields a new facet of STSP{V) with \V'\ = 10 in Fig. 4.3(b). These new facets cannot be generated by the clique-lifting results of Maurras, or Grotschel and Padberg. < 17 < 20 few n, s (a) A primitive binested inequality (b) A lifted binested inequality Figure 4.3: Facet-defining binested inequalities Now, we make use of the above result to derive our third main lifting result, rank inequality lifting. We first show an intermediate result. P r o p o s i t i o n 4.23 (Zero-Lifting for 0-1-Inequalities i n /i-normal form) Let ay < a define a nontrivial facet of STSP(V) 0 all e 6 E(V), where V = V \ {h}. in h-normal form. Assume that a Â£ {0,1} e for Then the inequality a*y* < a^, obtained by node- cloning (zero-lifting) ofay < ao w.r.t. h, defines a facet of STSP(V U{Â«}). Chapter 4. Hamiltonian Path and Symmetric Travelling Salesman Problem Proof: Let cx < CQ be its /i-restriction on HP(V). 95 By P r o p o s i t i o n 4.17, it suffices to show that V is c-connected. Suppose that V is not c-connected. Then by L e m m a 4.11(2), there exists a proper partition {U, U'} of V such that there exists no c-tight path on V with one endnode in U and the other in U'. If = 0 for some (u, u') Â£ E(U : U'), then let (p...uu'...q) be a c-tight path containing (u,u') (since cx < CQ is nontrivial). As Cp > 0 = c ^ i , (u...po...u') q is another c-tight path, contradicting the supposition. Therefore, we must have c = 1 e for all e Â£ Â£ ( Â£ / : {/'). Assume w.l.o.g. that \U\ < \U'\. Since cx < CQ is nontrivial, for any u Â£ (7, there exists a c-tight path P = (u...v) on F . If v 6 immediate. So consider v Â£ U. Since a contradiction is < \U'\, P contains at least one edge in E(U'). Thus, P has the general form (u...pq...v) with p,q Â£ E(U'). A contradiction is produced by defining a c-tight path (u...pv...q) (since Cp = 1 > c ). This shows V is c-connected. V pq â€¢ Recall (pp.282, [28]) that an STSP rank inequality is a valid STSP inequality ay < a with a Â£ {0,1} e 0 for all e. T h e o r e m 4.24 ( N o d e - C l o n i n g for R a n k Inequalities) Let ay < a be a facet-defining 0 rank inequality for STSP(V). Then the inequality a*y* < aj, obtained by node-cloning of ay < ao w.r.t any node h, is facet-defining for STSP(V Proof: Let V = V \ {h}, U {s}). Z = {v Â£ V : {h, v) Â£ E'} and W = V \ Z. If Z = 0, the result holds immediately by Proposition 4.23. If W = 0, we add the degree constraint â€”y(S(h)) = â€”2, and thus Proposition 4.23 also applies. If both of the above sets are nonempty, then node h is 1-regular and the result follows by T h e o r e m 4.22 (by (iii) if a = 0 for some e Â£ E(Q); and by (i) or (ii) otherwise). e â€¢ With the above result and T h e o r e m 4.20, one may obtain large new classes of Chapter 4. Hamiltonian Path and Symmetric Travelling Salesman Problem 96 STSP facets from rank inequalities. For instance, these liftings can repeatedly apply to rank inequalities of Fig. 4.2(a), the Petersen graph, primitive chains, clique-trees, etc. Thus, to show that a general clique-tree is facet-defining, it suffices to consider the corresponding primitive clique-tree. Another consequence is that lifted rank inequalities are again clique-liftable w.r.t. any node. In conclusion, we remark that the Hamiltonian path approach facilitates the STSP polyhedral study. By exploiting the near-full dimensional property of HP(V) and the polyhedral equivalence between HP(V) and STSP(V), we obtain simpler polyhedral proofs for STSP facetial results, as well as stronger lifting results for extending STSP facets than the results from the other approaches. This approach also applies to: â€¢ simple composition methods for extending STSP facets. â€¢ the polyhedral study of asymmetric travelling salesman problem. See C h a p t e r 5. â€¢ the polyhedral study of other related problems, such as vehicle routing problems [2],[14]. Chapter 5 Symmetric Inequalities for Asymmetric Travelling Salesman Polytopes In this Chapter, the Hamiltonian Path approach developed in Chapter 4 extends to the polyhedral study of Asymmetric Travelling Salesman (ATS) polytopes. By a Tree Com- position technique, we obtain a large new class of symmetric facet-defining inequalities for ATS polytopes. 5.1 Introduction Let D(V) = ( V , A(V')) be a complete directed graph, where the node set V represents a set of cities. A feasible solution to the Asymmetric Travelling Salesman (ATS) problem is a Hamiltonian cycle C on V, uniquely determined by its corresponding 0-1 incidence vector y E R ^ '^ (where y = 1 if edge e is used in C and zero otherwise). This chapter A V e studies the ATS polytope ATSP(V), the convex hull of incidence vectors y of all feasible solutions to the ATS problem. Over the past decade, substantial knowledge has been gained on the facial structure of ATS polytopes. Grotschel and Padberg [28] introduced several classes of valid inequalities, such as the D%, D\~, C3, C2 inequalities, and proved some of these to be facet-defining. Fischetti [17] later proved that all these, as well as the directed version of Comb inequalities, are facet defining, except for the 6-node comb. Balas [4], and Balas and Fischetti [5,6] used relaxation methods and a general node lifting technique to derive large new classes of facet-defining inequalities, called CAT, FDA and SD inequalities. Very recently, Fischetti [18] has shown by an inductive proof technique that the directed 97 Chapter 5. Symmetric Inequalities for Asymmetric Travelling Salesman Polytopes 98 version of the Clique Tree Inequalities, is also facet-defining for ATS polytopes. Grotschel and Padberg [28] addressed some interesting relationships between STS and ATS polytopes. To any given valid STSP inequality EKi^.ieV,kj}<Â«o, (5-1) which we write in short a'y' < a' , corresponds a unique directed version 0 Y,{ ayij V'i* ^ J"} < Â«o, a (5.2) in short ay < ao, for the corresponding ATS polytope, where ao = a' , and a,j = aj,- = a\j 0 for all i,j G V, i < j. Thus, we say that an ATSP inequality ay < ao is a symmetric inequality if it is the directed version of some STSP inequality a'y' < a' . Conversely, Q any symmetric ATSP inequality ay < a yields an undirected version a'y' < a' for the 0 Q corresponding STS polytope. It is easy to observe that an inequality a'y' < a' is an STSP 0 valid inequality if and only if its directed version ay < a is an ATSP valid inequality. 0 An important question raised by Grotschel and Padberg [28] is "whether or not the directed version ay < ao of an STSP facet-defining inequality a'y' < a' is also ATSP 0 facet-defining." Conversely, as observed in Fischetti [18], the undirected versions of all symmetric ATSP facet-defining inequalities induce facets of STS polytopes. The study of symmetric ATSP facet-defining inequalities thus has some theoretical importance. To date, the largest known class of symmetric ATSP facet-defining inequalities is the directed version of the famous Clique Tree class, which subsumes all previously known symmetric ATSP facet-defining inequalities, see Fischetti [18]. There are three major motivations for the present work. First, and as mentioned above, in addition to its theoretical interest, the study of symmetric ATSP inequalities is of practical importance: we expect that the cutting plane-based solution procedures that have been so successful in solving large scale STS problems will be adapted to ATS Chapter 5. Symmetric Inequalities for Asymmetric Travelling Salesman Polytopes 99 problems. In this respect, we feel that the symmetric ATSP facet-defining inequalities deserve further study, in particular because STSP separation heuristics also apply to ATSP symmetric facets. Second, large classes of valid inequalities, such as Naddef and Rinaldi's Regular Path Trees, Boyd and Cunningham's Ladders, and Padberg and Hong's Chains, etc., were shown to be STSP facet-defining in recent years [42]. It is of interest to know when the directed versions of these large classes are also ATSP facet defining. Finally, known classes of STSP facet-defining inequalities were extended by various composition methods, see Naddef and Rinaldi [44]. A composition approach is also introduced here for ATS polytopes and is used to generate large new classes of symmetric ATSP facet-defining inequalities. Two major difficulties arise when directly studying ATS polytopes: (i) these are quite far from being full dimensional polytopes, due to the degree constraints; and (ii) Hamiltonian cycles and circuits are rather cumbersome objects to work with. These difficulties complicate the (indirect) proofs that stated valid inequalities are facet-defining. In an indirect proof that valid inequality cx < CQ is facet-defining for a given polyhedron V, one aims at showing that any valid inequality fx < fo that dominates cx < CQ (i.e., such that fx = f whenever cx = CQ, for all x E V) must be equivalent to cx < CQ. This 0 amounts to showing that fx < fo can be obtained as a linear combination of implicit equations for V (equations satisfied by all x E V) and a positive multiple of cx < CQ. If there are several linearly independent implicit equations for V, as is the case for STS and ATS polytopes, the indirect proofs tend to be difficult. In addition, the cumbersomeness of Hamiltonian cycles or circuits manifests itself when trying to determine the structure of such dominating inequalities fx < f . 0 The components of / are usually determined by comparing c-tight solutions (Hamiltonian cycles or circuits whose incidence vector x satisfies cx = CQ), which differ from each other in as few components as possible. Indeed, Chapter 5. Symmetric Inequalities for Asymmetric Travelling Salesman Polytopes 100 two distinct Hamiltonian circuits differ by at least six edges (the so-called 3-opt interchange). The resulting conditions on the components of vector / then involve at least six components and are thus quite unwieldy. Various relaxation methods were proposed to overcome these difficulties, most notably (i) the Monotone ATSP approach (see Grotschel and Padberg [28] for a recent survey), and Fischetti [17]) and Graphical ATSP approach introduced by Chopra and Rinaldi [10]. The corresponding objects, edge-subsets of Hamiltonian cycles/circuits, and tours, respectively, are much more manageable than Hamiltonian cycles/circuits. Unfortunately, it is not easy to convert MATSP and GATSP facetial results into corresponding ATSP results. The Hamiltonian Path approach, introduced in C h a p t e r 4, can be extended to the polyhedral study of ATS polytopes. This approach uses an Asymmetric Hamiltonian Path (AHP) formulation and thus also relaxes the degree constraints. For any arbitrary node h Â£ V, let V = V \ {h}. Let A (resp., A') denote the edge set of the complete digraph on node set V (resp., V ) . The Asymmetric Hamiltonian Path polytope AHP(V) C R A is the convex hull of incidence vectors of all Hamiltonian paths (with free endpoints) on node set V. We show that polytope AHP(V) is a projection of ATSP(V) R of R '. This projection has two fundamental properties: AHP(V) A A onto subspace has full dimension minus one (with a single implicit equation ]C x = \V\ â€” 1); and the polyhedral structures e of AHP(V) and ATSP(V) e are equivalent. We are led to prefer the AHP approach for studying ATS polytopes to the MATSP or GATSP relaxations, for three main reasons which follow mostly from the above two properties. First, the (indirect) proofs for the AHP polyhedral results are almost as easy as in the full dimensional case, because the single implicit equation is easily dealt with. Second, all polyhedral results for trivially extend to ATSP(V), AHP(V) due to their polyhedral equivalence. Finally, we found that Hamiltonian paths are much easier to work with than Hamiltonian circuits, in particular Chapter 5. Symmetric Inequalities for Asymmetric Travelling Salesman Polytopes 101 Â» when comparing solutions in indirect proofs, as two distinct Hamiltonian paths may differ in a single pair of edges. The present paper is organized as follows. In Section 5.2, we introduce definitions and notation. In Section 5.3, we establish the main properties of ATSP(V) AHP(V), and its projection and then develop a projective approach for the ATS problem. In Section 5.4, we show that some known classes of STSP facet-defining inequalities, such as Path, Wheelbarrow, Envelope, Ladder and Chain Inequalities, induce symmetric ATSP and AHP facet-defining inequalities. The derivations are based on the projective approach, along with a S y m m e t r i c D o m i n a n c e L e m m a . In Section 5.5, we propose a Tree Composition of symmetric inequalities. This composition generates a large class of symmetric facetdefining inequalities for ATS polytopes, called ATSP Tree Inequalities, which generalize the directed versions of non-spanning Clique Tree Inequalities and Regular Path Tree Inequalities. Furthermore, the proposed Tree Composition may also be used to derive a large new class of STSP facet-defining Tree Inequalities. Figures 5.1- 5.5 herein present examples of new ATSP facets. The proofs of the main results in Sections 5.4 and 5.5 are provided in Sections 5.6 and 5.7, respectively. 5.2 Definitions and N o t a t i o n Most of the notation and terminology below follow from [5] and [28]. Let D(V) = (V, A) denote the complete (loop-free) digraph on n = \V\ nodes, where (5.3) A={(i,j)-.iev,jev\{i}}. Hereafter, we assume n > 3. Digraph D(V) contains ra = |A| = n(n â€” 1) edges. For any two subsets Vi, V of V, define 2 (V :V ) = 1 2 {(i j)eA:ieV J ev }. 1 1 2 (5.4) Chapter 5. Symmetric Inequalities for Asymmetric Travelling Salesman Polytopes 102 If Vi = V , (Vi : Vi) is denoted by A(Vi). Thus, A = A(V). A singleton set {v} is 2 denoted by v whenever convenient without causing confusion. Let S (v) = (v : V) and + S~(v) = (V : v) denote the out-star and in-star of node v, respectively. For complete undirected graph (V,E(V)) and any subsets Vi,V2 C V, the edge sets Â£(Vi : V ) = {(i,j) G E(V) : i e V j e V } 2 u = E(V : V ) and E{V ) = E(V : Vi) are 2 2 x X X similarly defined. A partial graph (S, A) of D(V) is a digraph with S C.V and AQ A. The incidence vector of the partial graph (V, A) of /^(V) is the vector y G R such that y = 1 if e G A A e and y = 0 otherwise. For any vector x ^ i?" and A C A, let 4 e X(A) = E x . - (5-5) For simplicity, let X (S : T) = ((S : T)) and X X (S) = (A(S)), X V5, T C V. (5.6) For any 5 C V, a Hamiltonian circuit C on 5 is a connected partial graph (5, A) such that \A n ^ (i;)| = \A D r (u)| = 1 for all w G S. + By definition, the incidence vector y of any Hamiltonian circuit C on V thus satisfies c the following degree constraints: y (6 {v)) = y (6-(v)) = 1, c + c for all v G V. Without risking confusion, a Hamiltonian circuit C with edge set A â€” on node set S = {v ,u } x s ui)} U {(u,-, v ) : i = i+1 1 , s - l } C V may be represented by edge set A alone or, equivalently, by the circular permutation (ui...u ) of the nodes in 5". s Chapter 5. Symmetric Inequalities for Asymmetric Travelling Salesman Polytopes 103 A Hamiltonian path P on S = {t>i,v } C V is a connected partial graph (S, A) such s that for some distinct i,j G S , (5, iu{j,j}) defines a Hamiltonian circuit on S. Note that 1 the endnodes of P are not specified in advance, i.e., we consider here P with free endnodes. Hamiltonian path P may be represented as the edge set {(Â«,-, u,+i) : i = 1 , s â€” 1} or, equivalently, as its corresponding node permutation (vi...v ). Note that if l^l = 1, the a first form is an empty set, whereas the second form reduces to a single node (vi). Note also that whenever a subchain of a Path is written in the form u...u,we allow the subchain to be a singleton, i.e., u = v. For any node set S, the ATS polytope ATSP(S) (resp., AHP polytope AHP(S)) is the convex hull of the incidence vectors of all Hamiltonian circuits (resp., Hamiltonian paths) on the complete (loop-free) digraph (S,A(S)): ATSP(S) = conv{y G R AHP(S) = conv{x G R Recall that STSP(S) c p : C is a Hamiltonian circuit on S}, A{S) : P is a Hamiltonian path on S}. A{S) (resp., HP(S)) is the convex hull of incidence vectors of the undirected Hamiltonian circuits (resp., undirected Hamiltonian paths) in a complete undirected graph K(S) = (S,E). STSP(S) (resp., HP(S)) counterpart ATSP(S) Note that the number of variables defining polytope is half of the number of variables defining its asymmetric (resp., AHP(S)). Let ay < ao and cx < CQ be any valid inequalities for ATSP(S) and AHP(S), respectively. An a-tight circuit C (resp., a c-tight path P) on S is a Hamiltonian circuit (resp., a Hamiltonian path) on S such that ayÂ° = a (resp., cx 0 p = CQ). Chapter 5. Symmetric Inequalities for Asymmetric Travelling Salesman Polytopes 5.3 104 T h e A T S P o l y t o p e and its Projection For any fixed node h G V , let V = V \ {h} and n = |V|. Consider two complete (loop-free) digraphs: D(V) = (V,A) where A' = A U {(v,h),(h,v) and : v e V}. = ( V , A'), D(V) That is, D(V) is obtained from D(V) by eliminating node h G V and all incident edges. Let A T 5 P ( V ) be the ATS polytope , defined on D(V), and AHP(V) be the AHP polytope defined on D(V). Observe that P is a Hamiltonian path on V from node u to node v iff C = P U {(h, u), (u, Ji)} is a Hamiltonian circuit on V. Thus, incidence vector x vector y c G onto subspace R projection of ATSP(V). vertices of ATSP(V) A of P ' . p GR A is a projection of incidence It follows that polytope AHP(V) A is a Moreover, there is a one-to-one correspondence between the and those of AHP(V). This correspondence will be shown to be affine-rank preserving. Associate two n X n(n â€” 1) matrices, A~ and A , to complete digraph D(V) as follows. + For all v G V and e G A, let ,4~ = 1 if e G (V : v); i.e., if u is the head of edge e; and e zero otherwise. Similarly, let A+ = 1 if e G (v : V), i.e., if v is the tailoi edge e; and zero e otherwise. Thus, A~ (resp., A ) is the tail (resp., head) node-edge incidence matrix of + D(V). By definition, the incidence vector y G R c and its projection x p GP A A> of any Hamiltonian circuit C on V satisfy the following identity: (u,u)GA; 1 - E e ^ A ^ f , (u,t;)â‚¬(fc:n Throughout the paper, we assume, unless otherwise noted, that â€¢} x G P A is a projection of y G P" '; and 4 (5-7) Chapter 5. Symmetric Inequalities for Asymmetric Travelling Salesman Polytopes 105 â€¢ V= where m = n(n- (y*,--,Ve ,yhv ---,yhv ,yv H,---,yvj ) , m 11 n 1 t i 1), t G A for all x / = 1 , m , and v\ G V for all / = 1 , n . L e m m a 5.1 Let B = [y , â€¢â€¢â€¢,?/'] &e <mj/ matrix such that all columns y are incidence 1 y 3 vectors of Hamiltonian circuits on D(V). Let matrix B == [ x , x ] , where x is the 1 x l 3 projection of y onto R , j = 1,...,/. Then, the number of affinely independent columns 3 A in By is equal to the number of affinely independent columns in B . x Proof. From (5.7), it follows rank 1* > rank B x / 1 > rank \ 0* I 0 1 -A- 1 -A+ ) = rank I I t where 0 (resp., 1) is a vector of zeroes (resp., ones) and I is an identity matrix, all of conformable dimension. Hence, equality must hold throughout. This completes the proof. T h e o r e m 5.2 The dimension of AHP{V) â€¢ is dim(AHP(V)) = n(n - 1) - 1, (5.8) where n = \V\ > 2. Proof. For n = 2,3,4, equation (5.8) follows from enumerating all possible corresponding Hamiltonian paths. Let n > 5. First, observe that for any Hamiltonian path P on V, we have ^ ^ A x = n â€” 1. Therefore, e P dim(AHP(V)) < n(n - 1) - 1. Chapter 5. Symmetric Inequalities for Asymmetric Travelling Salesman Polytopes 106 Next, let fx = fo be any equality satisfied by the incidence vectors x of all Hamiltonian paths on V. Let e and e' be any two edges in A(V) with distinct endnodes. Then, there exists a Hamiltonian circuit C on V containing both e and e'. Comparing Hamiltonian paths C\e and C\e' yields: 0 = fx<* - fx^' = f , - /.. e As n > 5, repeating the above argument to all pairs of non-adjacent edges implies that fx < fo is a multiple of x(V) = n â€” 1. â€¢ The dimension of the ATS polytope is described in Grotschel and Padberg [28]. The following is an alternative and simple derivation of this result. C o r o l l a r y 5.3 The dimension of ATSP(V ) 1 dim(ATSP(V')) is = n(n + 1) - 2(n + 1) + 1, (5.9) where \V'\ = n + 1 > 3. Proof. Follows directly from L e m m a 5.1 and T h e o r e m 5.2 by noting that n ( n - l ) - l = n(n + l ) - 2 ( n + l) + l . â€¢ Now, we turn to relationships between valid inequalities for ATSP(V) and for AHP(V). Consider any two inequalities ay < ao and cx < Co, defined on ATSP(V) AHP(V), respectively, and satisfying: a = Co; 0 a = c> e e 0, Ve G A; and a = 0, e and Ve G (h : V) U (V : h). We then say that inequality ay < ao has an isolated node, that ay < ao is an extension of cx < Co, and that cx < Co is a restriction of, or a projected inequality for, ay < ao w.r.t. node h. By L e m m a 5.1 and T h e o r e m 5.2, we have immediately: Chapter 5. Symmetric Inequalities for Asymmetric Travelling Salesman Polytopes 107 Theorem 5.4 (Polyhedral Equivalence) For any k such that 0 < k < n(n â€” 1) â€” 1, inequality ay < ao with an isolated node defines a k-dimensional face of ATSP(V) its restriction cx < CQ defines a k-dimensional face of iff AHP(V). The above result may also be derived by an application of Remark 4.2 of [27]. By appropriate scaling, the inequality ay < ao with an isolated node is in h-canonical form and its corresponding restriction cx < CQ is a AHP canonical inequality. A-canonical form (Balas and Fischetti [5]) An inequality ay < a for ATSP(V) 0 is in canonical form with respect to a given node h G V (/i-canonical form, for short) if (Cl) a vh = a hv = 0 for all v G V = V \ h; (C2) a > 0 and a = 0 for some e G A = A(V); e (C3) the coefficients a are relatively prime integers. e A H P Canonical Inequality Inequality cx < CQ for AHP(V) is a canonical inequality, or in canonical form, if the coefficients c satisfy conditions (C2) and (C3) above. e It is shown in [5] that any valid inequality for ATSP(V) has a unique ^-canonical form. This uniqueness property also follows directly from Theorems 5.2 and 5.4 by observing that conditions (C2) and (C3) may be imposed on the restriction cx < CQ by using the unique implicit equation x(V) = n â€” 1 for AHP(V), followed by an appropriate positive scaling. Following the results in [28] and the polyhedral equivalence, trivial facets of ATSP and AHP polytopes are defined as follows: Trivial Facets Inequality ay < ao (resp., cx < Co) defines a trivial facet of (resp., AHP(V)) e G A(V)). ATSP(V) if it is equivalent to y > 0 (resp., x > 0) for some e G A' (resp., e e Chapter 5. Symmetric Inequalities for Asymmetric Travelling Salesman Polytopes 108 From now on, we will work with symmetric inequalities, in canonical form for AHP( V), and in ^-canonical form for ASTP(V), i.e., with an isolated node h readily identified, for the following reasons. First, the projections of these inequalities ay < ao with respect to isolated node h are in fact the restrictions cx < CQ of ay < a . Consequently, the "struc0 tural" definitions of inequalities, such as Comb, Clique Tree, etc., ay < a for Q directly apply to cx < Co for AHP(V \ h) as well. Next, it follows immediately from T h e o r e m 5.4 that ay < a defines a facet of ATSP(V) 0 AHP(V ATSP(V) iff cx < Co defines a facet of \ h). So, no additional work is needed to recover one inequality from the other. Finally, the ATSP facet composition results are relatively easier to obtain, as is the case for 2-SUM GTSP facet compositions of Naddef and Rinaldi [44]. The proposed ATSP facet composition in Section 5.4 requires that all composing inequalities be in h-canonical forms. The facet-defining inequalities given as examples in Figures hereafter are for ATS polytopes and are all in /i-canonical form, unless otherwise noted. 5.4 S y m m e t r i c Facet-defining Inequalities In this section, we study three classes of symmetric inequalities: Regular Star, Chain and Ladder Inequalities. Of particular interest are these inequalities in "nice" /i-canonical form, i.e., with an isolated node. Their undirected versions are known to be facet-defining for STS polytopes. For STS polytopes, the inequalities in the first class was introduced as the Path Inequalities, along with variations, the Wheelbarrow and Bicycle Inequalities, by Cornuejols et al. [13]. They were called Regular Star Inequalities by Fleischmann [21] and shown to be STSP facet-defining by Naddef and Rinaldi [42]. The second class was introduced by Padberg and Hong [47] and shown to be STSP facet-defining by M . Hartmann and by S. Boyd (cf. Naddef and Rinaldi [41]). The Ladder Inequality was introduced and proven to be STSP facet-defining by Boyd and Cunningham [8]. We will Chapter 5. Symmetric Inequalities for Asymmetric Travelling Salesman Polytopes 109 show by projection that the Path, Wheelbarrow, Envelope, Ladder and Chain inequalities induce facets of ATS polytopes as well. A closed form representation for inequalities ay < ao is used in the Figures hereafter, where a collection of node subsets with positive weights (numbers) are given. Then, each coefficient a,j equals the total weight of all the subsets which contain both nodes i and j. All set weights of value one are omitted for simplicity. Whenever necessary, nodes are labeled with letters or italic numbers. A hollow circle g denotes an optional node, i.e., node g may or may not be present. If the right hand side of an inequality with node g is different from that without g, then the former is also indicated in parentheses. Figure 5.1 gives such a representation. Some of the resulting coefficients in the represented ATSP inequality are b[b' = , a 2 3 a b{bi = ' 4 a tj&Â£ = ' 4 a 6j6j = Â°> e t C - and the right hand side a = 44 if node g is absent, a = 48 if present. 0 0 ^12 b 3 m4.f*l2 v < 44 (48) 2 â€¢h Figure 5.1: An ATSP Regular Star Inequality Balas and Fischetti [6] recently proposed a powerful node lifting result for ATSP facets, Chapter 5. Symmetric Inequalities for Asymmetric Travelling Salesman Polytopes 110 called Clique-Lifting. This result implies that a class of ATSP inequalities are facetdefining if all the primitive inequalities in this class are facet-defining (cf. Fischetti [17] for the definition of a primitive inequality). Therefore, it suffices to consider ATSP inequalities in primitive form. In the sequel, all inequalities are introduced in primitive form. We now introduce primitive Star Inequalities for ATSP(V). F i g u r e 5.1 presents an example. Given are proper subsets of V as follows: N nested circles, A\ D A D ... D AN; 2 and an odd number s > 3 of disjoint spikes, B , B ,B", 1 where, for all i, B consists 2 % of nodes &}, j â€” 1,ra,- such that 6J,. â‚¬ AN and b\ (EV \ A\. Moreover, assume that for every i, inequality,;' < / implies that there is no q such that (E A and b\ A . Let M(v) q q denote the number of circles A containing node v. With each spike B associate a spike % q weight JV,- such that JV,- > M(b) ) - M(b)) for all 1 < j < ra, - 1 (cf. Fleischmann [21] +l for details). Then, a primitive Star Inequality ay < ao for ATSP(V) Â£y{A ) + Â£/%(Â£Â«) q 9=1 < Â£\A \ q g=l Â«'=1 is defined by v+JEL. + Â£iv,(|PÂ«| - 1 ) Â«=1 (5.10) Z Let a'y' < a' be the undirected version of inequality (5.10) for STSP(V). Q By adding to a'y' < a' proper multiples of the following valid equations (obtained from the degree 0 constraints): 2y\S) + y'(6(S)) = 2\S\, for all S â‚¬ {A A , B\ u N BÂ°], we obtain Â£ y'(Â«K)) + Â£ 9=1 NrfMl?)) > 2 Â£ Â»'=1 which is the Star Inequality for STSP(V) N + (s + 1)N, q (5.11) 9=1 in Fleischmann's form [21]. When Ni = M(6} ) â€” M(bj) for all i and j, inequality (5.10) represents a Regular +1 Star Inequality. If N = 1 and all spike weights Ni = 1, inequality (5.10) reduces to Chapter 5. Symmetric Inequalities for Asymmetric Travelling Salesman Polytopes 111 a Comb Inequality [28]. Hence, the Regular Star class properly generalizes the Comb class. Figure 5.1 presents a Regular Star Inequality with four circles and five spikes, i.e., a 5-Star (equivalently, a Path Inequality with five "paths"), in ^-canonical form. It reduces to a 3-Star if the spikes in the dash-box are removed. By definition, the spike weights for B*, B and the leftmost spike in the dash-box are 2, 4 and 2, respectively. 3 Recall that all other set weights are equal to one. A Path Inequality includes both nodes h and g, whereas a Wheelbarrow Inequality (resp., Bicycle Inequality) excludes node g (resp., excludes both nodes h and g). If node g exists, then the right hand side needs to be properly adjusted according to (5.10). If a Regular Star is not a Bicycle Inequality, its restriction cx < CQ is in canonical form for AHP(V), and reads: 5>04r) + LN z(B ) y i 9=1 i Â»'=1 < Â£\A \ q g=l + EAr,(|^'| - 1) Â»"=1 (5.12) Z T h e o r e m 5.5 Primitive Path and Wheelbarrow Inequalities (resp., their restrictions) are facet-defining for ATSP(V) (resp., AHP(V)). The proof of T h e o r e m 5.5 is given in Section 6. The ATSP Bicycle Inequalities do not have such nice ^-canonical forms. The smallest non-comb Bicycle Inequality, also called the Envelope Inequality by Boyd and Cunningham, is given in Fig. 5.2(a). An /i-canonical form of the Envelope Inequality is presented in Fig. 5.2(b). Fig. 5.2(c) represents the Ladder Inequality. Recall that node g is optional. Fig. 5.2(d) is itsfo-canonicalform. Note that these /i-canonical forms are obtained by replacing all non-empty subsets containing node h with their complements. In Fig. 5.2(b) and (d), italic numbers are used to label the nodes for convenience in proving the next theorem. (The other numbers are set weights.) If node g exists, an alternative simple hcanonical form for Fig. 5.2(c) is Fig. 5.2(c) itself by exchanging nodes h and g. We choose Chapter 5. Symmetric Inequalities lor Asymmetric Travelling Salesman Polytopes 112 the form in Fig. 5.2(c), because it is convenient for showing that the Ladder Inequality is facet-defining for ATSP{V) c â€¢ â€¢ â€¢ 3 â€¢ A â€¢ 5 â€¢ 6 â€¢ 2 for |V'| = 8,9. 2 ^ g . <9 (a) The Envelope Inequality 2 3 \^LJ < 10 (b) /i-canonical form of (a) < 12 (13) <8 (c) The Ladder Inequality (d) /i-canonical form of (c) Figure 5.2: Symmetric facets and their projections T h e o r e m 5.6 The following statements are true: 1. The Envelope Inequality defines a facet of ATSP(V), 2. The Ladder Inequality defines a facet of ATSP{V'), where \V'\ = 7. where \V'\ > 8. A proof of T h e o r e m 5.6 is contained in Section 5. We remark that the Envelope Inequality is one of the two smallest non-trivial, non-subtour elimination, primitive symmetric facet-defining inequalities for ATSP(V) with \V'\ = 7. (Otherwise, the undi- rected version of some primitive symmetric ATSP facet defining inequality would induce a facet of STSP(V) with |V'| = 7, contradicting a theorem by Boyd and Cunningham [8].) The other one is a 7-node Wheelbarrow Inequality. Chapter 5. Symmetric Inequahties for Asymmetric Travelling Salesman Polytopes 113 Note that Clique Lifting may then be applied to any node of these A T S P facetdefining Envelope and Ladder Inequalities. Other extensions of the above results to general Bicycle and Ladder Inequahties (without isolated nodes) are left for the interested reader, using proofs similar to those of Theorems 5.5 and 5.6. We now consider primitive ATSP Chain Inequalities with an isolated node h. Given are any positive integers p and k such that k â€” p is a positive even number. Let R and Si for i = 0,...,k, be proper subsets of V satisfying (i) Si D S,- = 0 for all i,j = 1 , k { i Â± j); (ii) Si = {si} for all i = 1, ...,p; (iii) Si \S = {b[} and S fl Si = {b } for all i = p + 1 , k ; Q 0 2 (iv) R = { r i , r } C So and R fl Si = 0 for all i = 1 , k ; and p (v) V'\u!u Â£â€¢ = {*}â€¢ Let T = { s i , s } . p bl fc s 3 2 " " M l bi W 6 f ^ r si <6(7) 2 â€¢h Figure 5.3: A 9-node ATSP Chain Inequality From the general Chain Inequality (see [47] for definition), we obtain a primitive Chapter 5. Symmetric Inequalities for Asymmetric Travelling Salesman Polytopes 114 Chain Inequality for ATSP(V): J2 v(Si) + y(R : T) 4- y{T :R)<\S \ + l(k+p-2). (5.13) 0 For p = 1, this reduces to a Comb Inequality. If k â€” p > 0 is odd, then it can be shown that the inequality is still valid but not facet-defining, see Padberg and Hong [47]. The smallest non-comb Chain Inequality in /i-canonical form is presented in Figure 5.3. T h e o r e m 5.7 Primitive Chain Inequalities defined in (5.13) with an isolated node (resp., their restrictions) are facet-defining for ATSP(V) (resp., AHP(V)). This theorem is also proved in Section 5. General Chain Inequalities are then shown to be ATSP facet-defining by CliqueLifting on any node. The proofs of Theorems 5.5-5.7 are based on the following two auxiliary results. The first one follows from the known STSP facetial results and the polyhedral equivalence of STSP(V) and HP{V) in C h a p t e r 1. Proposition 5.8 The undirected versions of the symmetric inequalities ay < ao and their projections cx < CQ stated in Theorems 5.5-5.7 define facets of STSP(V) and HP(V), respectively. L e m m a 5.9 (Symmetric D o m i n a n c e L e m m a ) Let cx < CQ be a symmetric inequality for AHP(V) whose undirected version dx' < d defines a facet of HP(V). 0 ists a symmetric facet-defining inequality f x < fo for AHP(V) then cx < Co defines a facet of which dominates cx < CQ, AHP(V). Proof. If fx < fo is symmetric, then it has an undirected version fx' Observe that fx' If there ex- < f' for HP(V). Q < f' also dominates the HP facet-defining inequality dx' < d , and Q Q Chapter 5. Symmetric Inequalities for Asymmetric Travelling Salesman Polytopes 115 therefore, they are equivalent. Because the equality set of HP(V) reduces to x'(E(V)) = n â€” 1, there exist scalars a > 0 and /? such that f' = ad + /3 for all e G E(V) and e /Q = QTCQ + (n â€” l)/3. It follows that f equivalent to fx<fo, e e = ac + /? for all e G A(V). Thus, cx < e hence facet-defining. CQ is â€¢ Thus, the proofs in Section 5 amount to showing that for each restriction cx < CQ of the proposed /i-canonical ATSP inequalities, there exists a symmetric AHP facet-defining inequality that dominates cx < CQ. The result then immediately translates into ATSP term by the polyhedral equivalence of T h e o r e m 5.4. 5.5 C o m p o s i n g S y m m e t r i c Inequalities In this section, we propose a Tree Composition of ATSP symmetric inequalities. Regular Star, Ladder and Chain Inequalities, each with an isolated node, are possible building blocks for the composition. Tree Composition may be used to generate a large new class of ATSP facet-defining inequalities, called ATSP Tree Inequalities, for ATS polytopes, generalizing the directed versions of Regular Path Tree, and thus all non-spanning Clique Tree, Inequalities with an isolated node. The application of Tree Composition also extends to facets of STS polytopes. The composition is similar in spirit to Naddef and Rinaldi's 2-SUM composition. However, the conditions required here for each composing inequality are different and much easier to apply, mostly by visual inspection. Furthermore, large classes of STSP facet-defining Tree Inequalities resulting from 2-SUM composition, such as Regular Path Trees, may also be obtained by the present Tree Composition. Consequently, this Tree Composition may be used to obtain large new classes of tree-like facets of STS polytopes as well. Definition 5 . A We say that an inequality ay < ao for ATSP(V) satisfies Condition S(h, S, Z; d; w; rj) if there exists a proper partition {h, S, Z] of V , with |5| > 2; a node Chapter 5. Symmetric Inequalities for Asymmetric Travelling Salesman Polytopes 116 d E S, called a tip; and two positive scalars u and n, such that the following conditions hold: 1. a > 0, Ve G A(V); 2. a = 0, Ve G (h : S U Z) U (5 U Z : h) U (d : Z) U (Z : d); e e 3. if |5| > 3, then a > nu, e 4. a â€ž = a d vd Ve G A(5 \ d); and = u>, Vv e S\ d. An inequality ay < a for AT5'P(y) is said to be an ATSP Tree Inequality with 0 respect to a subset 5* of V, called a bud, if the following two conditions hold: (51) ay < ao is a symmetric valid inequality for ATSP(V); and (52) ay < ao satisfies Condition S(h, S, Z; d;u; 1). An ATSP Tree Inequality ay < a with respect to bud S is said to be a composable 0 ATSP Tree Inequality if, in addition to (S2), it satisfies the following three conditions: (SI') ay < ao defines a non-trivial symmetric facet of ATSP(V); (53) for every v G S \ d, there exists an a-tight Hamiltonian circuit C on V, called an S-circuit, of the form (z...uv...qdh) with a uv = 0; and (54) there exists a Hamiltonian circuit d on V'\d, called aU-circuit, such that a(Cd) = a. 0 Conditions (S3) and (S4) are sometimes hard to verify and may be removed by strengthening (S2): (S2') There exist two disjoint subsets S and S' of V such that ay < ao satisfies both Conditions S(h, S, Z; d; u; 2) and S{h, S', Z'; d'; u'; 2). P r o p o s i t i o n 5.10 (S1'),(S2') (S3),(S4) w.r.t. both(S,d) and{S',d'). Chapter 5. Symmetric Inequalities for Asymmetric Travelling Salesman Polytopes 117 A proof is provided in Section 6. By Proposition 5.10, conditions (SI') and (S2') are sufficient for recognizing composable ATSP Tree Inequalities by inspection. Path and Wheelbarrow Inequahties are composable ATSP Tree Inequahties with respect to any spike as a bud. Clique Tree, Ladder and Chain Inequahties, each with an isolated node, are composable ATSP Tree Inequahties with respect to any pendant tooth as a bud. For some cases, however, the weaker conditions (SI'),(S3) and (S4) may apply, while (S2') fails. For instance, the Chain Inequality in Figure 5.3 is also a composable ATSP Tree Inequality relative to bud S = {si,ri,r2} with tip d = s\ and u = 1, in which case condition (S2') fails but (S2) holds, since a r i r 2 = 1 < 2u. However, (S3) and (S4) hold: for v = ri and v = r , 2 the S-circuits are (b\b\b\b\vs r dh) and (b\b\b\b\vs r\dh), respectively. The W-circuit is 2 2 2 C = (b\b\r s r b\b\h). d x 2 2 Let a V < aÂ£ (resp., a y < al) be an ATSP Tree Inequality for ATSP(V[) 2 ATSP(V ')) 2 2 (resp., with respect to bud Si (resp., bud S ). Assume that V{ fl V ' = {di,/*i} = 2 2 {d , ^2}, d = di = d and h = h\ = ft , where d\ G S\ and d G 5*2 are tips. Assume also 2 2 2 2 w.l.o.g. that u = UJI = u (by scaling). Define V = V{ U V \ S = Si U S and construct 2 2 inequality ay < yo for ATSP(V) by the following Tree Composition: ' a' , eG A{y!\hi), i = 1,2; e a =< P 2 w, eeA(S)\{A(S )UA(S2)}; 0, otherwise; 1 (5.14) and ao = aj + OQ. This composition is illustrated in Figure 5.4. After composition, two buds containing their corresponding tips di and d are combined into a single bud S in 2 Fig. 5.4(3), and di and d (resp., nodes ^1 and h ), are merged into a single tip d (resp., 2 node h). 2 Chapter 5. Symmetric Inequalities for Asymmetric Travelling Salesman Polytopes (1) Wheelbarrow Inequality 118 (2) Chain Inequality < 15 = 9 + 6 (3) An ATSP Tree Inequality Figure 5.4: A Tree Composition T h e o r e m 5.11 (Tree C o m p o s i t i o n Theorem) Let a ]/ < aj anda y 1 Tree Inequalities for ATSP(y() 1 2 2 < a , be ATSP 2 and ATSP(V^') w.r.t. buds Si and S , respectively, and 2 let ay < ao be obtained by the Tree Composition (i) ay < a is a valid inequality for ATSP(V), (5.14)- Then where V = V( U V{. 0 (ii) if, furthermore, the composing inequalities are composable ATSP Tree Inequalities w.r.t. buds Si and S , then the following statements hold: 2 (A) The composed inequality ay < ao is facet-defining for ATSP(V). (B) The composed inequality ay < ao is a composable ATSP Tree Inequality for AT'SP(V) with respect to the composed bud S = Si U S . 2 (C) If a^y < UQ is a composable Tree for ATSP(Vi) 1 with respect to another bud S' with tip d', satisfying S'DSi = 0, then, the composed inequality ay < a is a composable ATSP 0 Chapter 5. Symmetric Inequalities for Asymmetric Travelling Salesman Polytopes Tree Inequality for ATSP(V) 119 with respect to bud S'. The proof is given in Section 6. Statements (B) and (C) ensure that the Tree Composition procedure can be repeatedly applied so as to construct a large class of tree-like facet-defining inequahties for ATSP polytopes. For instance, T h e o r e m 5.11 implies that Fig. 5.4(3) represents an ATSP Tree Inequality with respect to any one of buds S, S' and S", along with a corresponding tip (5* by Statement (B); the other cases by Statement (C)). Therefore, the resulting inequality can be further used for Tree composition with respect to any bud. By repeating Tree Compositions, a large class of tree-like facet-defining inequalities may then be constructed for ATS polytopes. Finally, we show how the Tree Composition generates the ATSP version of a subclass of the Path Trees (See Figure 5.5), which were introduced as generalizations of the well-known clique trees in [44] and proven to be STSP facet-defining in [42]. Chapter 5. Symmetric Inequalities for Asymmetric Travelling Salesman Polytopes 120 (4) Figure 5.5: A Path Tree obtained from the Tree Compositions Write inequality (5.12) in the following equivalent form: Â£ y(A) + Â£ J W i r ' ) < Â£ | A , | + J2N (\B \ - I) - \ E(fc, +1), i 9=1 t=l 9=1 i=l (5.15) i 1 9=1 where k denotes the number of spikes intersected by circle q. By (Si') and (S2'), a q Regular Star with an isolated node (i.e., Path or Wheelbarrow) is a composable ATSP Tree Inequality with respect to any spike as a bud. For i = 1,2, let a'y' < a be such 0 a Regular Star Inequality with an isolated node hi in form (5.15) for ATSPiVi). Then, the Tree Composition can be applied to these inequalities and the resulting inequality V ^ o a a c a n be easily shown to be in form (5.15) as well. It then follows by repeating the Chapter 5. Symmetric Inequalities for Asymmetric Travelling Salesman Polytopes 121 Tree Composition that the Path Tree Inequalities in form (5.15) are ATSP facet-defining as well. Figure 5.5 illustrates how a Path Tree facet-defining inequality for the ATS polytopes may be built by repeated Tree Compositions. Fig. 5.5(1) represents a Path Tree Inequality after one application of the Tree Composition on the spikes with weight two. After two other applications of the composition on the spikes with weight one, a larger Path Tree facet-defining Inequality for the ATS polytope is obtained as shown in Fig. 5.5(4). It also follows that the undirected version of this inequality defines a facet of the corresponding STS polytope. 5.6 Proofs of the M a i n Results i n Section 5.4 We show in this section that the proposed classes of symmetric inequahties cx < CQ in section 4 define facets of AHP polytopes. For each of the following proofs, we implicitly assume that fx < f are facet-defining inequalities that dominate cx < CQ. By P r o p o 0 sition 5.8 and the Symmetric Dominance L e m m a , it suffices to show that their dominating facet-defining inequalities fx < f are symmetric. 0 We will use the following notation in the sequel. For a subchain P = (vx...vi) of any Hamiltonian path on V, define P = (u/...ui) to be the same subchain in reverse order. Given any inequality fx < f for AffP(V), define the f-length of P by 0 f(P) = f(v ...v ) l l = Â£f i , ViVi+1 i=i l<l<n. (5.16) Note that P may be a single edge, or even a single node; in the latter case f(P) = 0. Path P is f-symmetric if f(P) = /(*P). If p = /(P), define *p = /(P"). By definition, for any symmetric inequality cx < CQ, all edges e 6 A are c-symmetric. Chapter 5. Symmetric Inequalities for Asymmetric Travelling Salesman Polytopes 122 P r o o f of T h e o r e m 5.5: Define Define also P/ = (b[...b ) for all / = 1 , s . ni b{ 6j_ fti 'T 1 1 bl, b> 0 6 fl 6* 61. fc 1 P(b) P(a) 5 6 61. 6i fc P(c) L 1 I I I 9 - P(d) P(f) P(e) Figure 5.6: c-tight paths Given in Figure 5.6 are six c-tight paths on V (cf. Figure 5.1, disregarding h and inequality (5.12)), where the dashed box contains an even (possibly zero) number of spikes and a fixed Hamiltonian chain on these spikes. The node g in Figure 5.6 or in the following given paths and chains may or may not be present, (i) Comparing path P = P(a) with path P ' = P(a) U (&}, b\) \ (6*, b{), i.e., 0 yields = f xP ~ f xP = fb*b{ ~ fb{b[i = *c7. Replacing i, j, k in P(a) by k, i,j, we obtain as above that /< k = *c7. t b Similarly, we show by reversing these paths that h[b{ ~ fb{b* - fb*b[ - a - (5.17) Chapter 5. Symmetric Inequahties for Asymmetric Travelling Salesman Polytopes 123 (ii) Let P(Z) be obtained from P(b) by replacing (&Â£,&!) and (&i...6j) with (b[,b\) and (bj...fcj), respectively, for / = 2 , r i j â€” 1. Let P(n,) be obtained from P(d) by replacing (&!,&{) and Pj with (&i,&\) and P j, respectively. By (i), and by comparing P(rij) with P(d), P(Z) with P(6) for / = 2, ...,nj â€” 1, it follows that the following rij â€” 1 linearly independent equations hold: i-i i-i t=i t=i Therefore, edges ( 6 t , ^ ) are /-symmetric for all 1 < t < rij â€” 1 and 1 < j < s, and + 1 /(P,) = / ( P , ) for all 1 < / < s. (iii) Let 7 = f j b = /j , due to (ii). From path P(e), we construct: 6 p = (..<...6^i...6;^ ...6i), nj and from path P(c): P' = (&{...^...6^...6 6i...6g. 1 By (i) and (ii), and by Comparing P with P(e) and P' with P(c), respectively, it follows a+ 0 = *a + 0, a + j â€” *b7 + 0. Further, comparing P' with P (c) yields *h7 + 7 = a + 0 . From these three equations, we obtain a = *a and 0=0. Moreover, if node g exists, i.e., for Path Inequalities, define P = P(d) U P , U ftk) \ {P U ( 6 ^ ) } . By (i), (ii), (iii), and by comparing this P with P(d) and P with P (d) respectively, it follows Since the above hold for any i,j,fc,it follows that A({b\, ...,b{}) U A({y, 6 ^ , 6 ^ } ) contains only /-symmetric edges. Chapter 5. Symmetric Inequalities for Asymmetric Travelling Salesman Polytopes 124 (iv) For any j such that nj > 3, construct the following c-tight path: P' = ( i...6J ^...fe* ...6j6i...^^....Df ). 0 l fc +1 Observe that by (ii) and (iii), all edges in P' are /-symmetric except edge (fc/,6^.), therefore comparing P' with P' yields that (bj, b ^) is also /-symmetric for 1 < / < rij â€” 2. 3 Further, if n,j > 4, from P(d), construct the following c-tight path: Observe that all edges in P have been shown to be /-symmetric except edge (&t,6/ ). +1 Therefore, comparing P with P implies that (V , 6/ ) is /-symmetric for all 1 < t < I < t +1 rij. It follows that all edges in A ( { & i , . } ) are /-symmetric for all 1 < j < s. (v) For any pair of nodes b\ and 6f +1 such that 1 < t < \ â€” 1, 1 < / < nj â€” 1, i / j and M(b\) < Af(6f ) (cf. page 110 for the definition of M(*)), define c-tight paths: for +1 t > 2, P(t, 1 + 1) = P(f); otherwise t = 1, we have P(*,Z + 1) = (6i...6^ ....6f fei...6',.... ...6^...6j). n +1 5 Observe that P(2,Z + 1) contains exactly one edge (6j, 6f ) not shown to be / +1 symmetric, therefore comparing P(t, Z+l) with P (t, l+l) yields (6j, &/ ) as /-symmetric. +1 For all b\ and bj +1 such that Af(oJ) > M(6f ), exchange i and j, and then repeat (v). +1 If node g exists, define c-tight paths P&) = (fe^..6; ..^...&Jfei...^^....6| ), r +1 i < t < m - I. Observe also that for any 1 < t < nj â€” 1, the edges in Pj(t) are shown to be /-symmetric except for the edge (b\,g). By comparing Pj(t) with P j(t), it follows that edges (b\,g) are /-symmetric for all t and j. Chapter 5. Symmetric Inequahties for Asymmetric Travelling Salesman Polytopes 125 From (iii), (iv) and (v), it follows that fx < f is a symmetric inequality. The proof 0 is complete. â€¢ P r o o f of T h e o r e m 5.6: This proof is conducted by successive augmentations of a set Ef of /-symmetric edges until Ef = A(V). The set Ef has the property that e G Ef implies V G Ef. For any subset E' C A(V), define the following operation E'QEf. replace Ef with Â£ / U {e G A(V) : either e or *e~ is in E'}. The proof consists of the following three phases. (i) An initial set Ef C A(y) of /-symmetric edges with the same /-length is constructed. paths P and P' implies "something". Moreover, the implication may implicitly use the previous results and obvious symmetries. The /-length of the underlined part in P has been shown to be equal to that in P'. (iii) Select any edge e G A(V) \ Ef and construct a c-tight path P on V such that e G P and P \ e C Ef. Thus, P, P~ = â€¢ { e } Â© Â£ / . Repeating (iii) until E = A(V). f E n v e l o p e : Let a = f , 0 = / 4 , *P = f*3, 7 = /24, 7" = f*2, Z = /se and T = / 3 12 6 5 . (i) Let C = (124356) and C = (214356). 1 2 C \ (1,2), C \ (3,5) =^> / 1 Hence, / 1 2 1 =/ 1 2 = a and let 1 2 = /ss; C \ (2,1), C \ (3,5) = Â» / 2 2 2 1 =/ 3 5 . = {(1,2), (2,1)}. Observe that for any e G E\ = {(3,5)} U ({1},{4,6}), there exists e' G Ef and a Hamiltonian cycle C on V such that e, e' G C and cx = CQ + 1. (For e = (3,5), let c e' = (1,2) and C = C above; for e = (1,4), let e' = (2,1) and C = C above; for 1 2 e = (1,6), let e' = (2,1) and (216534).) Thus, comparing C \ e and C \ e', and then Chapter 5. Symmetric Inequahties for Asymmetric Travelling Salesman Polytopes 126 C \ *e~ and C \ e' implies that e is /-symmetric. Hence, set Ef = {e} @Ef. It follows by repeating the above that Ef = Â£ 1 Â© Ef. Moreover, f = a for all e E Ef. e (ii) (4356 21), (12 4356) => / (2156 43), (156243) => / 6 2 6 4 = / 2 4 = 7- = 2 7 - 0 , due to the above and (i). Reversing the above two pairs of paths, we have he = /42 = 7~i and / 4 6 = 27" - a, respectively. Using the above results, we have the following implications: (126435), (534621) (561243),(342165) "7 4- 27 - a + *J = 7 + 2*7 - a + /3; and Â£ + 7 + 7 = 7 + 7" + It follows that Â£ = Â£ . B y symmetry, /? = /3 . Hence, 7 = ^7" and {(3,4), (5,6), (4,6), (2,4), (2,6)} 0E . y (iii) For edges (1,3),(1,5),(2,3),(2,5),(3,6),(4,5), construct, respectively, the corresponding desired c-tight paths (213465), (215643), (123465), (125643), (124365), (345621). â€¢ L a d d e r : Let a = / 4 7 and Ef = 0. (i) Let C = (7216534) and C = (7432156). 1 2 C \ (7,2), C \ (4,7) =>â€¢ / 1 1 7 2 = / 4 7 = a; it follows / 7 2 = fa = a by exchanging nodes 3,4 with 5,6. C 2 \ (7,4), C \ (6,7) 2 / 7 4 = / 6 7 . Hence, / 7 4 = / 4 7 = / 6 7 = f 76 = a and {(4,7), ( 6 , 7 ) } Â© / ^ . Observe that for any e E E\ = {(7,2)} U ({1}, {3,4,5,6}), there exists e' E Ef and a Hamiltonian cycle C on V such that e, e' E C and c x = CQ + 1 (either C or C above). c 1 2 Chapter 5. Symmetric Inequalities for Asymmetric Travelling Salesman Polytopes 127 Thus, comparing C \ e and C \ e', C \*e~ and C \ e' implies that e is /-symmetric Hence, { e } $ Â£ / . Repeating the above yields E\ Â© Ef. Moreover, f â€” a for all e G Ef. e (ii) (7432156). (7432165) =â€¢ {(5,6), (3,4)} Â© Ef. (12743 56). (12765 34) =â€¢ {(3,5)} Â©Â£,. (72134 65). (72156 43) =â€¢ {(4,6)} Â©Â£,. (22 13465). (56431 21) "=Â» {(1,2)} Â© Â£/. (743 2156). (6512 347) =â€¢ {(2,3),(2,5)}Â©Â£,. (iii) For edges (1, 7),(2,4),(2,6),(3,6),(3, 7),(4,5),(5,7), construct, respectively, the corresponding desired c-tight paths (5643217), (1243567), (1265347), (7436521), (1256437), (1234567), (1234657). This completes the proof for \V\ = 8. If node g exists, revise the above proof as follows: â€¢ for every path or cycle used in (i), (ii) and (iii) above, replace subchains (12) and (21) by (#12) and (21g), respectively; â€¢ in (i), replace E by {(7,2), (1, <?)} U ({</}, {3,4,5,6}); x â€¢ in (iii), replace (1,7) by (<7,7), and add:" for edges (2,#), (1,3), (1,4), (1,5), (1,6), (1,7), construct, respectively, the following desired c-tight paths (12tf43567),(7213465s),(7214356), (7215643#),(7216534#),(5643217)." 5 5 This shows that the result holds for the case |V'| = 9. Finally, apply Clique-Lifting on the isolated node g to complete the proof. â€¢ Proof of Theorem 5.7: Let cx < CQ be the restriction of inequality (5.13), and let fx < fo be a facet-defining inequality for AHP(V) that dominates cx < CQ. Note Chapter 5. Symmetric Inequahties for Asymmetric Travelling Salesman Polytopes 128 that by definition, for any t,q Â£ {l,...,p}, there exists a "zig-zag" Hamiltonian path P = (r ...s ) on RUT such that c(P) = 2p - 1 (cf. Fig. 5.7(1)). Let (6^...6 ) and q t X (6f ...6* ) denote twofixedsubchains (r ...s ) and (s ...r ), respectively. Let n,- = 2 for all fc q t t q i. Thus, following (i), (ii), (iii) and (v) in the proof of T h e o r e m 5.5, where n,- = 2 for all i, and the subchains P k and Pk are replaced by (r â€¢ â€¢ â€¢ s ) and (s â€¢ â€¢ â€¢ r ), respectively, q we show that all edges in A\A(RUT) t t q are /-symmetric. Construct the four c-tight paths on V, see F i g u r e 5.7. P(l) 9 s 1 St t Tt P(3) P(4) Figure 5.7: c-tight paths for the Chain Inequality For any 1 < q < p, we obtain from path P(l) a c-tight path P' = P ( l ) U (ijrrfftjfti) \ (fei%r ,). g5 Thus, comparing P(l) with P', and P ( l ) with P', respectively, yields f Sqrq For any 1 < q < t < p, we obtain from path P(2) a c-tight path P" = P(2) U {(r , V ), (s , r )} \ {(s , r t ), ( r Â« , s )}. t 2 t t q t = f Tqaq . Chapter 5. Symmetric Inequalities for Asymmetric Travelling Salesman Polytopes 129 As above, comparing P(2) with P", and P (2) with P", respectively, yields f a r t = f, r aq Finally, observe that all edges in paths P(3) and P(4) have been shown to be / symmetric except edges {r ,r ) and (s ,s ). q t q t Thus, comparing P(3) with P (3), and P(4) with P (4), respectively, implies that edges (r , r ) and (s , s ) are /-symmetric. It follows q t q t that fx < fo is symmetric. 5.7 â€¢ Proofs of the Main Results in Section 5.5 Proof of Proposition 5.10: Let d â‚¬ S and u = d' G S' be the tips. For any v G S\d, we have a uv = 0 by (S2'). By (SI'), construct an a-tight circuit C containing (u, v). Thus, C contains a subchain (uv...qd). First, observe that a d â€” u; otherwise replacing q the subchain in C with (uq...vd) yields a circuit with a-length at least ao + u>. So, C is in the form of either (v...h...qdp...u) or (v...qdp...h...u). If a dp = 0, then construct the desired S-circuit by moving h in C to the position between d and p; else, a dp = u>, and moving d in C to the position immediately before h yields the desired Â«S"-circuit, since Cqd + a-dp = 2u < a pq (due to (S2')) and ay < a is valid for ATSP(V). 0 This shows that (S3) holds. To show that (S4) also holds, we first claim that there exists an a-tight circuit C on V of the form (u...pdq) with either (i) p, q G Z U h or (ii) p,q G S. To prove this claim, let n = \V \ h\ and let cx < Co be the restriction of ay < ao w.r.t. node h. By (SI') and polyhedral equivalence, there are n(n â€” 1) â€” 1 affinely independent incidence vectors y of a-tight circuits on V (resp., incidence vectors x of c-tight paths on V \ h). If the claim is false, then these incidence vectors y satisfy equations y(d : S\d)+y(S\d : d) = 1, ay = ao and y(V \ h) = n â€” 1. Observe that the above three equations are in "/i-canonical form", and their restrictions x(d : S\d) + x(S\d : d) = 1, cx = CQ and x(V'\h) = n â€” 1 are three linearly independent equations on AHP(V \ h). (Note that c > 2u for all e G e A(S\d), Chapter 5. Symmetric Inequahties for Asymmetric Travelling Salesman Polytopes 130 due to (S2').) Further, these equations are satisfied by dim(AHP(V \ h)) = n(n â€” 1) â€” 1 affinely independent incidence vectors x above, a contradiction. Hence, the claim holds. Construct Cd = (u...pq). Note that a d = a,d = 0 for case (i); a p q pq > 2u = a + a.d pd for case (ii). Therefore, Cd is the desired W-circuit. q â€¢ To prove the Tree C o m p o s i t i o n T h e o r e m , we need the following four auxiliary results. Let ay < a be a composable ATSP Tree Inequality with respect to a bud S for 0 ATSP(V) and let {h, S, Z} be the corresponding partition. Define V = V \ h. Then, the restriction cx < CQ of ay < a w.r.t. h is called a composable Tree Component for 0 AHP{V). Z-path: Define the following special paths w.r.t. cx < CQ and tip d: A c-tight path (t...vd...s) w.r.t. v 6 Z such that c = 0, VeG ({t,v} : {d,s}). e <S-path: A c-tight path (z...uv...qd) w.r.t. v E S \ d such that c zv = c uv = 0 and c >u e for all e used in subchain (v...qd). W-path: A Hamiltonian path Pd on V \ d such that c(Pd) = CQ and both endnodes in Z. L e m m a 5.12 Let cx < CQ be a composable Tree Component for AHP(V). Then, 1. for every v Â£ Z, there exists a Z-path (t...vd...s); 2. for every v Â£ S\d, there exists an S-path (z...uv...qd); and 3. there exists U-path Pd on V \ d. Proof. Note first that by polyhedral equivalence and (SI), cx < CQ defines a non-trivial facet of AHP{V). Chapter 5. Symmetric Inequalities for Asymmetric Travelling Salesman Polytopes 131 (1) For every v Â£ Z, there exists a c-tight path containing (v, d) of the form (t...vd...s). If there is an edge e â‚¬ ({t,v}, {d, s}) with c > 0, say e = (v,s), w.l.o.g., then a e Hamiltonian path P = (t...vs...d) yields cx > Co, a contradiction. p (2) For every v 6 S \ d, by (S3), there exists an o-tight 5-circuit (z...uv...qdh) with o-uv = 0. Remove h from this circuit to obtain an <S-path (z...uv...qd). (Note that c^, = 0 holds by definition and c = 0 follows since (u...zv...qd) is also a c-tight path. The last zv condition follows by contradiction: if for some e in subchain (v...qd), c < UJ, replacing e e with (d, v) and then connecting an endnode of the resulting subchain with node u of (u...z) yields a Hamiltonian path P with c(P) > CQ.) (3) By (S4), there exists a ZY-circuit Cd- Then, W-path Pd is obtained by removing h from Cd- If one of the endnodes in Pd is in S, then connecting this endnode with d yields a Hamiltonian path P on V with c(P) = Co + w, a contradiction. â€¢ L e m m a 5.13 (3-Path L e m m a ) Let cx < CQ and fx < fo be two valid inequalities for AHP(V). Assume the former inequality is symmetric and dominated by the latter. Let Ui,Ui, Uz be a partition ofV and let Pi = (u,-...u ) be a Hamiltonian path on Ui, i = 1,2,3. t Define E = {P, P, : i = 1,2,3}, p If c = 0 for all e â‚¬ Eo and YA=I (Pi) c e (i) f(P) = fCPi) (ii) f e = c E = lj({"^} = Â«,-}). 0 o> then for i = 1,2,3; and is a constant for all e G EQ. Proof, (i) From Pi, P , P 3 , we obtain two Hamiltonian circuits on V: 2 C = (u ...v U2...v u ...v ), 1 1 2 3 3 C = {ui...viv ...u u ...v ), 2 2 3 3 (5.18) Chapter 5. Symmetric Inequalities for Asymmetric Travelling Salesman Polytopes 132 such that c(C) = c(C) = CQ. Comparing c-tight paths C \ (v , ui) and C \ (t>i, u ) yields 3 /Â«stn = fv 1 U 2 ; 2 comparing C \ (u , Â«i) with C \ {v , v ) yields 3 x fviV2 /v3"l = 2 (5.19) fv\U - = 2 Further, comparing P = (U3...V3U1...V1U2...V2) and P' = (U3...V3U1...V1V2...U2) yields 0 = f(P) - f(P') = f VlU2 + f(P ) - f 2 - / ( P ) = /(P ) - / ( P ). VlV2 2 2 2 Similarly, we show that P\ and P are /-symmetric. Hence, (i) holds. 3 (ii) Observe that for any eo G Eo, there exists a Hamiltonian circuit C C E U EQ P on V such that eo E C and c(C) = Co. W.l.o.g., assume that C has form (5.18) and Co = (vi, U2). Comparing the c-tight paths C \ (v , U2), C \ (i> , u ) and C \ (u , Â«i) yields x /"iÂ«2 /"2U3 = = /f3Â«i = 2 f(C) 3 3 /o- Similarly, using C , we obtain fu Vl 2 fu3V = 2 = fli\V3 = /( C ) /o- Further, by (i) and f(C \ (v\,u )) = f(C \ (u ,i^)), we have 2 2 i=l Â«'=1 Hence, all edges e G Eo are /-symmetric. 0 Since all elements in Eo U _E are shown to be /-symmetric, repeating (5.19) for all P permutations of indices of u , u , u and exchanging the roles of the u and u nodes imply x 2 3 that (ii) holds. The proof is complete. â€¢ Chapter 5. Symmetric Inequalities for Asymmetric Travelling Salesman Polytopes 133 L e m m a 5 . 1 4 The composed inequality ay < OQ for ATSP(V) for defined in (5.14) is valid ATSP(V). Proof. It suffices to show that its undirected version a'y < ao is valid for Let S[ = Si\ di and S' = S \ d . 2 2 2 STSP(V). An edge e is called an w-edge if e 6 E(d : 5 J U ^ ) U E(S[ :S' ). Let C* be any solution to 2 m&x{a'y : C is a Hamiltonian cycle} = a^. c Let C = C*. (i) [u>-Edge Reduction] Let E(V{ : V \ d ) be the set of all crossing edges, and let 2 E(Si 2 : S' ) be the set of all UJ-crossing edges. 2 For any Hamiltonian cycle Co on V, let N (Co) = \Cof\E(Si : S' ) \ denote the number u 2 of w-crossing edges used in Co. If there exists a pair (u, v) and (s, t) of uncrossing edges in C such that some subchain connecting (u, v) and (s, t) in C contains an odd number of crossing edges, then transform C to Hamiltonian cycle C as follows: C = (d...uv...st...r) â€”â€¢ C = (d...us...vt...r). Since a' + a' > 2u, we have a* = a'(C) < a'(C') = a*, and N {C) us C = C vt W (5.20) = N {C) - 2. Let W Observe that such a reduction is always possible whenever liV^C)! > 2. Hence, we repeat (i) until N (C) < 2. W (ii) Exchange sets S[ and S' in (i) and then apply (i). 2 (iii) First, observe that C contains at most one edge in E w â€” E(S[ : S' ). Otherwise, 2 C contains exactly two edges (u,v), (t,s) Â£ E . Further, by (i) and (ii), C contains the w subchain (pdq) with a' = a' = 0, where d is the common tip. Replacing subchains (uv) pd dq and (pdq) in C with (udv) and (pq), respectively, we obtain a Hamiltonian cycle C on V such that a'(C) > a'(C) + u> > a^, a contradiction. Chapter 5. Symmetric Inequalities for Asymmetric Travelling Salesman Polytopes 134 Now, let Pi = C fl E(V{) and P = C D E(Vj). Note that P and P are subsets of 2 x 2 some Hamiltonian cycles C\ on V{ and C on V , respectively. If C contains no edges in 2 2 E , then w a'(C*) = a'(C) = a'(Pi) 4- a'(P ) < a'(Ci) + a'(C ) < aj + a = a . 2 2 2 0 Otherwise, C contains exactly one edge (u, v) Â£ E with u Â£ S[ and v Â£ 5j> and a w subchain (pdq). Let P ' = Pi U (u,d) and P ' = P U (d,u). If p,q Â£ V/ (resp., p,g Â£ Vj), x 2 2 then, P (resp., P[) is a subset of some Hamiltonian cycle on V (resp., V{). Else, 2 2 w.l.o.g. assume q Â£ V{ and p Â£ V^', and observe also that either P[ is a subset of some Hamiltonian cycle on V[ or P is on V , since otherwise both P[ and P contain some 2 2 2 sub-cycles covering d, and so does Pi U P U (u, u) C C , which contradicts that C is a 2 Hamiltonian cycle on V. If P/ is contained in some Hamiltonian cycle C[ on V{, then a'(C*) = a'{C) = a'(Pi) + a'(P ) < a'(C[) + a'(C ) < a 4- a = a ; 2 2 2 0 0 else the above holds by exchanging indices 1 and 2. Let inequality ay < a for ATSP(V) be obtained by the Tree Composition (5.14) 0 of two ATSP Tree Inequalities a y < aj and a y 1 â€¢ 1 2 < OQ, relative to buds S\ and S , 2 2 respectively, and let {hi, Si, Z{\ and {h , S , Z } be the corresponding partitions. Define 2 2 2 Vi = V! \ hi, i = 1,2, and V = V'\h. Recall that Vi n V = {d} = {d } = {d }, where 2 d is the common tip. The restrictions cx < CQ, C X X x x 2 < cj and c x < c\ of ay < ao, 2 2 a y < aj and a y < al, w.r.t. h, hi and h , are called Tree Components, for 1 1 AHP(Vi) 2 2 2 and AHP(V ), 2 AHP(V), respectively. Then, we say that cx < CQ is obtained by AHP Tree Composition of two Tree Components c x < c\ and c x < x x 2 2 Recall that the restriction of a composable ATSP Tree Inequality is a composable Tree Component. See Figure 5.4 for an example of the AHP Tree Composition, disregarding nodes hi, h , h. 2 Chapter 5. Symmetric Inequahties for Asymmetric Travelling Salesman Polytopes T h e o r e m 5.15 135 Inequality cx < CQ obtained by AHP Tree Composition of two composable Tree Components c x 1 1 < cj and c x < CQ defines a facet of 2 2 AHP(V). Proof: The vahdity of cx < CQ follows by L e m m a 5.14 and the polyhedral equivalence. Let fx < fo be a facet-defining inequality that dominates cx < CQ. Let {Vi, V \ d } be the partition of V , and by L e m m a 5.12(3), let P = (u ...v ) be 2 2 2 2 2 a W-path on V \ d with c(P ) = c\ and u , v G Z . 2 2 2 2 2 2 (i) For every v\ G Z i , by L e m m a 5.12(1), we construct a S-path (t\...v\d...8\) on Vi, and let Pi = {t\...V\) and P = (d...si); for every vi G 3 S*i \ di, by L e m m a 5.12(2), we construct an Â«S*-path (z\...u\V\...q\d) on Vi, and let Pi = (zi...u\) and P 3 = {yi...q\d). Note that for all v Â£ Vi \ d 1} we obtain Pi, P and P satisfying the conditions in 2 3 L e m m a 5.13, and therefore we have f = f d for all e 6 ({"2, v } : Vi) U (Vi : {u , v }) e U2 2 2 2 and f(P ) = f(P ). This further implies that for any c -tight path P' on Vi, there exists 2 1 2 a c-tight path P on V containing P' and P such that 2 fo = fx Since c x 1 1 P = f(P') + f(P ) + f 2 < c\ is facet-defining for AHP(Vi) . U2d and the above equality holds for all c 1 tight paths P', there exist real numbers ai > 0 and fi\ such that f = a\c + fa for all e e e G A(Vi). By partitioning V into {V2, Vi \ di}, we show by symmetry that for some real numbers a 2 > 0 and /?2, / e = <*2C + /5 holds for all e G A(V 2 ). e 2 (ii) For any v G Z , construct a Z path (< -"t>2d....s ) on V . As in (i), for every v\ G Z i , 2 2 2 2 2 construct a Z-path (t\...v\d...s\) on Vi; and for every v\ G 5*i \ d, we construct an S-path (^i...Â«it;i...oid) on Vi. As required by the conditions for L e m m a 5.13, we obtain for the former case Pi = (<i...t>i), P2 = (t ...v ), 2 2 P = (gi...d...s ), 3 2 Chapter 5. Symmetric Inequalities for Asymmetric Travelling Salesman Polytopes 136 and for the latter case, Px Further, since c ZlVl = P = (t ...v ), (*i...ui), =c V2S2 2 2 P = (ui...Oid...s ). 2 3 2 = 0, by (i) and L e m m a 5.13, we have By symmetry, it follows f =flfor all e â‚¬ A(V) \ {A(Vi) U A(V ) U A(S)}. e 2 (iii) For any Vi G 5,- \ d, construct an <S-path (z,-...UjU,-...o,d), i = 1,2. Recall that (u,-...o,-d) uses only edges e with c > u> and c j = u by definition. Possibly o,- = u,.) Comparing e gi the following two c-tight paths: P' = (zx...u z ...u v ...q dqi...v ), x 2 2 2 2 P" = 1 yields 0 = f(P') - f(P") = (3 + f -/3- /^ dqi P' and P" yields f VlV2 V l 2 = a i = a 2 1 1 2 2 = uj + 0 - f ai V2Vl 2 2 1 . Further, comparing = a\to +fl,due to (i) and (ii). By exchanging V\ and V , we show also / â€ž a (z ...u z ...u dq ...v v ...qx) lV2 = = cc u> + fl. It follows that 2 , (i), (ii) and (iii) imply that f = ac +flfor all e e A(V). e e â€¢ Now, we are in a position to prove the Tree Composition Theorem. P r o o f of the Tree C o m p o s i t i o n T h e o r e m : Part (i) of the theorem is proved in L e m m a 5.14. For part (ii), Statement (A) follows from T h e o r e m 5.15, by polyhedral equivalence. For statements (B) and (C), (S2) holds by inspection. We need to examine conditions (S3) and (S4) for each case. Chapter 5. Symmetric Inequahties for Asymmetric Travelling Salesman Polytopes 137 For (B), Condition (S3) follows by constructing, for every vi G Si \ d, S-circuit (u ...v z\...u\v ...q\dh) 2 2 x on V, where (u ...v ) is aZY-path on V \d and 2 2 2 is (zi...UiVi...q d) 1 an <S-path on V\. Similarly, we obtain a requisite Â«S-circuit for every v Â£ S \ d. 2 2 (S4) holds by exhibiting W-circuit (ux...v\U2...v h) on V ' \ d , where (u,-...u ) is aW-path 2 t on Vi \ di, i = 1,2. For (C), Condition (S3) follows by constructing, for every Â»i 6 5' \ d', S-circuit {u ...v z\...u\V\...q\d!h) on V, where (u2...v ) is a W-path on V2 \ d and (zi...uii>i...fl d ) 2 2 2 1 is an Â«S-path on Vi. (S4) holds by exhibiting ^/-circuit (â€¢U2...V2)) (ui...viu ...v h) 2 2 on V \ d', where (ui...vi) (resp., is a W-path on VI \ d' (resp., V2 \ d). This completes the proof of the theorem. â€¢ V / Bibliography [1] D. Applegate and W. Cook (1991). A Computational Study of the Job-Shop Scheduling Problem. Preprint, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA. February 22, 1991. [2] J.R. Araque G.(1989). Contributions to the Polyhedral Approach to Vehicle Routing. Ph.D Thesis, State Univ. of New York at Stony Brook, N.Y. [3] E. Balas (1985). On the Facial Structure of Scheduling Polyhedra. Mathematical Programming Study 24, 179-228. [4] E. Balas (1987). The Asymmetric Assignment Problem and Some New Facets of the Travelling Salesman Polytope. MSRR No. 535, GSIA, Carnegie Mellon University. To appear in the SIAM Journal on Discrete Mathematics. [5] E. Balas and M . Fischetti (1988). The Fixed-Outdegree 1-Arborescence Polytope. MSRR No. 551, GSIA, Carnegie Mellon University, Pittsburgh, PA. [6] E. Balas and M. Fischetti (1989). A Lifting Procedure for the Asymmetric Travelling Salesman Polytope and a Large New Class of Facets. MSRR No. 556, GSIA, Carnegie Mellon University, Pittsburgh, PA. [7] S. T. Boyd and W. Cunningham (1987). Workshop on Computational Discrete Optimization at Cornell University, Ithaca, N.Y., June, 1987. [8] S. T. Boyd and W. Cunningham (1989). Small Travelling Salesman Polytopes. Preprint, Carleton University, Ottawa, to appear in Math, of Operations Research. 138 Bibliography 139 [9] P. Bratley, B.L. Fox and L.E. Schrage (1983). A Guide to Simulation, SpringerVerlag New York Inc. [10] S. Chopra and G. Rinaldi (1990). The Graphical Asymmetric Travelling Salesman Polyhedron. Integer Programming and Combinatorial Optimization, proceedings of a conference held at the University of Waterloo, May 1990, by the Mathematical Programming Society, edited by Raviv Kanan and W.R. Pulleyblank. [11] G. Clark and J.W. Wright (1964). Scheduling of Vehicles from a Central Depot to a Number of Delivery Points. Operations Research 12, 568-581. [12] M. Conforti, M.R. Rao and A. Sassano (1988). The Equipartition Polytope I: Formulations, Dimension and Basic Facets. To appear in Math. Programming. [13] G. Cornuejols, J. Fonlupt and D. Naddef (1985). The Travelling Salesman Problem and Some Related Integer Polyhedra. Math. Programming 33, 1-27. [14] G. Cornuejols and Harche (1989). Polyhedral Study of the Capacitated Vehicle Routing Problem. MSRR No. 553, GSIA, Carnegie Mellon University, Pittsburgh, PA. [15] T. Christof, M . Junger and G. Reinelt (1990). A Complete Description of the Travelling Salesman Polytope on 8 nodes. Report No. 249, Institut fur Mathematik, Universitat Augsburg. [16] M . Dyer, L. Wolsey (1989). Formulating the Single Machine Sequencing Problem with Release Dates as a Mixed Integer Program. Discrete Applied Mathematics, to appear. [17] M . Fischetti (1991). Facets of the Asymmetric Travelling Salesman Polytope. Math, of Operations Research, Vol.16, No.l, Feb.1991, pp. 42-56. Bibliography 140 [18] M . Fischetti (1989). Clique Tree Inequalities Define Facets of the Asymmetric Travelling Salesman Polytope. Technical report OR/89/7, DEIS, University of Bologna. [19] B. Fleischmann (1985). A Cutting Plane Procedure for the Travelling Salesman Problem on Road Networks. European Journal of Operations Research 21, 307-317. [20] B. Fleischmann (1987). Cutting Planes for the Symmetric Travelling Salesman Problem. Paper presented at the joint annual meeting of DGOR and NSOR, Eindhoven, Netherlands, Sept. 23-25, 1987. [21] B. Fleischmann (1988). A New Class of Cutting Planes for the Symmetric Travelling Salesman Problem. Math. Programming 40, 225-246. [22] M.R. Garey and D.S. Johnson (1979). Computers and Intractability: a Guide to the Theory of NP-Completeness, W.H. Freeman, San Francisco. [23] R. S. Garfinkel (1985). Motivation and Modeling, in: E.L. Lawler et al., eds., The Travelling Salesman Problem. (J. Wiley & Sons, 1985), pp.22-23. [24] A.M. GeofFrion (1985). Lagrangean Relaxation for Integer Programming. Mathematical Programming Study 2, pp.82-114. [25] P.C. Gilmore, E.L. Lawler and D.B. Shmoys (1985). Well-Solved Special Cases, in: E.L. Lawler et al., eds., The Travelling Salesman Problem. (J. Wiley & Sons, 1985), pp.87-143. [26] M . Grotschel and M.W. Padberg (1979a). On the Symmetric Travelling Salesman Problem I: Inequalities. Math. Programming 16, 265-280. [27] M . Grotschel and M.W. Padberg (1979a). On the Symmetric Travelling Salesman Problem II: Lifting Theorems and Facets. Math. Programming 16, 281-302. Bibliography 141 [28] M . Grotschel and M.W. Padberg (1985). Polyhedral theory. In: E.L. Lawler et al., eds., The Travelling Salesman Problem. (J. Wiley & Sons, 1985), pp. 251-305. [29] M . Grotschel and W.R. Pulleyblank (1986). Clique Tree Inequalities and the Symmetric Travelling Salesman Problem. Math, of Operations Research 11, pp. 537-569. [30] A. Kearny (1980). Improving Productivity in Physical Distribution. Report Undertaken for CPDM, London. [31] G. Kolata (1991). Math Problem, Long Baffling, Slowly Yields. The New York Times, March 12, 1991, pp. C l and C9. [32] G. Laporte and Y. Nobert (1987). Exact Algorithms for the Vehicle Routing Problem. Annals of Discrete Mathematics 31, 147-184. [33] E. L. Lawler (1978). Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints. Annals of Discrete Mathematics 2, pp. 75-90. [34] E. L. Lawler (1983). Recent Results in the Theory of Machine Scheduling, in: A.Bachem, M.Grotschel and B.Korte, edrs, Mathematical Programming: The State of the Art-Bonn 1982, Springer, Berlin, 1983, pp. 202-234. [35] E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D.B. Shmoys (1985). The Travelling Salesman Problem. J. Wiley & Sons, 1985. [36] E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D.B. Shmoys (1989). Sequencing and Scheduling: Algorithms and Complexity. Report BS-R8909, Center for Mathematics and Computer Science, 1009 AB Amsterdam, The Netherlands. [37] J.K. Lenstra and A.H.G. Rinnooy Kan (1978). Complexity of Scheduling under Precedence Constraints. Operations Research 26, pp. 22-35. Bibliography 142 [38] J.F. Maurras (1975). Some Results on the Convex Hull of Hamiltonian Cycles of Symmetric Complete Graphs. B. Roy, ed., Combinatorial Programming: Methods and Applications (Reidel, Dordrecht, 1975), pp. 179-190. [39] T . E . Morton and D.G. Dharan (1978). Algoristics for Single-Machine Sequencing with Precedence Constraints. Management Science 24, pp. 1011-1020. [40] D. Naddef (1989). The Binested Inequalities for the Symmetric Travelling Salesman Polytope. To appear in Math, of Operations Research. [41] D. Naddef and G. Rinaldi (1988). The Graphical Relaxation: a New Framework for the Symmetric Travelling Salesman Polytope. Report R.244, IASI-CNR, Rome, Italy. To appear in Math. Programming. [42] D. Naddef and G. Rinaldi (1988). The Symmetric Travelling Salesman Polytope: New Facets from the Graphical Relaxation. Report R.248, IASI-CNR, Rome, Italy. [43] D. Naddef and G. Rinaldi (1988). The Crown Inequalities for the Symmetric Travelling Salesman Polytope. Report R.249, IASI-CNR, Rome, Italy. To appear in Math, of Operations Research. [44] D. Naddef and G. Rinaldi (1989). The Symmetric Travelling Salesman Polytope and its Graphical Relaxation: Composition of Valid Inequalities. To appear in Math. Programming. [45] G.L. Nemhauser and L.A. Wolsey (1988). Integer and Combinatorial Optimization. John Wiley and Sons, New York. [46] M.W. Padberg and M. Grotschel (1985). Polyhedral Computations. In: E.L. Lawler et al., eds., The Travelling Salesman Problem. (J. Wiley & Sons, 1985), pp. 307-360. Bibliography 143 [47] M.W. Padberg and S. Hong (1980). On the Symmetric Travelling Salesman Problem: a Computational Study. Math. Programming Study 12, 78-107. [48] M.W. Padberg and G. Rinaldi (1987). Optimization of a 532-city Symmetric Travelling Salesman Problem by Branch and Cut. Oper. Res. Letters 6 (1987), 1-7. [49] M.W. Padberg and G. Rinaldi (1991). A Branch-and-Cut Algorithm for the Resolution of Large Scale Symmetric Travelling Salesman Problems. SIAM Review, Vol.33, No.l, pp. 60-100, March 1991. [50] C.N. Potts (1985). A Lagrangean Based Branch and Bound Algorithm for Single Machine Scheduling with Precedence Constraints to Minimize Total Weighted Completion Time. Management Science 31, pp. 1300-1311 [51] W. R. Pulleyblank (1983). Polyhedral Combinatorics, in: A. Bachem, M . Grotschel and B. Korte, edrs, Mathematical Programming: The State of the Art-Bonn 1982, Springer, Berlin, 1983, pp. 101-123. [52] M . Queyranne (1986). Structure of a Simple Scheduling Polyhedron. Working Paper, 1986, Faculty of Commerce, University of British Columbia. To appear in Math. Programming. [53] J.B. Sidney (1975). Decomposition Algorithms for Single Machine Sequencing with Precedence Relations and Deferral Costs. Operations Research 23, pp. 283-298. [54] W.E. Smith (1956). Various Optimizers for Single-Stage Production. Naval Research Logistic Quarterly 3, pp. 59-66. [55] J.P. Sousa, L. Wolsey (1989). Time Indexed Formulations of Non-Preemptive Single Machine Scheduling Problems", CORE discussion paper 8904. Center for Opera- tions Research and Economics, Universite Catholique de Louvain, Belgium. Bibliography 144 [56] S.L. van de Velde (1990). Dual Decomposition of Single Machine Scheduling Problems. Integer Programming and Combinatorial Optimization, proceedings of a con- ference held at the University of Waterloo, May 1990, by the Mathematical Programming Society, edited by Raviv Kanan and W.R. Pulleyblank. [57] L.A. Wolsey (1989). Formulating Single Machine Scheduling Problems with Precedence Constraints. CORE Discussion Paper No. 8924. Center for Operations Research and Economics, Universite Catholique de Louvain, Belgium. Appendix A G e n e r a t i n g the Sample of 280 scheduling problems This appendix contains all relevant information to generate the 280 scheduling problems used in the computational experiments in C h a p t e r 3. A problem generator, coded in FORTRAN, is presented. The problem generator uses the portable random number generators in [9]. To randomly generate an instance of the scheduling problem, one needs to specify five input parameters: the number n of jobs, the maximum processing time (IPMAX (IWMAX = 100 in this study), the maximum job weight = 10 in this study), the P-value, i.e., the probability of including each arc (i, j) with i < j (before the transitive closure is taken), and the seed number for the random generator. The output consists of three parts: (1) the number of jobs, and the number of arcs in the transitive reduction of the precedence graph; (2) the integer job processing times and weights; and (3) the arcs e, represented by their head nodes (TO(e)) and tail nodes (FROM(e)), in the transitive reduction. Tables A . l and A.2 provide the seed numbers used for generating the 280 problems. These numbers are produced as follows. For eachra,one arbitrarily chooses a seed number for the first problem in the group of 20 problems. Then, the random number produced immediately after the completion of the previous instance is used as the seed number for the next problem. This process continues till all instances in the group are produced. Thus, the 280 instances can be easily generated in 14 runs of the problem generator, using a DO loop with relevant parameters in it (note that the P values vary within each group). 145 Appendix A. C C C C C Generating the Sample of 280 scheduling problems PROGRAM FOR GENERATING THE SINGLE-MACHINE PRECEDENCE CONSTRAINED JOB SEQUENCING PROBLEMS. (USING MICROSOFT FORTRAN 5.0) PRECEDENCE MATRIX, PROCESSING TIMES AND JOB WEIGHTS. COMMON NP(200,200),P(200),W(200) INTEGER FR0M(3000),T0(3000) INPUT VARIABLE FORMAT DEFINITION K* C C c c c C C N IPMAX IWMAX PROB NSEED 15 15 15 F5.3 110 NO. OF JOBS MAXIMUM PROCESSING TIME MAXIMUM JOB WEIGHT P VALUE FOR THE PRECEDENCE GRAPH SEED FOR THE RANDOM NUMBER GENERATOR THE FOLLOWING 5 STATEMENTS MAY BE CHANGED IF A DIFFERENT FORTRAN COMPILER IS USED. WRITE(*,*) 'Input data f i l e name?' 0PEN(UNIT=23,FILE=' ') OPEN(UNIT=24,FILE='dg.log') WRITE(*,*) 'Output data f i l e name?' 0PEN(UNIT=25,FILE=' ') C READ(23,100) N,IPMAX,IWMAX,PROB,NSEED 100 FORMAT(315,F5.3,I10) NPOS=0 NAME=NAME+1 DO 33 1=1,N DO 33 J=1,N 33 NP(I,J)=0 DO 10 1=1,N P(I) = IVUNIF(NSEED,IPMAX)*1.0 W(I) = IVUNIF(NSEED,IWMAX)*1.0 IA=I+1 DO 20 J=IA,N PP=UNIF(NSEED) IF(PP.GE.PROB) GOTO 20 NP(I,J)=1 NP(J,I)=1 NP0S=NP0S+1 20 CONTINUE 10 CONTINUE Appendix A. Generating the Sample of 280 schedvhng problems C C C FIND THE TRANSITIVE CLOSURE AHD REDUCTION OF THE PRECEDENCE DIGRAPH. CALL TRANSCR(N,NPOSA) COMPUTE THE ORDER STRENGTH R NPOSTO=NPOS+NPOSA R=(NPOSTO*1.0)/(N*(N-l)*l.0/2.0) WRITE(24,101) N,NC,IPMAX,IWMAX,PROB,R,NSEED 101 F0RMAT(4I5,2X,F5.3,2X,F7.6,2X,110) N1=N-1 NC=0 DO 61 J=1,N1 JA=J+1 DO 62 I=JA,N IF(NP(I,J).LT.l) GOTO 62 NC=NC+1 FROM(NC)=J TO(NC)=I 62 CONTINUE 61 CONTINUE C NC IS THE NUMBER OF ARCS IN THE TRANSITIVE CLOSURE WRITE(25,63) N.NC 63 F0RMAT(3I5) DO 140 1=1,N WRITE(25,150) P(I),W(I) 150 F0RMAT(2F10.2) 140 CONTINUE DO 143 1=1,NC WRITE(25,153) FROM(I),TO(I) 153 F0RMAT(2I5) 143 CONTINUE STOP END Appendix A. Generating the Sample of 280 scheduling problems C C C C C C C C C C C C C C C C SUBROUTIHE TRANSCR(HOP.HPOSA) CONNOI NP(200,200),P(200),tf(200) FIID THE TRANSITIVE CLOSURE AND REDUCTION OF THE GIVEH DIGRAPH REPRESENTED BY NP(I,J). INPUT THE PRECEDENCE GRAPH NP OUTPUT THE UPPER TRIANGULAR OF NP: THE TRANSITIVE CLOSURE THE LOWER TRIAGULAR OF NP: THE TRANSITIVE REDUCTION NPOSA: NO. OF ADDITIONAL ARCS USED IN CONSTRUCTING THE TRANSITIVE CLOSURE NPOSA=0 NT=N0P-2 DO 10 111=1,NT I = NT-III+1 11=1+1 12=1+2 DO 20 J=I2,N0P J0=J-1 DO 30 K=I1,J0 IF (NP(I.K).EQ.O .OR. NP(K,J).EQ. 0) GOTO 30 IF (NP(I.J).NE.l) NP0SA=NP0SA+1 NP(I,J)=1 NP(J,I)=0 30 CONTINUE 20 CONTINUE 10 CONTINUE RETURN END Appendix A. Generating the Sample of 280 scheduling problems FUICTIOI UIIF(IX) C C C C C CC C C C C C C C C C C C C C PORTABLE RANDOM NUMBER GENERATOR IMPLEMENTING THE RECURSION: IX = 16807 * IX MOD (2**(31) - 1) USING ONLY 32 BITS, INCLUDING SIGN. REFERENCE: "A GUIDE TO SIMULATION", P. BRATLEY, B.L. FOX AND L.E. SCHRAGE, 1983, Springer-Verlag New York Inc. SOME COMPILERS REQUIRE THE DECLARATION: INTEGERS IX, K l INPUT: IX = INTEGER GREATER THAN 0 AND LESS THAN 2147483647 OUTPUTS: IX = NEW PSEUDORANDOM VALUE, UNIF = A UNIFORM FRACTION BETWEEN 0 AND 1 Kl = IX/127773 IX = 16807*(IX - Kl+127773) - K l * 2836 IF ( IX .LT. 0 ) IX = IX + 2147483647 UNIF = IX*4.656612875E-10 RETURN END Appendix A. Generating the Sample of 280 scheduling problems FUNCTION IVUHIF(IX,N) C C C C CC C C C C C C C C C C C C C C C C PORTABLE CODE TO GENERATE AH INTEGER UNIFORM OVER THE INTERVAL 1,H USING INVERSION REFERENCE: "A GUIDE TO SIMULATION", P. BRATLEY, B.L. FOX AND L.E. SCHRAGE, 1983, S p r i n g e r - V e r l a g New York I n c . INPUTS: IX = RANDOM NUMBER SEED N = THE UPPER BOUND OF THE UNIFORM INTEGER M = LARGEST VALUE FOR IX + 1 AUXILIARY ROUTINE: UNIF OUTPUTS: IX = NEW PSEUDORANDOM VALUE, IVUNIF = A UNIFORM INTEGER BETWEEN 1 AND N THE RANDOM NUMBER GENERATOR IS ASSUMED TO USE THIS MODULUS DATA M/2147483647/ C JUNK = UNIF(IX) C C C C C C WE WANT INTEGER PART OF IX/(M/N) USING INFINITE PRECISION. FORTRAN TRUNCATION UNDERSTATES M/N, THUS, FORTRAN MAY OVERSTATES WHEN IT COMPUTES IX/(M/N). SO DECREASE JTRY UNTIL JTRY <= IX/(M/N), I.E. M/IX <= N/JTRY. JTRY = IX/(M/N) IF(JTRY .LE. 0) GOTO 500 GOTO 200 100 JTRY=JTRY-1 Appendix A. Generating the Sample of 280 scheduhng problems C C HOW CHECK IF M/IX <= N/JTRY C 200 I = M J = IX K =I L = JTRY C C MORE GENERALLY, IS 1/3 <= K/L, WHERE I>=J, K>=L C IF THE INTEGER PARTS DIFFER THE qUESTION IS ANSWERED. C 300 UI = 1/3 KLI = K/L IF( IJI .LT. KLI ) GOTO 500 IF( IJI .GT. KLI ) GOTO 100 C C MUST LOOK AT THE REMAINDERS; IS IJR/J <= KLR/L C IJR = I - IJI * J IF ( IJR .LE. 0 ) GOTO 500 KLR = K - KLI * L IF ( KLR .LE. 0 ) GOTO 100 C C STILL NOT RESOLVED; REPHRASE IN STANDARD FORM, C I.E. IS L/KLR <= J/IJR? C I = L K = J J = KLR L = IJR GOTO 300 C C NOW ADD 1 TO PUT IN THE RANGE l.N C 500 IVUNIF = JTRY + 1 RETURN END Appendix A. Generating the Sample of 280 scheduhng problems 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 .001 .001 .020 .020 .040 .040 .060 .060 .080 .080 .100 .100 .150 .150 .200 .200 .300 .300 .500 .500 n=30 8913445 755493537 1809917341 1725092278 1822638204 1180075628 150617066 1548235839 373360250 1157536406 94545423 1103566408 206050178 1524763277 581095035 1260330676 2069131884 930436326 575844519 1424549194 n=40 47920113 1617675166 1175781217 1058321011 1046809820 1112508140 1562075571 678966767 1078420215 234794403 1482029273 1539623401 2111547401 525300461 455447345 1553388927 2064816761 849467010 1762170024 1310705738 n=50 19026 1715650722 106619163 946083291 1851494651 35270033 890663124 2111398339 1642491473 1253273425 114463185 1192173437 1080955147 411821081 289919440 1817182748 1622539993 228036027 765120123 1588399166 n=60 85617 1664517790 299964548 1527627754 589620248 305479182 13878902 359148491 554424631 73982478 313191047 829336955 1401168127 1088629889 685524764 1898463718 2139336862 49606783 1988304799 646765699 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 .001 .001 .020 .020 .040 .040 .060 .060 .080 .080 .100 .100 .150 .150 .200 .200 .300 .300 .500 .500 n=70 76815623 1201897528 1630262163 1221144650 18421799 417497068 758772556 107891396 829805974 1807075147 345975380 999548725 698081069 599774400 776266564 2084721901 984818336 1482079848 1692157679 338192698 n=80 4375178 1611982795 697923001 247554449 439147435 234303362 1679599250 1669397446 1558045213 1150686510 985796663 1837490202 1344833772 2128144389 967140344 514443436 2013815749 1460738242 1748668138 1739693055 n=90 350983217 1728743609 236415471 2056300857 668603022 873157283 1467748577 1764811933 387567746 95713841 428865251 427903940 349430181 1808998354 964298149 2089434947 383679383 757904826 728441454 1709478887 n=100 2593 1468695453 1096690315 1630069622 1583467229 782036086 1798123704 2043023199 486855177 1991158124 1426983424 71993197 133879335 1365624620 217047395 1362135656 544616922 2019009597 513041050 387185455 Table A . l : Seeds for the instances with n = 30,40,50,60,70,80, 90,100 152 Appendix A. Generating the Sample of 280 scheduling problems 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 .001 .001 .020 .020 .040 .040 .060 .060 .080 .080 .100 .100 .150 .150 .200 .200 .300 .300 .500 .500 n=110 578 872858166 1966911261 2035263084 1077304999 1367175068 1810714895 1350354151 1145775358 415529128 1992218419 120830678 115769795 392329467 278009491 517310160 1625666109 1168319371 1497262303 81858226 n=120 327819 1896871566 1879863869 1751592867 927231622 1907798662 1892363717 1351713937 1788610971 795452143 1633349205 1207063493 302181295 278166407 1189966678 350462138 66273535 710696277 1172431752 134821562 n=130 7456673 2090383671 613433542 2002449486 1046463762 818258585 1970034241 1274437629 1473953588 62622184 2013606980 731735072 1371935740 830555894 646486032 814653809 1787943512 162859647 2131368145 1849154095 .001 .001 .020 .020 .040 .040 .060 .060 .080 .080 .100 .100 .150 .150 .200 .200 .300 .300 .500 .500 n=140 87485 347175951 2040294373 1031163234 1248974721 1161785585 147857977 559322792 1142323614 1994794676 236427843 309642129 628556917 67336514 1546694624 1908158645 34474010 601131006 405094013 1210698212 n=150 1782437 153399920 1372129829 451762956 1730677699 922885587 1942371325 615429360 2101567237 1030042377 397005716 2127352365 185713150 499856450 747760362 1210383192 96454607 799671032 2130125375 1194121298 n=160 7142 661277793 2105052591 1604032548 1335044189 259379126 1562102629 1301809084 1795967001 1083362231 500851712 809794613 1888704444 623919773 266082890 2086462989 284799641 1756198218 1023000068 597523231 Table A.2: Seeds for the instances with n = 110,120,130,140,150,160 153
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Polyhedral studies on scheduling and routing problems
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Polyhedral studies on scheduling and routing problems Wang, Yaoguang 1991
pdf
Page Metadata
Item Metadata
Title | Polyhedral studies on scheduling and routing problems |
Creator |
Wang, Yaoguang |
Publisher | University of British Columbia |
Date Issued | 1991 |
Description | During the last decade, there have been major advances in solving a class of large-scale real world combinatorial optimization problems. Such problems are formulated as Travelling Salesman Problems (TSP), some involving up to thousands of cities. These achievements, mainly due to the use of so called polyhedral techniques, have established the importance of the polyhedral study for various combinatorial optimization problems. This thesis studies polyhedral structures of two well known combinatorial problems: (i) precedence constrained single machine scheduling and (ii) TSP, both Symmetric TSP (STSP) and Asymmetric TSP (ATSP). These problems are of both theoretical interest and practical importance. Better knowledge of the polyhedral descriptions of these problems may facilitate the polyhedral study of more complex scheduling and routing problems. For the scheduling problem, we present two classes of facetial inequalities, which suffice to describe the linear system of the scheduling problem when the precedence constraints are series-parallel. We also propose a cutting plane procedure based on these facet cuts. The computational results show the procedure yields feasible schedules with relative deviations from the optimum less than 0.25% on the average and less than 1% in the empirical worst case. For TSPs, we explore a Hamiltonian path approach to the polyhedral study. We propose various facet extension techniques for deriving large classes of facets from known facets. In the STSP case, we propose new clique lifting results. In the ATSP case, we develop a Tree Composition method, which generates all non-spanning clique tree facetial inequalities. |
Subject |
Combinatorial optimization Combinatorial analysis |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2011-03-12 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0101095 |
URI | http://hdl.handle.net/2429/32385 |
Degree |
Doctor of Philosophy - PhD |
Program |
Business Administration |
Affiliation |
Business, Sauder School of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- 831-UBC_1991_A1 W36_2.pdf [ 8.77MB ]
- Metadata
- JSON: 831-1.0101095.json
- JSON-LD: 831-1.0101095-ld.json
- RDF/XML (Pretty): 831-1.0101095-rdf.xml
- RDF/JSON: 831-1.0101095-rdf.json
- Turtle: 831-1.0101095-turtle.txt
- N-Triples: 831-1.0101095-rdf-ntriples.txt
- Original Record: 831-1.0101095-source.json
- Full Text
- 831-1.0101095-fulltext.txt
- Citation
- 831-1.0101095.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0101095/manifest