P O L Y H E D R A L S T U D I E S O N S C H E D U L I N G A N D R O U T I N G P R O B L E M S 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 O w ^ e ^ - Bt*o'»ej>s /W/^.^jf^-f,^ The University of British Columbia Vancouver, Canada Date T c ^ \ ? > m/ DE-6 (2/88) Abstract 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 inter-est 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. 11 Table of Contents Abstract ii List of Tables v List of Figures v i Acknowledgement vii 1 Introduction 1 1.1 Preliminaries 2 1.2 Precedence constrained single machine scheduling 4 1.3 Travelling Salesman Problems 7 2 Single Machine Scheduling: Polyhedral 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 3 Single Machine Scheduling: Polyhedral Computations 41 3.1 Introduction 41 3.2 A cutting plane procedure 42 iii 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 4 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 5 Symmetric Inequalities for Asymmetric Travelling Salesman Polytopes 97 5.1 Introduction 97 5.2 Definitions and Notation - 101 5.3 The ATS Polytope and its Projection 104 5.4 Symmetric Facet-defining Inequalities 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 i v List of 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 v i Acknowledgement First, I wish to express my sincere gratitude to Professor Maurice Queyranne for intro-ducing 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 large-scale 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 compu-tations for the precedence constrained single machine scheduling problem. Chapter 3 introduces a cutting plane procedure which uses effective cuts (i.e., facet-defining inequal-ities) derived in Chapter 2. Computational results show that the solution procedure 1 Chapter 1. Introduction 2 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. 1.1 Preliminaries 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 1, • • •, xk G Rn and Ai, • • •, A* G R, the vector x G i f 1 with x = Xix1 + • • • + XkXk is called a linear combination of the vectors x1, • • •, xk. If in addition, Ai + • • • + A* = 1 (resp., all A,- are nonnegative and A H \- Xk = 1), then x is called an affine (resp., convex) combination of the vectors x 1, • • •, xk. 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 1 is called linearly (resp., affinely) independent, if for every finite set {x1, x2, • • •, xk} C S, the equations Aix 1 + h XkXk = 0 (resp., Aix 1 H h \kxk = 0 and Ai 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 R71 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 RJ1 is called full-dimensional 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 € RJ1. A set H € RJ1 is said to be a half space if there exist a vector a 6 RJ1 and a scalar a0 (z R such that H = {x 6 RJ1 : ax < a0}. Then H is the halfspace defined by the 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 < a0 for S is called tight, or supporting, if ax = a 0 for some x 6 S. An inequality ax < ao for S is called an implicit equation if ax = ao holds for all x £ S. A polyhedron is the intersection of finitely many halfspaces. A bounded polyhedron is called a polytope. For any polyhedron V C RJ1, there exist an (m,n)-matrix A and a vector b €E R™ such that V can be represented in the form V = {x <E Rn : 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 = a0}. We say that the inequality ax < a0 defines F or is face-defining for V. A /ace£ F of V is any face of V 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 com-pletion 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]. Spe-cial 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 Relax-ation. 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 polyhe-dra 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 ma-chine 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, dead-lines 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(n2) vari-ables, mostly binary, and 0(n2) or 0(n3) constraints. In this thesis, we consider a formulation of the precedence constrained single schedul-ing problem involving only n variables, one per job. In Chapter 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 Chapter 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(n2) 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 Chapter 1. Introduction 8 circuit C on V , uniquely determined by its corresponding 0-1 incidence vector yc, where = 1 if edge e is used in C and zero otherwise. The STS polytope STSP(V) (resp., ATS polytope ATSP(V')) 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 Pad-berg [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 polyhe-dral study of TSPs. The first one is to reformulate TSPs by relaxing the degree con-straints: 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 clique-lifting [27],[38],[41], [6] for extending TSP facets, and composition [41] techniques for extending STSP facets. Using these approaches, large classes of facet defining inequal-ities 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 Sales-man (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 Hamilto-nian 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 observa-tions 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) poly-hedral 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 Chapter 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 < a0 with coefficients satisfying a,v,- = a^ ,- for all i 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\, • • •, Cn)* to describe schedules of interest. Thus, by letting IN 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 RN : d > P i , Vi G IN; Cj - d > P j , V(», j) G A(N); Ci - d > Vi V Ci - Cj > Pi, 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 prece-dence 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 re-sults. 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, re-spectively. 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 and 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) = {CeRs: d> Pi, Vi E Is; Cj -d> Pj, e A(S); CJ - Ci > P j V d - Cj > pu Vt,j 6 S, j, $ A(S)}. Note now that G(S) specifies precedence relations on job set S and the scheduling poly-hedron 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 ° r all i G S i and j € 52. For any S C JV, 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 G A(N) : i,j G {1,2,3,4}} = {(1,2), (3,2), (3,4)}. Note that a graph G(N) 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 S2. A schedule C G Rs 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., interme-diate) 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. Proposition 2.1 S C N is an initial set of N iff N \ S is a terminal set of N. Proposition 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. Proposition 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. Single Machine Scheduling: Polyhedral Structure 15 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 £ Rs be the subvector of a € RN whose components are those in a indexed by S. Let (S\,S2) be a partition of S. Then by C = (as1,bs2), where a, b £ Rs, we mean that { ak, if k £ Si] bk, if k £ S2. For arbitrary vectors u,v £ RN and subset S C N, we let « ( 5 ) = E « i » « a (s) = E « i > Define also jes jes g(S) = (P(S)2+p2(S))/2, g'(S) = (p(S)2-p2(S))/2. Proposition 2.4 Letwk £ R, k = l,...,n. Let a' £ RN, i = \,..., n = \N\, be n affinely independent vectors satisfying n X wka\ = wo, Vi , (2.1) k=i and let S = {k : wk ^ 0}. Then, 1. There are precisely s = \S\ affinely independent vectors in {a*s : i = l,...,n}; and 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 ((as)', 1); and My be an n by / submatrix of M whose 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 *2 = < ' Wk, if k G S; — W o , if k = n + 1; . 0, 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. • Corollary 2.5 The facet-inducing inequalities for a full dimensional polyhedron P C RN are unique up to some positive multiples. Proof. Since P C RN is full dimensional, there exists no equation satisfied by all points x e P C RN. The result then follows from Theorems 2.5 and 2.6 in Pulleyblank [51]. • 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: Polyhedral Structure 17 2.3 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 RJ1 is a vector of one's. Clearly, C (E P(N) for all y > 0. But ^ k € N wkCk < w0 for y sufficiently large, which produces a contradiction. • 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(SU S2) = -P(S2)p * C(Si) + p(Si)p * C(S2) -p(S2)g(Si) - p(Si)g(S2) + P(S2)p2(Si) > 0 (2.4) is a valid inequality of P(N). 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(S2), (2.5) t 'eSi and (b) implies P(SI) E - 0 > 9(S2)P(Si). (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 S2 = {2,4} U Q . Note that Q may be empty. Proposition 2.8 The following inequalities -p(S')p*C(S'1) + \P({1}UQ)P(S)+P2P3}C2+P3P4C4 > p(S')9'({l,2,3}UQ)+P3Pl, (2.7) - P 1 P 2 C 1 - b({4}ug)p(5)+p2p3]C3-rK^>*c(52) > 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 - C3 > Pl} and T 1 3 = {C G T(JV) : C3 - Ci > p3} • Clearly, T(N) = T31 U r13. C l a i m 1. (2.7) is valid for T 3 1 . Proof. Note that the definition of T 3 1 implies that {3} —> S'. Using Proposi-tion 2.7(ii) with Si = {3} and S2 = S', the inequality - P(S')P3C3 + p3(p * C(S')) > p3g(S') (2.9) is valid for T 3 1 . Using Proposition 2.7(H) again, but with Si = {1} U Q and S2 = {2}, the inequality P(S)[-piCi - p * C(Q) +p({l}U Q)C2] > p(S)g'({1,2} U Q) (2.10) Chapter 2. Single Machine Scheduling: Polyhedral Structure 20 is valid for T 3 1 . The sum of (2.9) and (2.10) yields (2.7). 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 1 3 , we have {1} -+ {3} -> {Q,2,4}. The following two inequalities j*p(S ' ) ( -Ci + C2) > Plp(S')(P2 +P3 + p(Q)), (2.11) PM-C3 + C a ) > P lp3(p2 + p(Q)), (2.12) directly follow from the induced precedence relation {1} —» {3} —» Q —» {2}. Using Proposition 2.7(h) with Si = {3} and 5*2 = S'2, the inequality - P(S'2)P3C3 + P3p * C(52) > P39(S'2) (2.13) valid for T 1 3 . Also, using Proposition 2.7(h) with S\ = Q and S'2 = {2}, the inequality - p(S)P * C(Q) + P(S)p(Q)C2 > P(S)g'({2} U Q) (2.14) is valid for T 1 3 . The sum of (2.11) to (2.14) yields (2.7). This completes the proof for 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 i - C 2 > M and T 4 2 = {C € T(N) :C2-C4> p2}. 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 21 2.4 Structure of the precedence constrained scheduling polyhedra 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 J £ P(N),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). Theorem 2.11 (Face-Lifting Theorem) Let E ^ i > « ) o , (2.16) »es where C € Rs, be an (s — b — 1)-dimensional face-inducing inequality of P(S), where 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 P(N). Proof. Let s = \S\ and = 0, for all i G N \ S. Let FS = {C eP(S):'£wiCi = w0}, SCN. (2.17) First, note that since C G T(N) Cs G T(S), any valid inequality for P(S) induces a valid inequality for P{N), and hence so does (2.16): YlieswiCi ^ wo holds for all C G P(N). Next, let P(S) be represented by a minimal linear system, that is, P(S) = {CeRS : 5>MC,- > a M , h G /}, (2.18) • ies where / is an index set of all facet-inducing inequalities. For face Fs, let Ie = {h€l: = °fco,VC E Fs}. (2.19) Face Fs is an (5 — b — l)-dimensional face of P(S) if and only if matrix Ae with rows a^., h G Ie, has rank 6 + 1 . As observed before, the inequalities ^2ahiCi>ah0, Vh G Ie, are also valid inequalities for P(N). Moreover, these inequalities are tight for all C G FN-Therefore, 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 C3S G Fs, for all j = 1 , s — b. Chapter 2. Single Machine Scheduling: Polyhedral Structure 23 Let CN\S G T(N \ S), and u = max{(CJ)jt : k G S,j = l,...,s - 6}. For all j = 1, ...,s - b, let I (CN\s)i + «, if i G S; ieN\s. Since S is an initial set of JV, by Proposition 2.1, JV \ S is a terminal set of JV. It follows that C'NeT{N),j = i1...,s-b. 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 7 G F^,j — 1 ,n—b, and that they are affinely independent. (2) S is intermediate. Since Fs is (s — b — 1) dimensional, there are 5 — 6 affinely independent schedules, C3S G Fs, j = 1 , 2 , s — b. Let U = {k : k G JV \ S, 3i G S, k -> »}, V = JV \ (5 U U) , and u = Let Cr/ G T(U), Cv G T(V). Let mi = max{(Cr/),- : i G U}, m 2 = mi + max{(Cs); : i G 5, j = 1 , s — b}. Define the following schedules for P(N). For j = u + 1, u + 2 , M + 5 — b, ( {Cu)i, iii E U; (C'N)i = | rm + (Cs~uh if*eS"; I m 2 + (Cv),-, iii EV. 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 C3N 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 £ wkCk > w0 (2.20) keN 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 wk = 0, for allkeN\S. L e m m a 2.13 Let E wkCk > wo (2.21) keN 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 (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 con-taining 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 —> S2 —> • • • —* Sb+i, where 0 < b < n — 1 is the total number of series-compositions in S. Then, FN = {CG P(N) : w * C(S) = w0} is at most (n — b — 1)-dimensional. 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 permu-tation schedule in T(S), and therefore C is tight for all series-inequalities (2.4) induced by the b pairs of sets, (Si -» S2), (S2 - » S 3 ) , —, (Sb - * S&+i), (cf. Proposition 2.7). Assume that we have a finite P(7V)-defining linear system a^C > a^0, h G / , including (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 = aho, h = l,...,b+l. Chapter 2. Single Machine Scheduling: Polyhedral Structure 26 It suffices to show that a ,^ h = l,...,b+l, are linearly independent. Let Ae be the matrix whose rows are a/,, h = 1 , 6 + 1. For any y £ Rb+1 such that ytAe = 0fN, we have 0 = y'A^N = y\w(N), 0 , . . , Of = Vlw(N) and therefore y\ = 0 since w(N) > 0. Further, observe that any square submatrix of Ae 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 Ae are linearly independent, which implies that y2 = ••• = J/6+i = 0. It follows that Ae itself is of rank 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). ^ Theorem 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 Theorem 2.14, and therefore FJV is at most (n — b — l)-dimensional. This further implies, by the Face-Lifting Theorem, 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(Sk), for k = 1 , 2 , 6 + 1 . Chapter 2. Single Machine Scheduling: Polyhedral Structure 27 Let s 0 = "lo = 0, ZQ = 1, and s = \S\ = X)£ti5fc- Recursively define m* = p(Sk) + "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 sk Zk + mk-i, if zk < j < zk + sfc; 7^+mfc-x, otherwise. It is easy to verify that C J G D Fs. Moreover, all C J — C 1 , j' = 2 , 3 , s — 6 are linearly independent. This implies that all C J s are affinely independent, and therefore Fs is (s — 6 — l)-dimensional. Since S is initial, by the Face-Lifting Theorem, FN is (n — 6 — l)-dimensional. • We now turn to the dimension of the face induced by a zero-sum inequality. Theorem 2.16 Let X) tvid > w0 (2.24) 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 FN = {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 AE (defined the same as in Theorem 2.14) is of rank at least max{l, 6} (cf. Theorem 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). Theorem 2.17 For any Si,S2 such that Si —* S2 and S = Sil) S2 is an intermediate set of N, F(Si, S2) = -(p(S2))P * C(Si) + (p(Si))P * C(S2) -piSMSJ - p(Si)g(S2) + P(S2)p2(Si) > 0 (2.25) is a (n — b)-dimensional face-inducing inequality for P(N), 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 Theorem 2.16, and therefore FN is at most (n — fe)-dimensional, since b > 1. This further implies, by the Face-Lifting Theorem, that Fs = {C E P{S) : F(SU S2) = 0} is at most (s - 6)-dimensional. To show that Fs 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 C3 G T(S), j = l,...,s — b in the same way as we do in Theorem 2.15 and let C'-b+1 = C1 + ls. Observe that CJ 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 + 1 Vj = 0 and Ej=i + 1 vjCj = °s, we have s-b+l s-b+1 P* E VjCi = E WW + v*-b+iP(S) = o Chapter 2. Single Machine Scheduling: Polyhedral Structure 29 implying us-6+i = 0, where p* G R" is the processing time vector for job set S. Moreover, since C3,j = l,...,s — 6, are affinely independent, we have Vj = 0,j = l,...,s — b, which implies that CJ,j — 1 , s — 6 + 1, are affinely independent. Therefore Fs is (s — 6)-dimensional. Since S is intermediate, by the Face-Lifting Theorem, Ffi is (n — fe)-dimensional. • Theorem 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. Theorem 2.18 Let £ v>jCj > w0 (2.26) jeN 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 Theorem 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 , C3So G T(So) is a permutation schedule. Thus, C3,j = l , . . . ,n , are tight for the valid inequality p * C(So) > g(S0). Hence, by Corollary 2.5, both (i), i.e., S0 = S, and (iii) follow. Moreover, by Proposition 2.4, we have s = \S\ affinely independent feasible permutation schedules in {C3S : j = 1, ...,n}, which, by L e m m a 2.10, implies (ii). The proof is complete. • Chapter 2. Single Machine ScheduHng: Polyhedral Structure 30 Theorem 2.19 below characterizes which series-inequalities are facet-inducing for P(N). Theorem 2.19 Let £ wkCk > w0 (2.27) be a valid inequality for P(N). Let S be the smallest intermediate set containing S = {ieN: Wi^O}. Assume S = ( S i S 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 S2 is itself series-decomposable; and (iii) (2.27) is a positive multiple of (2.4)-Proof. Sufficiency trivially follows from Theorem 2.17. Necessity Since (2.27) is facet-inducing, we have n affinely independent schedules Cj EFN = {Ce P(N) : w * C(S) = wo}, j = 1 , n . L e m m a 2.13 implies that V j , C3S - tjls 6 T(S), for some tj > 0, are permutation schedules, therefore all C3s are tight for the series-inequality defined by (Si —> S2). By 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 Theorem 2.17, we derive a contradiction: dim(Fjv) = n — b < n — 1. The proof is complete. • Thus, Theorem 2.18 characterizes all positive facet-inducing inequalities for P(N) and Theorem 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'2,S', S", and Q be defined as in Section 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 1 € T(S) be a feasible permutation schedule with sequence (1,3, 2,4). For j = 2,...,q + 2, let C3 be the permutation schedule with job 1 in the jth-position and the rest of the jobs in the same sequence as in C 1 . Further, let Cq+3 be the feasible permutation schedule with sequence (3,4,1, Q, 2), and Cs = Cq+A = C 1 + I 5 . Since C3 — C 1 , j = 2 , s , are linearly independent, schedules C 1 , C , are affinely independent. Next, we can check that Cq+3 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 follow-ing corollary. Corollary 2.21 (1) Parallel inequality (2.3) is face-inducing if and only if S is initial; and 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 Lifting 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,2). These results further lead to a minimal linear system sufficient for scheduling polyhedra when the precedence constraints are series-parallel. L e m m a 2.22 (Facet-Lowering Lemma) Let E mCk > w0 (2.28) 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 CSo - tlSo = C, for some t > 0 (Note, t = 0 if w(S) > 0). Thus, VC € T(S0), W * C(S0) = w * C{S0) > w0. Therefore, (2.28) is also valid for P(S0). Further, by Proposition 2.4, we have |So| affinely independent schedules in {CSo : j = l,...,s}, tight for w * C(SQ) > WQ, where C3,j — 1 , s are s affinely independent schedules in 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 Theorem 2.23 The facet-inducing inequalities for P(S), where S = (S1WS2), are pre-cisely 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 J2) > g(Ii U I2), 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 Theorem), and (iii) (by Theorem 2.18) is sufficient to define a facet of P(S). Conversely, let ^wkCk>w0 (2.29) kes be facet-inducing for P(S) and S = {i E £ : Wi / 0}. If S C Si (resp., S C S2), by the Facet-Lowering Lemma, (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 Theorem 2.18, S is an initial set of S. By Letting Ix = S fl Si and I2 = S ("1 52, (2.29) has representation (iii). The proof is complete. • The following theorem characterizes all facets resulting from series composition. Theorem 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) > P(I)g(T) + P(T)g(I) - p(I)P2(T), (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 Theorem , any facet of P(Si) induces a facet of P(S). (2) Since S2 is an intermediate set of S, by the Face-Lifting Theorem , any zero-sum facet of P(S2) induces a zero-sum facet of P(S). (3) By Theorem 2.19, the given conditions imply that (2.30) induces a zero-sum facet for P(S). Conversely, let J2wkCk>w0, C e i ? 5 , (2.31) kes 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 Theorem 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 Lemma, (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 -»• S2), we have S f) S\ —• S fl S 2. By Theorem 2.19, (2.31) has representation (iii) with T = S D Si and I = S C\ S2. (2) one of SnSi and S (~)S2 is empty. Observe that both Si and S2 are intermediate set of S, by the Facet-Lowering Lemma, (2.31) has one of the representations (i) and (ii). The proof is complete. • As a straightforward consequence of Theorem 2.23 and Theorem 2.24, we have the following. Corollary 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) -(P(S2))p * C(Si) + (p(Si))p * C(S2) >p(S2)g(Si)+P(Si)g(S2)-p(S2)P2(Si), for all non-series-decomposable sets Si and S2 such that S = Si —• S2 is an intermediate 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 Theorem 2.23 and Theo-rem 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 Theorem 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 Theorem 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 lemmata Proof of L e m m a 2.9. Let S = {i : wt ^ 0}. and F = {C e P(N) : w * C(S) = w0}. First, F is an (n — b — l)-dimensional face of P(N) if and only if there are precisely ra — b affinely independent points Ck € F, k = 1 , 2 , n — b. Let Cj € T(N),j = 1 , 2 , m be a minimal collection of affinely independent feasible schedules such that each Ck can be represented by a positive convex combination of C3s. Then, we have Vfc, nt 771 W0 = W* Ck{S) =J2WhYs VkjCh = 12 VkJW * CJ(S) > ">(>, hes j=i i=i Chapter 2. Single Machine ScheduHng: Polyhedral Structure 37 where vkj > 0, Vj, and Y^jLi vkj = 1? which implies that C3 G F, j = 1 , m . Thus, C3s also span the linear hull of F. Hence, dim(F) = n — b — 1 if and only if there are precisely n — b affinely independent schedules in F. The proof is complete. • Proof of L e m m a 2.10. Let s = \S\. Let C3 € Rs, j = 1 , / , be a maximal collection of affinely independent permutation schedules in T(S). Clearly, all C3s are tight for both (2.3) and series-inequality (2.4), 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, C3,j = 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}). for all j = 1 , s — 1, and let C be the permutation schedule in T(S) such that job fc is sequenced last and the rest of the jobs are sequenced the same order as in C 1 . We easily 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 Si U {i} = (S" —> S'") with S'" containing terminal job i, and thus, S = S" —> (S'" U S2), a contra-diction. Therefore, by the induction hypothesis, there are |Si| + 1 affinely independent Sufficiency. Suppose S is series-decomposable, i.e. S = Si —* S2. Define Chapter 2. Single Machine Scheduling: Polyhedral Structure 38 permutation schedules in T(ft U {i}), namely, C3SiU^y, j = 1 , | f t | + 1. Let Cs2 £ ^(ft) be any permutation schedule and define Ci = f (CkuoyU if h e ft U {i}; U C f t J f c + p C f t u O } ) , if/* e f t , for; = l,...,|ft| + l . Let 7r be the permutation induced by C 1 . For |ft| + 2 < j < s, let C-7 be a permutation schedule with job i sequenced at the 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. Therefore, all C3, j — l , . . . ,s, are feasible permutation schedules in T(S). Moreover, since C3 — C 1 , j = 2,3,...,3, are linearly independent, C-7, j = 1 , 2 , s are affinely independent. In either case, we can construct s affinely independent permutation schedules in T(S). The proof is complete. • Proof of L e m m a 2.12. (1) Since (2.20) is facet-inducing, there are n affinely independent schedules, C3 E (^JV"), j = 1 , n , satisfying: £ wkC{ = w0. (2) We claim that wkC{ = 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's)i, if i e ft C l ~ I (Ch\s)i + «, 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, £ wkCk = vi + w0 - vh < w0, keN 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 wk = 0 for all k £ N\S. The proof is complete. • Proof 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, wk = 0, a contradiction. 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 - {Cn(X) -PT(I))^N £ T(N), but w * C(N) = wo — w(N) < WQ, a contradiction. Hence, there is no idle time before C^i) for w(N) > 0. Define f 1, i fx>0 ; 6(x) = [0, iix<0. By Proposition 2.3, Q is a terminal set of I(Q). Let Mc = max{Cjt : k € I(Q)} and Chapter 2. Single Machine ScheduHng: Polyhedral Structure 40 define a schedule C as follows: Ci, iii£l(Q)\Q; Ci =<Ci + Mc(l - S(w(N))), iiieQ; .C,- + 2MC, if 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 = w0 — w(X)u < 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 con-straints, 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(n2) binary variables and 0(n3) 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 con-straint) is introduced in Van de Velde [56]. In spite of these research efforts, one is still unable to solve even medium-sized prob-lems. 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(n2) of binary variables in the integer programming formulations, and (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 pro-cedure. 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 computa-tion 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 polyhe-dron 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 Formulation 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), 7r(i)}, i = 2,3,n. 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 Cut t ing Planes and Separation Algorithms 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 log ra) separation procedure for the scheduling prob-lem with no precedence constraints. Note that the procedure is still valid for the prece-dence 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: Integer ra; 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. Sort JV = {1,...,ra} as JV = (TT(1), . . . , 7r(ra)) in nondecreasing order of the Cj coefficients; 2. Let S' := 0; p := 0; 7 ' := 0; 7 := 0; S := 0; 3. For i :— 1 to ra do begin k := TT(0; S' := S' U {k}; p := p + pk\ i := i + Pk(p - Ck); if 7 ' > 7 then begin 7 : = 7 ' ; S := S' end end 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 o p t = min EieJV^jC'i (3.4) st. Cj — Ci > pj, all nonredundant (3-5) CeQ (3.6) 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: LBP = min wC (3.7) st. 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 < Zopt. 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: LBR = 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: Theorem 3.1 The optimal lower bound in Van de Velde's Lagrangian Relaxation ap-proach 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 S2 in Si —> ft, is a singleton. So, simple series cuts are of the form - p{S2)Cu + p * C(S2) > g(S2), where {u} -> S 2, (3.15) or -p* C(Si) + P(Si)Cv > sftSi U {v}), where Si {v}. (3.16) For simplicity, we denote the simple series inequalities by T(Si, S2) < 0, where Si (resp., S2) is singleton if it is the cut (3.15) (resp., (3.16).), and r(Si,S2) denotes the amount by which the cut is violated. Chapter 3. Single Machine Scheduling: Polyhedral Computations 47 We now develop an 0(n2) separation procedure for the series cuts. To do so, we rewrite the above inequalities in the following equivalent forms: for (3.15), £ Pj(Cj - Cu) > </(ft), where {u} - ft, (3.17) jes2 and, for (3.16), £ Piitv - ti) > 9(Si), where ft -> {u}. (3.18) where = 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 — Cu and restricted to those jobs j that are successors of given job u. For inequality (3.18), one may imagine that all jobs in ft start backward from time tv, and thus have "completion times" tv — t,-. Therefore, it is also in the form of a 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 — Cu as completion 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 fan-out structure requires 0(n2) computational steps. This Simple Series Cut Separation 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 S2, such that S\ —• 52, one of them is a singleton set, and T(5i, 52) is maximized. 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)) in nonincreasing order of the start times tj; 2. [ FORWARD SEARCH ] Let 5' := 0; p := 0; 7' := 0; 7 l := 0; 52 := 0; 3. For 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{? ~Ck + Ci); if 7' > 71 then begin 71 := 7'; 52 := 5', u := i end end; 4. [ BACKWARD SEARCH ] Let 5' := 0; p := 0; f := 0; 72 := 0; Si := 0; 5. For 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 + pk; 7' == i + Pk{p ~ U + h); if 7' > 72 then begin 72 := 7'; Si := S', v := i end end 6. Retrieve inequality r(Si, S2) < 0 from (3) if 71 > 72 and from (5) otherwise. end. Chapter 3. Single Machine Scheduling: Polyhedral Computations 49 3.2.3 Heuristics for the U p p e r Bounds 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 Opti-mal 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 One-Pass 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 Cutt ing 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 > Pj by the nonnegativity constraints on 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 Computational 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 Zopt, that the schedule cannot deviate from the optimal schedule by more than 0.3 percent, since (UB - Z°pt)/Zopt < (UB - LB) I LB < 0.003. To illustrate how the cutting plane procedure works, we begin with two simple nu-merical examples. Chapter 3. Single Machine Scheduling: Polyhedral Computations EXAMPLE 1. Consider Potts' 10-job example [50]. 52 Job i 1 2 3 4 5 6 7 8 9 10 Pi Wi 6 9 1 3 9 5 7 7 6 2 2 5 9 6 5 4 9 3 8 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. i Cut type Violated facet cut LB UB % Gap 1 1 6CX + 9C2 + C3+ 3C 4 + 9C 5 + 7C7 + 6C9 > 987 1526. 1530. 4. 2 P 9C 2 + C3+ 3Ct > 130 1526.7 1530. 3.3 3 SS - 6 C 1 - 9 C 2 - 9C 5 - 7C7 + 31C9 > 543 1527.2 1530. 2.8 4 SS - 6 C 1 - 5C6 - 7C8 + I8C10 > 143 1527.5 1530. 2.5 5 SS - 6 C 1 - 9CS - 7C7 + 22C9 > 291 1528.0 1530. 2. 6 SS - 5 C 6 - 7C8 + 12Cio > 59 1530. 1530. 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 EXAMPLE 2. Consider Wolsey's 30-job example [57]. 53 Job i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 Pi 57 45 50 76 73 82 51 19 82 94 98 15 52 78 75 4 44 89 80 74 43 9 32 2 43 56 27 45 68 63 Wi 9 3 7 1 6 8 6 4 3 6 7 8 9 5 3 5 5 2 5 1 5 1 8 7 7 7 2 5 9 2 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 ) , ( 2, 6), ( 2, 7), ( 3, 8), ( 3, 9), ( 3,13), ( 4, 7), ( 4, 9), ( 5, 8), ( 5,19), ( 6, 9), ( 6,12), ( 7, 8), ( 7,10), ( 7,13), ( 8,11), ( 9,18), ( 9,25), (10,12), (11,15), (11,16), (11,17), (12,17), (12,25), (13,16), (13,17), (13,19), (14,20), (14,21), (14,23), (15,18), (15,20), (17,18), (17,22), (18,21), (18,23), (19,20), (19,21), (19,28), (21,27), (21,29), (21,30), (22,26), (23,24), (24,28), (24,30), (25,28), (26,28), (26,29), (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 54 Iter Cut type Cumul.time L B U B % Gap 0 1.37 56495.1757 123568 118.72310 1 P 1.53 71642.9524 123568 72.47754 2 P 1.81 103696.0370 121799 17.45772 3 P 2.52 116799.2382 121799 4.28065 4 P 2.85 119231.7078 121799 2.15320 5 P 3.02 119329.0365 121799 2.06988 6 SS 3.35 119422.0401 121799 1.99039 7 SS 3.68 119611.9931 121799 1.82842 8 ss 3.95 119623.1333 121799 1.81893 9 ss 4.28 119703.7625 121799 1.75035 10 ss 4.66 119867.9137 121799 1.61101 11 ss 4.99 119959.1578 121799 1.53372 12 SS 5.32 120062.2191 121799 1.44657 13 ss 5.65 120364.2442 121799 1.19201 14 p 5.87 120425.5471 121799 1.14050 15 SS 6.31 120638.8663 121799 .96166 16 SS 6.64 120674.8199 121799 .93158 17 SS 6.97 120811.7984 121799 .81714 18 SS 7.30 120848.5473 121799 .78648 19 SS 7.69 120881.8021 121757 .72401 20 SS 8.07 120904.6679 121757 .70496 21 SS 8.40 120914.2967 121757 .69694 22 SS 8.78 120932.7068 121757 .68161 23 SS 9.11 120941.9816 121757 .67389 24 SS 9.50 120955.3635 121757 .66275 25 SS 9.88 120981.0002 121757 .64142 26 SS 10.27 121001.3894 121757 .62446 27 SS 10.60 121017.5399 121757 .61104 28 SS 10.98 121026.4292 121757 .60365 29 ss 11.53 121031.6281 121757 .59932 30 ss 11.92 121031.7969 121757 .59918 31 ss 12.30 121031.8770 121757 .59912 Table 3.4: Solutions from the cutting plane procedure Chapter 3. Single Machine Scheduhng: Polyhedral Computations 55 Job Schedule Schedule L P Solution L P Solution (optimal) (at iter 31) (final) (at iter 5) 1 57 57 57.0000 57.0000 3 107 107 107.0000 107.0000 2 152 152 234.1205 382.1086 6 234 234 443.1205 527.1086 4 310 310 310.1205 382.1086 7 361 361 361.1205 433.1086 13 413 413 413.1205 485.1086 10 507 599 537.1205 527.1086 12 522 614 552.1205 542.1086 5 595 486 434.1205 433.1086 8 614 505 453.1205 452.1086 11 712 712 623.4538 550.1086 16 716 716 627.4538 554.1086 17 760 760 757.1067 594.1086 22 769 769 766.1067 603.1086 26 825 825 822.1067 659.1086 9 907 907 963.5766 1092.1319 25 950 950 1006.5766 1135.1319 14 1028 1028 1041.5766 1181.1319 15 1103 1103 1116.5766 1092.1319 18 1192 1192 1205.5766 1181.1319 23 1224 1224 1237.5766 1213.1319 24 1226 1226 1239.5766 1215.1319 19 1306 1306 1260.1559 1181.1319 21 1349 1349 1323.5428 1224.1319 29 1417 1417 1391.5428 1292.1319 28 1462 1462 1365.8683 1260.1319 27 1489 1489 1489.0000 1489.0000 30 1552 1552 1552.0000 1552.0000 20 1626 1626 1626.0000 1626.0000 Table 3.5: The optimal schedule and the relevant solutions 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 from ra = 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 sec-ond 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 op-timality. 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 57 n ACT MCT # OPT AGAP MGAP P 30 6.94 14.06 10 .16 .95 .10 40 19.50 75.79 7 .10 .74 .30 50 36.08 72.61 4 .11 .62 .15 60 65.00 133.19 4 .18 .54 .15 70 109.46 214.05 2 .20 .61 .15 80 129.68 246.56 2 .29 .53 .10 90 225.16 562.22 3 .23 .95 .10 100 290.33 530.80 2 .21 .51 .20 110 414.27 1614.70 3 .21 .88 .10 120 466.18 1449.15 2 .35 .96 .06 130 605.82 1888.78 2 .19 .49 .15 140 680.39 1769.81 2 .30 .87 .08 150 851.16 2074.26 2 .30 .67 .08 160 1137.32 3513.58 2 .29 .66 .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 AGAPV 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 Theorem 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 58 p AGAPV A G A P M G A P # O P T .001 0.007 0 0 28 .02 0.069 0.035 0.467 9 .04 0.248 0.098 0.347 4 .06 0.675 0.248 0.962 2 .08 1.076 0.329 0.872 1 .10 1.518 0.408 0.952 0 .15 2.024 0.409 0.794 0 .20 2.113 0.303 0.860 1 .30 3.733 0.263 0.756 0 .50 4.116 0.154 0.359 2 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. Com-putation 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 proce-dure 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 defin-ing 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 Computations 3.4 Computational Results for 280 problems #Jobs Name P Oid.Sth. # Arcs # Cuts CT % Gap Statistic 30 1 .001 .00460 2 1 2.36 .00000 AGAP 2 .001 .00000 0 1 2.42 .00000 .1589 3 .020 .03678 11 2 3.13 .00000 4 .020 .03448 9 1 2.36 .00000 ACT 5 .040 .07356 22 2 3.57 .00000 6.938 6 .040 .03218 10 2 2.97 .00000 7 .060 .06667 23 4 3.74 .00000 8 .060 .06207 21 7 4.95 .00000 9 .080 .11954 29 6 4.62 .21058 10 .080 .14483 32 22 8.34 .03627 11 .100 .17931 34 24 9.01 .32752 12 .100 .30575 42 26 10.82 .95170 13 .150 .38621 50 24 10.16 .34220 14 .150 .48736 54 24 11.09 .26927 15 .200 .57701 52 16 6.26 .00000 16 .200 .55632 45 18 9.40 .08065 17 .300 .62299 59 29 14.06 .41234 18 .300 .69425 54 20 9.72 .42745 19 .500 .88046 46 23 10.88 .12030 20 .500 .91035 45 20 8.90 .00000 40 1 .001 .00000 0 1 3.90 .00000 AGAP 2 .001 .00128 1 1 3.90 .00000 .0958 3 .020 .03590 23 9 8.63 .00000 4 .020 .01795 12 1 3.90 .00000 A C T 5 .040 .09615 34 14 11.53 .00462 19.4955 6 .040 .04231 27 10 9.01 .00000 7 .060 .18718 55 33 17.42 .04461 8 .060 .14231 32 17 17.30 .09125 9 .080 .12308 54 45 24.00 .00000 10 .080 .24359 52 36 19.28 .02760 11 .100 .30641 61 33 18.89 .07638 12 .100 .21410 66 28 16.53 .23652 13 .150 .42180 73 26 15.60 .08634 14 .150 .53590 72 35 22.13 .14889 15 .200 .63974 74 36 21.36 .09571 16 .200 .56923 83 28 18.51 .20624 17 .300 .78718 80 26 16.87 .02668 18 .300 .79487 74 27 36.69 .74286 19 .500 .90256 62 55 75.79 .12927 20 .500 .93333 66 37 28.67 .00000 Table 3.8: Computational results for n — 30,40 Chapter 3. Single Machine ScheduHng: Polyhedral Computations 61 #Jobs Name P Ord.Sth. # Arcs # Cuts CT % Gap Statistic | 50 1 .001 .00000 0 1 5.71 .00000 AGAP 2 .001 .00082 1 1 5.93 .00000 .1069 3 .020 .02122 20 1 6.26 .00000 4 .020 .03429 28 5 10.10 .00646 A C T 5 .040 .07429 50 56 43.72 .00000 36.076 6 .040 .12408 62 43 29.44 .06609 7 .060 .13061 67 56 43.28 .02668 8 .060 .13796 65 56 41.80 .04592 9 .080 .25633 80 42 30.75 .09488 10 .080 .22531 76 49 36.74 .05686 11 .100 .28082 84 39 28.23 .11125 12 .100 .40082 74 47 36.47 .15972 13 .150 .54857 108 51 42.62 .25105 14 .150 .62939 83 58 51.63 .62363 15 .200 .73714 87 55 49.10 .29168 16 .200 .70612 99 48 44.10 .25035 17 .300 .83918 79 30 26.20 .01573 18 .300 .83347 90 58 63.93 .11547 19 .500 .95510 67 44 72.61 .02199 20 .500 .95020 75 48 52.89 .00095 60 1 .001 .00113 2 1 8.96 .00000 AGAP 2 .001 .00169 3 1 10.16 .00000 .1754 3 .020 .06497 46 26 36.47 .00000 4 .020 .02260 33 40 64.98 .00000 ACT 5 .040 .06328 64 66 63.39 .00242 64.996 6 .040 .08362 70 73 69.70 .02342 7 .060 .19209 88 55 50.69 .11333 8 .060 .22712 96 72 69.04 .47417 9 .080 .32090 94 67 65.36 .14805 10 .080 .31808 107 52 53.28 .16912 11 .100 .49378 118 63 69.32 .36744 12 .100 .44350 113 54 62.67 .24633 13 .150 .61582 119 48 56.03 .53784 14 .150 .62429 120 69 86.34 .54094 15 .200 .71073 122 61 81.84 .15449 16 .200 .69661 111 84 112.76 .22352 17 .300 .84746 106 60 81.94 .10690 18 .300 .85254 116 78 133.19 .29882 19 .500 .94237 99 60 79.64 .01473 20 .500 .94915 89 35 44.16 .08674 Table 3.9: Computational results for n = 50,60 Chapter 3. Single Machine Scheduling: Polyhedral Computations 62 #Jobs Name P Ord.Sth. # Arcs # Cuts CT % Gap Statistic 70 1 .001 .00041 1 1 12.36 .00000 AGAP 2 .001 .00041 1 1 12.03 .00000 .1951 3 .020 .03064 43 57 108.31 .00975 4 .020 .02650 39 25 105.08 .46689 ACT 5 .040 .11511 87 103 139.84 .00377 109.46 6 .040 .08861 94 81 106.22 .10148 7 .060 .17143 112 86 108.64 .01781 8 .060 .22485 119 76 94.86 .09505 9 .080 .34576 147 65 84.80 .18851 10 .080 .31387 139 58 68.76 .34954 11 .100 .42774 163 79 108.86 .19217 12 .100 .56522 138 70 98.21 .20274 13 .150 .64306 138 106 169.00 .61276 14 .150 .60373 148 66 82.71 .23170 15 .200 .82650 132 82 138.85 .34946 16 .200 .76563 145 42 97.98 .40806 17 .300 .89151 139 78 131.76 .27388 18 .300 .87992 140 75 196.91 .18546 19 .500 .95694 111 57 214.05 .09142 20 .500 .96398 105 40 109.91 .12117 80 1 .001 .00158 5 1 17.31 .00000 AGAP 2 .001 .00063 2 1 16.09 .00000 .2870 3 .020 .04620 75 46 110.13 .10601 4 .020 .04620 60 19 47.79 .03868 A C T 5 .040 .06709 107 120 221.19 .00306 129.68 6 .040 .17690 125 95 132.75 .17918 7 .060 .28196 168 113 175.32 .22464 8 .060 .22722 160 64 117.37 .36282 9 .080 .46171 170 71 109.24 .25996 10 .080 .34240 170 65 98.75 .71447 11 .100 .36266 183 61 99.08 .15841 12 .100 .46772 185 78 126.77 .53486 13 .150 .72468 174 83 157.80 .45760 14 .150 .70949 168 84 165.54 .41877 15 .200 .78798 162 83 154.67 .39464 16 .200 .72089 206 76 146.54 .38601 17 .300 .91994 132 19 70.74 .75583 18 .300 .85886 158 83 246.56 .43060 19 .500 .95285 122 39 171.69 .23316 20 .500 .95601 136 82 208.22 .08160 Table 3.10: Computational results for n = 70,80 Chapter 3. Single Machine Scheduling: Polyhedral Computations 63 #Jobs Name P Oid.Sth. # Arcs # Cuts CT % Gap Statistic 90 1 .001 .00050 2 1 22.36 .00000 AGAP 2 .001 .00050 2 1 20.38 .00000 .2290 3 .020 .03071 72 140 562.22 .00000 4 .020 .03845 87 94 310.38 .01671 ACT 5 .040 .11261 156 107 192.23 .08633 225.14 6 .040 .10786 140 102 206.74 .13070 7 .060 .24145 177 92 162.97 .11381 8 .060 .25368 171 97 167.64 .26182 9 .080 .36654 205 70 131.55 .47914 10 .080 .41973 182 92 208.00 .54811 11 .100 .50737 200 78 175.93 .95225 12 .100 .56105 207 74 161.43 .35829 13 .150 .72584 216 108 298.19 .59628 14 .150 .70212 205 98 215.64 .32440 15 .200 .81248 202 103 244.26 .18701 16 .200 .76405 207 81 221.79 .16728 17 .300 .87965 169 96 265.67 .13002 18 .300 .87590 194 114 321.92 .20084 19 .500 .97129 129 73 284.40 .00510 20 .500 .96404 145 82 329.00 .02184 100 1 .001 .00081 4 1 24.71 .00000 AGAP 2 .001 .00101 5 1 25.65 .00000 .2095 3 .020 .04525 99 60 199.71 .05779 4 .020 .03030 89 99 530.80 .01623 A C T 5 .040 .10101 162 148 389.54 .08459 290.33 6 .040 .09677 170 122 269.68 .05475 7 .060 .23899 213 106 222.06 .17924 8 .060 .30929 209 129 265.18 .06981 9 .080 .43495 218 105 218.50 .30606 10 .080 .45394 228 110 243.71 .25238 11 .100 .57737 239 126 418.37 .30853 12 .100 .50202 233 109 250.13 .37136 13 .150 .73960 209 126 372.78 .43368 14 .150 .75414 218 141 449.40 .48349 15 .200 .83778 200 90 320.55 .19209 16 .200 .79859 217 126 381.19 .51074 17 .300 .91515 188 67 376.02 .27127 18 .300 .92222 178 87 461.76 .18564 19 .500 .96606 164 56 232.22 .12527 20 .500 .97030 157 53 154.68 .28807 Table 3.11: Computational results for n = 90,100 Chapter 3. Single Machine Scheduling: Polyhedral Computations 64 #Jobs Name P Ord.Sth. # Arcs # Cuts CT % Gap Statistic 110 1 .001 .00050 3 1 30.43 .00000 AGAP 2 .001 .00100 6 1 30.05 .00000 .2101 3 .020 .04087 110 317 1614.70 .00000 4 .020 .05588 129 222 813.66 .00948 A C T 5 .040 .26539 201 113 289.51 .07890 414.27 6 .040 .17831 205 102 245.90 .05274 7 .060 .31793 271 94 233.10 .21554 8 .060 .32127 266 114 288.90 .46806 9 .080 .44671 285 102 245.14 .19019 10 .080 .48791 276 97 256.06 .24626 11 .100 .66806 241 156 459.94 .23973 12 .100 .58415 294 108 348.67 .88693 13 .150 .75113 268 109 308.46 .24279 14 .150 .75663 256 109 488.46 .29757 15 .200 .84304 232 116 456.71 .40698 16 .200 .84871 237 132 397.77 .21956 17 .300 .90142 223 34 166.75 .41074 18 .300 .92410 206 115 540.19 .04542 19 .500 .97448 173 86 570.29 .13094 20 .500 .96931 162 91 500.76 .06043 120 1 .001 .00140 10 1 42.85 .00000 AGAP 2 .001 .00084 6 119 768.46 .00000 .3466 3 .020 .05574 154 205 909.18 .04924 4 .020 .03529 126 265 1449.15 .00363 ACT 5 .040 .28123 261 124 352.18 .14214 466.18 6 .040 .23193 236 136 494.98 .16975 7 .060 .36807 279 124 389.59 .96183 8 .060 .41583 300 111 311.48 .19506 9 .080 .52507 304 104 327.85 .55736 10 .080 .52563 305 104 567.11 .40434 11 .100 .64160 282 111 334.94 .27584 12 .100 .62661 304 121 422.11 .70647 13 .150 .74776 313 132 475.77 .68209 14 .150 .80924 257 50 237.55 .69801 15 .200 .84566 258 75 524.92 .76291 16 .200 .85294 267 105 463.24 .33794 17 .300 .92031 229 52 234.37 .29232 18 .300 .91681 239 50 301.60 .37252 19 .500 .98039 176 38 183.45 .22883 20 .500 .97521 186 68 532.78 .09273 Table 3.12: Computational results for n = 110,120 Chapter 3. Single Machine Scheduhng: Polyhedral Computations 65 #Jobs | Name P OrcLSth. # Arcs # Cuts CT % Gap Statistic 130 1 .001 .00143 12 45 264.53 .00000 AGAP 2 .001 .00119 10 13 114.96 .00000 .1888 3 .020 .04568 168 296 1726.70 .03171 4 .020 .04770 153 312 1888.78 .05270 ACT 5 .040 .17197 291 145 445.51 .11493 605.82 6 .040 .13787 274 118 390.14 .06434 7 .060 .41145 321 68 291.05 .44764 8 .060 .42922 302 76 300.77 .34043 9 .080 .52009 344 103 332.69 .25293 10 .080 .56947 301 129 445.23 .25269 11 .100 .68515 322 130 527.62 .33697 12 .100 .64782 329 103 471.09 .37895 13 .150 .75826 332 149 627.36 .49034 14 .150 .79165 322 115 407.88 .17745 15 .200 .87871 265 115 589.68 .15636 16 .200 .86094 292 110 524.70 .11167 17 .300 .94252 231 123 1051.00 .12904 18 .300 .90912 288 170 773.95 .17247 19 .500 .97865 194 77 485.10 .07439 20 .500 .96923 219 76 457.75 .19034 140 1 .001 .00113 11 1 64.15 .00000 AGAP 2 .001 .00082 8 124 1180.68 .00000 .2956 3 .020 .05704 181 304 1769.81 .02924 4 .020 .06495 199 259 1342.71 .07154 ACT 5 .040 .22354 332 150 571.00 .28460 680.39 6 .040 .19168 297 139 581.77 .14907 7 .060 .46218 326 187 647.36 .31147 8 .060 .46578 321 134 525.03 .31678 9 .080 .54820 354 153 643.45 .40014 10 .080 .52795 368 149 601.05 .87223 11 .100 .69239 372 113 567.71 .36579 12 .100 .68612 325 152 775.33 .58323 13 .150 .77359 354 113 527.67 .09663 14 .150 .82867 304 40 217.95 .79355 15 .200 .84327 347 154 858.60 .14770 16 .200 .86218 312 32 257.88 .86032 17 .300 .94132 278 162 1052.65 .11478 18 .300 .93731 291 59 361.58 .15913 19 .500 .97718 225 87 593.25 .13079 20 .500 .97811 218 55 468.07 .22498 Table 3.13: Computational results for n = 130,140 Chapter 3. Single Machine Scheduling: Polyhedral Computations 66 #Jobs Name P Oid.Sth. # Arcs # Cuts CT % Gap Statistic 150 1 .001 .00107 12 119 1112.90 .00000 AGAP 2 .001 .00125 14 125 1194.52 .00000 .3038 3 .020 .05145 223 344 2074.26 .00365 4 .020 .05414 219 268 1613.16 .00618 A C T 5 .040 .20546 354 151 585.62 .34732 851.16 6 .040 .22407 326 156 537.89 .14711 7 .060 .48054 388 157 671.85 .49276 8 .060 .41682 422 117 583.81 .20610 9 .080 .53127 437 154 692.94 .66706 10 .080 .61494 405 156 847.50 .63095 11 .100 .69942 388 105 653.78 .71995 12 .100 .69110 389 124 682.55 .21691 13 .150 .80143 370 81 443.47 .38478 14 .150 .83400 338 151 934.89 .22556 15 .200 .88143 326 209 1729.00 .34891 16 .200 .88608 330 60 449.67 .58260 17 .300 .93709 279 51 430.12 .42886 18 .300 .94622 280 116 1051.93 .15777 19 .500 .97888 236 58 296.93 .14922 20 .500 .98201 231 46 436.44 .35984 160 1 .001 .00087 11 1 112.16 .00000 AGAP 2 .001 .00126 15 129 2280.40 .00000 .2889 3 .020 .06022 233 289 2005.44 .01548 4 .020 .05299 220 402 3513.58 .01715 ACT 5 .040 .26832 386 160 633.40 .20351 1137.32 6 .040 .24772 369 150 591.05 .24819 7 .060 .38585 474 142 625.27 .34809 8 .060 .48884 429 112 738.20 .54318 9 .080 .58530 426 111 625.88 .39843 10 .080 .61580 423 152 921.66 .42387 11 .100 .71069 394 176 950.65 .72379 12 .100 .73538 396 107 698.43 .43946 13 .150 .81942 406 210 1544.83 .66236 14 .150 .83561 392 166 1100.38 .34659 15 .200 .89285 357 75 628.79 .41888 16 .200 .89222 345 191 1288.22 .24187 17 .300 .93789 327 158 1277.35 .19612 18 .300 .93931 325 86 1132.02 .21530 19 .500 .98608 223 56 384.31 .17023 20 .500 .98019 251 113 1694.40 .16632 Table 3.14: Computational results for n = 150,160 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 gen-eral 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 gener-alize 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 rep-resents 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 £ RE(V') (where ye = 1 if edge e is used in C and zero otherwise). This 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 ex-cellent 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], Fleis-chmann [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 inde-pendently 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 facet-defining 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 trav-elling 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 RE(V) of RE(V'\ More importantly, HP(V) exhibits three fundamental properties for this projective approach: (a) HP(V) is near-full dimensional, with a single implicit equation 52eeE(V) 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 69 equivalence: the polyhedral structures of HP(V) and STSP(V) 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 ATS 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(S1 : S2) = {(ij) <E E(V) : i € Slyj <E S'2}. 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 £ RE^ such that \e = 1 if e G E and Xe = 0 otherwise. For any vector ij> G RE^ and E C E(S), let 4>(£) = 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 \ECl£{v)\ = 2, for all r; G S. Without risking confusion, a Hamiltonian cycle C with edge set E = : * = l , - , ^ - 1} U {(tty.), «„(!))} on node set S = {v\,vs} C V may be represented by edge set E alone or, equivalently, by the circular permutation (u<7(i)...i>o-(a)) of the nodes. A Hamiltonian path P on S = {vi,...,vs} C V is a connected partial graph (S,E) 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,-, ut+i) : i — l,...,s — 1} or, equivalently, by its corresponding node permutation (vi...va) with endnodes v\ and va. Note that if l^l = 1, the first form is an empty set, whereas the 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) = conv {yc G R?W : C is a Hamiltonian cycle on 5}, HP(S) = conv{xp G RE(S) : P is a Hamiltonian path on 5}. (3). To any inequality cx < CQ with c > 0 and x G RE(S\ we associate its support graph: Ge(S) = (5, E c), where Ec = {ee E(S) : ce > 0}. The complement graph GC(S) = (S,EC), where _EC = E(S) \ Ec, is called the zero-graph w.r.t. cx < CQ. Chapter 4. Hamiltonian Path and Symmetric Travelling Salesman Problem 72 (4). Let ay < ao and cx < Co be two valid inequalities for STSP(S) 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 ayc = a0 (resp., if P is a Hamiltonian path on S and cxp = Co). 4.3 Polyhedral 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)) and K(V) = (V',E(V)). That is, K(V) is obtained from K(V) by eliminating node h £ V and all incident edges. Let STSP(V) be the STS polytope defined on K(V), and HP(V) be the HP polytope defined on K(V). 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 xp £ RE(V) is a projection of the incidence vector yc £ RE(V>) onto subspace REW of RE<y'\ It follows that the polytope HP(V) is a projection of STSP(V). In what follows, we assume that all incidence vectors y on K(V) are indexed as: y = ( j / i , y m , t / m + i , y m ' Y i where the first m = n(n — l)/2 elements correspond to the edge set E(V). 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 yc G RE(V') of all Hamiltonian cycles C on V and their projections xp G RE^ satisfy the following identity: (u,v)eE(V); (4.2) 2 - ZeeE(v)(An)vex?, (u, t;) G E{h : V). 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 By = [y1,yl] be any matrix such that all column vectors y3 are in-cidence vectors of Hamiltonian cycles on K(V'). Let Bx = [x1,xl], where x3 is the projection of y3 into RE(V\ j = 1 , / . Then the number of affinely independent column vectors in By is equal to the number of affinely independent column vectors in Bx. Proof: From equation (4.2), it follows aff.rank ( J?„ ) = / > rank rank / it \ > rank V l V \ Bx J = aff.rank a , 1 0* I v \ 0 1 I = rank 2 -An 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 74 Theorem 4.2 The dimension of HP(V) is: dim(HP(V)) = ^ ~ ^ - 1, w/iere n = > 3. (4.3) Proof. Since every Hamiltonian path P on V must satisfy implicit equation xp(E(V)) = 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\, e2 E ^(^)5 there exists a Hamiltonian cycle C in K(V) containing e\ and e2. Since P 1 = C \ ei and P 2 = C \ e2 are two Hamiltonian paths in -RT(V), 0 = fxpl - fxp2 = /„ - / e i . This shows that / e is constant for all e £ -E^) , and equation fx = fo must be a multiple of implicit equation x(E(V)) — n — 1. • Remark 4.3 By Theorem 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 de — ace + 0 for all e 6 ^(V"). This equivalence greatly simplifies indirect proofs of facetial results for HP(V). • Corollary 4.4 The dimension of STSP(V) is: dim(STSP(V')) = 1 } - (n + 1). (4.5) Proof. From L e m m a 4.1 and Theorem 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 Remark 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 pos-itive 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 2_*_ ~hf\ ( ( d U U ) < 9 (a) An Envelope 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-dd1 = 0, etc. Now, we turn to relationships between valid inequalities for STSP(V) and those for HP(V). Recall that V \ V = {h}. Consider two inequalities ay < a0 and ex < Co, defined on STSP(V) and HP(V), respectively, and satisfying: aQ = co ; ae = ce> 0, Ve G E(V); and ae = 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 < aQ is an extension of ex < Co. By L e m m a 4.1 and Theorem 4.2, we have immediately: (b) /^ -normal form (c) Zi'-normal form Chapter 4. Hamiltonian Path and Symmetric Travelling Salesman Problem 76 Theorem 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 Remark 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. ^-normal form. An inequality ay < a0 for STSP(V) is in normal form w.r.t. a given node h £ V (^-normal form, for short) if (Cl) ae = 0 for all e £ E({h} : V \ {h}); (C2) a > 0 and ae = 0 for some e € E(V \ {h}); (C3) min{ae > 0 : e £ E(V')} = 1. Inequality cx < CQ for HP(V) is in normal form if its extension ay < a0 for STSP(VU {h}), where h V, is in fe-normal form. See Figure 4.1 for examples. Remark 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 dif-ferent scaling in (C3). Such forms can also be obtained by applications of Remark 4.2 of Grotschel and Padberg [27]. • Any valid inequality ay < a0 for STSP(V) 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. ^-Normalization procedure Input: A valid inequality ay < a0 for STSP(V), where \V'\ = 71 + 1, and any given projection node h £ V. Chapter 4. Hamiltonian Path and Symmetric Travelling Salesman Problem 77 Output : An equivalent valid inequality a'y < a'Q for STSP(V) in /i-normal form. Step 1: /i-Projection. Adding to ay < a0 the following linear combination of degree constraints: £ -avhy(S(v)) = £ -2avh v£V'\{h} vev\{h} yields ay < ao. Note that after the projection, ae = 0 for all e G 8(h). Step 2: Shifting. Adding to ay < a0 the implicit equation Xy(E(V'\{h})) = \(n - 1), for STSP(V), where A = -min{a e : e G £ ( V \ {h})}, yields ay < do. Note that after shifting, d0 = d0 + A(n — 1), a, > 0, and de = ae + A if e G i5(V \ {/i}) and zero otherwise. Note also that for some e(EE(V'\{h}), ae = 0. Step 3: Scaling. The scaling operation is defined by (a',a'0) = (a,a0)/7, where 7 = min{ae > 0 : e G F(y)}. For instance, Fig. 4.1(a) represents inequality ay < a0. After the normalization 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'0 be the /i-normal form of aV < °o for STSP(V), and let ex < CQ be the ^-restriction of a'y < a'0. Then ex < CQ for HP(V \ {h}) is an h-projected inequality or h-projection of ay < ao. Two important observations immediately follow from the above procedure. First, the normalization procedure requires 0(E(V')) 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'0 satisfy: a' > 0, a'e = 0 for all e G 6(h) and a'e = 0 for some e G E(V \ {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'0 is in support-reduced form, and therefore o'y < a'o is facet-defining for the monotone STS polytope MTSP(V) if it defines a nontrivial facet of STSP(V). Remark 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 facet-defining inequalities for HP(V). Proposition 4.9 Let S(v) = E({v} : V \ {v}) for all v G V, and let n = \V\. The following is a system of facet-defining inequalities for HP(V), where n > 4, no two of which are equivalent. Chapter 4. Hamiltonian Path and Symmetric Travelling Salesman Problem 79 (a) xe > 0, 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 xvh < 1 (resp., xvh > 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 Trivial Facets. Inequality ay < a0 defines a trivial facet of STSP(V) if it is equivalent to ye > 0 for some e G E(V). (cf. [26,29]) H P P Trivial Facets. Inequality cx < CQ defines a trivial facet of HP(V) if it is equiv-alent either to xe > 0 (with normal form: x(E(V) \ {e}) < |V| — 1) for some e G E(V) or to x(S(v)) < 2 for some v G V. (cf. Proposition 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 HP(V). Then Chapter 4. Hamiltonian Path and Symmetric Travelling Salesman Problem 80 (1) for every edge e E E(V), 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 xe > 0 for some e E E(V). (2) holds since otherwise cx < CQ is equivalent to x(S(v)) < 2 for some v EV. • 4.4 Clique-Lift ing 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 ui ,u 2 , . . . ,u / E U with U\ = p and u/ = q such that u,- and u , + i are c-adjacent 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 < aQ be a valid inequality for STSP(V) and cx < Co be its h-projection for HP(V), where V = V \ {h}. Then the following statements are equivalent. (1) V is c-connected. 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 facet-defining HPP inequality ex < CQ is given below. L e m m a 4.12 (Sufficient Condition for c-Connectedness) Letcx < CQ define a non-trivial facet of HP(V) with c>0, and let GC(V) be its zero-graph (cf. (3) in Section 2). Suppose that the set U C V induces a connected subgraph GC(U) of GC(V). 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 GC{U) is connected, there exists a c-adjacent node 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,tv for all v E V \ {h,t}, and (C2) aht = m&x{auh + avh — auv : 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 (Clique-Lifting, Zero-Lifting and Node-Cloning) . Let ay < a0 be a valid inequality for STSP(V). For any given h E V, define clique weight £ = max{aih + ajh - 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 < a0 w.r.t. to node h if aj = a 0 + and au v, u E V, v E V ; <C= j ahv, ueS, veV\{h}; (4.7) £, u E S U {/i}, u E 5U{fe}. It is a zero-lifting if £ = 0. It is called node-cloning if |5| = 1. The facet-defining inequality ay < a0 is clique-liftable (resp., node-clonable) w.r.t. 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 12 15 (a) A primitive bipartition inequality h', s' h, s (b) A lifted bipartition inequality Figure 4.2: Facet-defining bipartition inequalities L e m m a 4.13 (Property of a Node-Cloned Inequality) Let ay < a0 be an inequal-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\s = a*s = a^t. Proof: Since h and t form a clone pair, node-cloning of ay < a0 w.r.t. h yields a*hs = max{a,fc + ajh - a{j :i,jeV'\ {h}, i ^ j} = max{a/lt,max{aht + ahv — atv : v 6 V \ {h, t}}} = aht-Similarly, we show that a*s = aht- a L e m m a 4.14 (Validity of Clique-Lifting) Let ay < a0 be any valid inequality for STSP(V), and let the inequality a*y* < be obtained by clique-lifting ofay < a0 w.r.t. any given node h. Then a*y* < 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*) - aus - avs + auv = a*(C*) - auh - avh + auv > - a*h3 = a0, 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 > b0 in tight triangular form. Recall the definition of this form below. 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 buv < buw-\-bwv holds; and (T2) for any w £ V, there exists a pair of nodes u, v £ V \ {w} such that buv — bum ~\~ bwv. ' Note that any STSP inequality has a unique (up to positive scaling) TT-representation. Proposition 4.15 (Characterizations of Primitive Inequalities) Let ay < a0 be any valid inequality for STSP(V). For any node h £ V, let ahy < a§ be the h-normal form of ay < ao and Gah(V) be its support graph. Then the following statements are equivalent: (a) ay < a0 is a primitive inequality. (b) There exists no clone pair w.r.t. ay < a0. (c) The support graph Gah(V) 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 < a0 iff both h and t are isolated nodes in Gah(V). The latter is equivalent to bht = 0, proving (c) (d). • From this proposition, it follows that node-cloning of ay < a0 w.r.t. 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. Theorem 4.16 (Clique-Lifting with IS*! > 2) Let ay < ao be any nontrivial facet-defining inequality for STSP(V). Then, inequality a*y* < aj obtained by clique-lifting of ay < a 0 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*Q is valid. Let V = V \ {h}. Let cx < Co and c*x* < CQ be the ^-projections of ay < a0 and a*y* < a|J, respectively. By L e m m a 4.13, L e m m a 4.14 and Proposition 4.15, c*x* < CQ is a valid inequahty for HP(V U S) with c^ = Co; c* = ce for all e £ E(V) and zero otherwise. Let fx* < fQ 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 / e = 0 for all e £ E(5') U E{S : V). (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 f0 = /(P*) = f(P) + p\S\ for all c-tight path P on V. Since cx < Co is facet-defining, there exist two scalars a > 0 and 7 such that fe = ace + 7 for all e £ E(V). Next, since cx < C Q is in normal form, there exists e = (p, q) £ i£(V) such that ce = 0. Let (u...pq...v) be a c-tight path on V and let (ij...k) be a 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 Remark 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 86 For any nontrivial facet-defining inequality ay < a0 for STSP(V) 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 com-pleteness. Proposition 4.17 (Sufficient Condition for Node-Cloning) Let ay < a0 define a nontrivial facet for STSP(V), and let cx < CQ be its h-projected inequality for HP(V), where V = V'\ {h}. 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 U {s}). Proof: Note first that V is c-connected by L e m m a 4.11. Now, let c*x* < c^ be an /^ -projected inequality of a*y* < a„ and fx* < f0 be a facet-defining inequality for 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. Comparing the c*-tight paths P 1 = (u...vs) and P2 = (su...v) yields /„„ = fvs. Since V is c-connected, we deduce that there exists some scalar /3 such that 0 = fvs 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 - f t it follows that for some scalars a > 0 and 7, we have fe = ace + 7 for all e 6 E(V). The rest of the proof is similar to the last part of the proof of Theorem 4.16: since cx < CQ is in normal form, there exists an edge (p, q) £ E(V) with Cpq = 0. Let (u...pq...v) be a c-tight path on V. Comparing the c*-tight paths (u...pq...vs) and (q...vsu...p) on FU{s} yields 7 = fpq = fus = 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. Corollary 4.18 (Lifting of Clone Pairs) Let ay < a0 define a nontrivial facet of STSP(V) 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 < a0 w.r.t. h (or t) is facet-defining. Proof: Let cx < CQ be the /Vprojected inequality for HP(V) w.r.t. ay < a0, where V = V \ {h}. Observe that the support graph GC(V) contains an isolated node t, and thus its complement, the zero-graph GC{V) is connected. By L e m m a 4.12, V is 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 Corollary 4.18. The next theorem shows that Naddef and Rinaldi's node-cloning condition in Propo-sition 4.17 is also necessary. Theorem 4.19 (Necessary and Sufficient Condition for Node-Cloning) Let ay < a0 be any nontrivial facet-defining inequality for STSP(V). Let a*y* < a„ be an inequality for STSP(V 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 (uhu1) with u £ U and u' € U'. Proof: Let cx < Co and c*x* < CQ be the /i-projected inequalities of ay < a0 and a*y* < a|J, 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 (PC) 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)) = C Q . 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. Theorem 4.20 (Repeated Node-Cloning and Clique-Lifting) Let ay < a0 be any 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*), obtained by clique-lifting of ay < ao w.r.t. any node t E V 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 Theorem 4.19, there exists an a-tight cycle C on V containing subchain (uhu') with u G Q and u' € Q' (condition (PC)) . 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'u1) with u G U and u' G V. (Note that for Case (2), u = t.) Hence condition (PC) 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 < a0 for STSP(V) is node-clonable w.r.t. every node in U. Let a*y* < for STSP(V*) be obtained by repeated clique-lifting of ay < a0 w.r.t. every node v G V \ U, such that each such node v is replaced by a clique of size greater than two. By Theorem 4.16, a*y* < is facet-defining. Then Theorem 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 Conditions for Node-Cloning As condition (PC) 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 Gc is the complement of the support graph Gc associated 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} : cdv > 0} and U' = {v £ V \ {h,d} : cdv = 0}; B2 . if U ^ 0, then ce < u for all e £ E(d : U) and ce > u for all e £ E(U). Note that ay < a0 in /i-normal form ensures the existence of a partition {h, d, U, U'} satisfying ( B l ) and U' ^ 0, because ae = ce = 0 for some e £ E(V \ {h}). Let ay < ao be a star inequality [21], and let a'y < a'Q be its /i-normal form w r^.t. any node h. Then a'y < a'Q satisfies condition B(h, d; u>) for some properly chosen d. (The h-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. Theorem 4.21 (1-Node Zero-Lifting Theorem) Let ay < a0 be a nontrivial facet defining inequality for STSP(V) satisfying condition B(h,d;u). Then the inequality a*y* < ag for STSP(V U {s}), 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 (Bl ) , U' 0 {d} induces a connected subgraph of the zero-graph GC(V), 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 cud = 0 by ( B l ) and Hamiltonian path P' = (u...wt...vd) satisfies c(P') > Co) , and therefore by (B2), we have cut > 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 facet-defining 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 < a0 if u > 0 and there exists a proper partition {h, Q, Q'} of V such that = u for all v G Q and ahv = 0 for all v G Q'. Chapter 4. Hamiltonian Path and Symmetric Travelling Salesman Problem 92 Theorem 4.22 (cj-Regular Node-Cloning) Let ay < a0 define any nontrivial facet 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 adv> = 0 andadv < <*> for all v G Q'\{v'}. (ii) For all e G E(Q) ^ 0, ae > u; there exists a node d G Q such that adv < UJ for all v G V \{d}. (iii) There exists an edge e = (z, j) G E(Q) such that ae = 0 and ae < u for all eeE(Q)UE{Q :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'Q be the /i-normal form of ay < ao and cx < CQ be the /i-restriction of a'y ^ a'o- Note that a*y* < a^ is equivalent to the inequality obtained by node-cloning of a'y' < a'0 w.r.t. h. We thus need only prove that a'y' < a'0 is node-clonable w.r.t. h. Note also that V = Q U Q'. Case (i). Note first that clique weight £ = a\s = ahd + ahv< — a<ftv = Define U = {v G V \ {d} : cdv > 0} and U' = {v G V \ {d} : cdv = 0}. Then a'y' < a'0 satisfies condition B(h, d; u>). Case (ii). Note first that clique weight £ = a£ s = ahd + ahv — adv=u for any v E Q\ {d}. Observe that, in this case, a'y' < a'Q may be obtained by complementing set Q U {h}, cf. equation (4.6). Thus, ' ae -u, e G E(Q\J{h}); ae+u, e G E(Q'); (4.8) a e otherwise. Also observe that (ii) implies a<f„ = and thus edv = 0, for all v G Q \ {d}. Further by (ii), we have that cdv < w for all u G <5', and ce>u for all e G E(Q'). Hence, condition Chapter 4. Hamiltonian Path and Symmetric Travelling Salesman Problem 93 B(h,d;u) also holds w.r.t. a'y' < a'0 and a partition {h,d,U,U'}, where U C Q'. The proof for Cases (i) and (ii) is complete by Theorem 4.21. Case (iii). Note that clique weight £ = a£a = a^ ,- + a -^ — a,j = 2u>. Also observe that: (01) ce < u for all e G E(Q); and (02) u < ce < 2u for all e G E(Q : Q'), and ce>2u for all e G E(Q'). (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 ce. < 2u> (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 cwip + cqwii >2u> czip + cqz». 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 2« u for either u eQ or u eQ'. Thus, (Z"...UJU...U) is a c-tight path with v G Z' and 2;" 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 cpv > Cp2, implying that (w...pv...z) is a c-tight path on V. 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 Theorem 4.22(ii) (and also a special case of Theorem 4.24 below). Next, Theorem 4.22 (i) and (ii) generalize Theorem 4.12 (ii) in Grotschel and Padberg [27] (Using Z = {h}). Finally, observe that Theorem 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 Theorem 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 Theorem 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 few < 20 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. Proposition 4.23 (Zero-Lifting for 0-1-Inequalities in /i-normal form) Let ay < a0 define a nontrivial facet of STSP(V) in h-normal form. Assume that ae £ {0,1} for all e 6 E(V), where V = V \ {h}. 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 95 Proof: Let cx < CQ be its /i-restriction on HP(V). By Proposition 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 Cpq > 0 = c ^ i , (u...po...u') is another c-tight path, contradicting the supposition. Therefore, we must have ce = 1 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 a contradiction is immediate. So consider v £ U. Since < \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 CpV = 1 > cpq). This shows V is c-connected. • Recall (pp.282, [28]) that an STSP rank inequality is a valid STSP inequality ay < a0 with ae £ {0,1} for all e. Theorem 4.24 (Node-Cloning for Rank Inequalities) Let ay < a0 be a facet-defining 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 U {s}). Proof: Let V = V \ {h}, 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 Theorem 4.22 (by (iii) if ae = 0 for some e £ E(Q); and by (i) or (ii) otherwise). • With the above result and Theorem 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 Chapter 5. • the polyhedral study of other related problems, such as vehicle routing prob-lems [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 RA^V'^ (where ye = 1 if edge e is used in C and zero otherwise). This chapter 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 in-equalities, 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 E K i ^ . i e V , k j } < « o , (5-1) which we write in short a'y' < a'0, corresponds a unique directed version Y,{aayij V'i* ^ J"} < «o, (5.2) in short ay < ao, for the corresponding ATS polytope, where ao = a'0, and a,j = aj,- = a\j 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'Q. Conversely, any symmetric ATSP inequality ay < a0 yields an undirected version a'y' < a'Q for the corresponding STS polytope. It is easy to observe that an inequality a'y' < a'0 is an STSP valid inequality if and only if its directed version ay < a0 is an ATSP valid inequality. 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'0 is also ATSP 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 com-position 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) Hamil-tonian 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 = f0 whenever cx = CQ, for all x E V) must be equivalent to cx < CQ. This 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 < f0. 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 inter-change). 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 no-tably (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. Unfor-tunately, it is not easy to convert MATSP and GATSP facetial results into corresponding ATSP results. The Hamiltonian Path approach, introduced in Chapter 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 RA 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) onto subspace RA of RA'. This projection has two fundamental properties: AHP(V) has full dimension minus one (with a single implicit equation ]Ce x e = \V\ — 1); and the polyhedral structures of AHP(V) and ATSP(V) 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 AHP(V) trivially extend to ATSP(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) and its projection AHP(V), 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 Symmetric Dominance Lemma. In Section 5.5, we propose a Tree Composition of symmetric inequalities. This composition generates a large class of symmetric facet-defining 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 Notation 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 Hereafter, we assume n > 3. Digraph D(V) contains ra = |A| = n(n — 1) edges. For any two subsets Vi, V2 of V, define » A={(i,j)-.iev,jev\{i}}. (5.3) (V1:V2) = {(i1j)eA:ieV1J ev2}. (5.4) Chapter 5. Symmetric Inequalities for Asymmetric Travelling Salesman Polytopes 102 If Vi = V2, (Vi : Vi) is denoted by A(Vi). Thus, A = A(V). A singleton set {v} is 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 : V2) = {(i,j) G E(V) : i e V u j e V 2 } = E(V2 : Vx) and E{VX) = E(VX : Vi) are 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 RA such that ye = 1 if e G A and ye = 0 otherwise. For any vector x ^ i?"4 and A C A, let X(A) = E x . - (5-5) For simplicity, let X(S : T) = X((S : T)) and X(S) = X(A(S)), 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 yc of any Hamiltonian circuit C on V thus satisfies the following degree constraints: yc(6+{v)) = yc(6-(v)) = 1, for all v G V. Without risking confusion, a Hamiltonian circuit C with edge set A — ui)} U {(u,-, vi+1) : i = 1 , s - l } on node set S = {vx,us} C V may be represented by edge set A alone or, equivalently, by the circular permutation (ui...us) of the nodes in 5". Chapter 5. Symmetric Inequalities for Asymmetric Travelling Salesman Polytopes 103 A Hamiltonian path P on S = {t>i,v s} C V is a connected partial graph (S, A) such that for some distinct i,j G S1, (5, iu{j,j}) defines a Hamiltonian circuit on S. Note that 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...va). Note that if l^l = 1, the 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{yc G RA{S) : C is a Hamiltonian circuit on S}, AHP(S) = conv{xp G RA{S) : P is a Hamiltonian path on S}. Recall that STSP(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). Note that the number of variables defining polytope STSP(S) (resp., HP(S)) is half of the number of variables defining its asymmetric counterpart ATSP(S) (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° = a0 (resp., cxp = CQ). Chapter 5. Symmetric Inequalities for Asymmetric Travelling Salesman Polytopes 104 5.3 T h e A T S Polytope 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) and D(V) = (V, A'), where A' = A U {(v,h),(h,v) : v e V}. That is, D(V) is obtained from D(V) by eliminating node h G V and all incident edges. Let AT5 , 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 xp G RA is a projection of incidence vector yc G onto subspace RA of P A ' . It follows that polytope AHP(V) is a projection of ATSP(V). Moreover, there is a one-to-one correspondence between the vertices of ATSP(V) 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~e = 1 if e G (V : v); i.e., if u is the head of edge e; and zero otherwise. Similarly, let A+e = 1 if e G (v : V), i.e., if v is the tailoi edge e; and zero otherwise. Thus, A~ (resp., A+) is the tail (resp., head) node-edge incidence matrix of D(V). By definition, the incidence vector yc G RA> of any Hamiltonian circuit C on V and its projection xp G P A satisfy the following identity: (u,u)GA; 1 - E e ^ A ^ f , ( u , t ; ) € ( f c : n (5-7) Throughout the paper, we assume, unless otherwise noted, that •} x G P A is a projection of y G P"4'; and Chapter 5. Symmetric Inequalities for Asymmetric Travelling Salesman Polytopes 105 • V = (y*,--,Vem,yhv11---,yhvn,yv1H,---,yvjt)i, where m = n(n- 1), tx G A for all / = 1 , m , and v\ G V for all / = 1 , n . L e m m a 5.1 Let By = [y1, •••,?/'] &e <mj/ matrix such that all columns y3 are incidence vectors of Hamiltonian circuits on D(V). Let matrix Bx == [ x 1 , x l ] , where x3 is the projection of y3 onto RA, j = 1,...,/. Then, the number of affinely independent columns in By is equal to the number of affinely independent columns in Bx. Proof. From (5.7), it follows 1* rank > rank > rank Bx / 1 0 0* I \ ) I I t = rank 1 -A-1 -A+ 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. • Theorem 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 corre-sponding Hamiltonian paths. Let n > 5. First, observe that for any Hamiltonian path P on V, we have ^ e ^ A xP = n — 1. Therefore, 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^' = fe, - /.. 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. Corollary 5.3 The dimension of ATSP(V1) is dim(ATSP(V')) = 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 Theorem 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) and AHP(V), respectively, and satisfying: a0 = Co; ae = ce> 0, Ve G A; and ae = 0, 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 Theorem 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) iff its restriction cx < CQ defines a k-dimensional face of 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 < a0 for ATSP(V) is in canonical form with respect to a given node h G V (/i-canonical form, for short) if (Cl) avh = ahv = 0 for all v G V = V \ h; (C2) a > 0 and ae = 0 for some e G A = A(V); (C3) the coefficients ae are relatively prime integers. A H P Canonical Inequality Inequality cx < CQ for AHP(V) is a canonical inequality, or in canonical form, if the coefficients ce satisfy conditions (C2) and (C3) above. 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 ATSP(V) (resp., AHP(V)) if it is equivalent to ye > 0 (resp., xe > 0) for some e G A' (resp., e G A(V)). 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 < a0. Consequently, the "struc-tural" definitions of inequalities, such as Comb, Clique Tree, etc., ay < aQ for ATSP(V) directly apply to cx < Co for AHP(V \ h) as well. Next, it follows immediately from Theorem 5.4 that ay < a0 defines a facet of ATSP(V) iff cx < Co defines a facet of AHP(V \ 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 Symmetric 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 ab[b'3 = 2, ab{bi = 4 ' atj&£ = 4 ' a6j6j = °> e t C -and the right hand side a0 = 44 if node g is absent, a0 = 48 if present. ^12 m4 . f* l2 b3 v2 < 44 (48) • 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 facet-defining 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). Figure 5.1 presents an example. Given are proper subsets of V as follows: N nested circles, A\ D A2 D ... D AN; and an odd number s > 3 of disjoint spikes, B1, B2,B", where, for all i, B% consists 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 Aq and b\ Aq. Let M(v) denote the number of circles Aq containing node v. With each spike B% associate a spike weight JV,- such that JV,- > M(b)+l) - M(b)) for all 1 < j < ra, - 1 (cf. Fleischmann [21] for details). Then, a primitive Star Inequality ay < ao for ATSP(V) is defined by £y{Aq) + £/%(£«) < £\Aq\ + £iv ,(|P«| - 1 ) - v+JEL. (5.10) 9=1 «'=1 g=l «=1 Z Let a'y' < a'Q be the undirected version of inequality (5.10) for STSP(V). By adding to a'y' < a'0 proper multiples of the following valid equations (obtained from the degree constraints): 2y\S) + y'(6(S)) = 2\S\, for all S € {Au AN, B\ B°], we obtain £ y ' ( « K ) ) + £ NrfMl?)) > 2 £ Nq + (s + 1)N, (5.11) 9=1 »'=1 9=1 which is the Star Inequality for STSP(V) in Fleischmann's form [21]. When Ni = M(6}+1) — M(bj) for all i and j, inequality (5.10) represents a Regular 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*, B3 and the leftmost spike in the dash-box are 2, 4 and 2, respectively. 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) + yLNiz(Bi) < £\Aq\ + EAr,(|^'| - 1) - (5.12) 9=1 »'=1 g=l »"=1 Z Theorem 5.5 Primitive Path and Wheelbarrow Inequalities (resp., their restrictions) are facet-defining for ATSP(V) (resp., AHP(V)). The proof of Theorem 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 Cunning-ham, 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 its fo-canonical form. 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 h-canonical 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) for |V'| = 8,9. • 3 • 5 • • 2 2 c • A • 6 • < 9 (a) The Envelope Inequality 2 < 8 3 ^ g . \ ^ L J < 10 (b) /i-canonical form of (a) < 12 (13) (c) The Ladder Inequality (d) /i-canonical form of (c) Figure 5.2: Symmetric facets and their projections Theorem 5.6 The following statements are true: 1. The Envelope Inequality defines a facet of ATSP(V), where \V'\ = 7. 2. The Ladder Inequality defines a facet of ATSP{V'), where \V'\ > 8. A proof of Theorem 5.6 is contained in Section 5. We remark that the Enve-lope 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 ATSP facet-defining 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 \SQ = {b[} and S0 fl Si = {b2} for all i = p + 1 , k ; (iv) R = { r i , r p } C So and R fl Si = 0 for all i = 1 , k ; and (v) V'\u!u £• = {*}• Let T = { s i , s p } . bl fc3 s2 si " " M l bi W 6 f ^ r 2 <6(7) •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)<\S0\ + l(k+p-2). (5.13) 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. Theorem 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 Clique-Lifting 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 Chapter 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 Dominance Lemma) Let cx < CQ be a symmetric inequal-ity for AHP(V) whose undirected version dx' < d0 defines a facet of HP(V). If there ex-ists a symmetric facet-defining inequality f x < fo for AHP(V) which dominates cx < CQ, then cx < Co defines a facet of AHP(V). Proof. If fx < fo is symmetric, then it has an undirected version fx' < f'Q for HP(V). Observe that fx' < f'Q also dominates the HP facet-defining inequality dx' < dQ, and 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'e = ade + /3 for all e G E(V) and /Q = QTCQ + (n — l)/3. It follows that fe = ace + /? for all e G A(V). Thus, cx < CQ is equivalent to fx<fo, hence facet-defining. • 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 Theorem 5.4. 5.5 Composing Symmetric 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. ae > 0, Ve G A(V); 2. ae = 0, Ve G (h : S U Z) U (5 U Z : h) U (d : Z) U (Z : d); 3. if |5| > 3, then ae > nu, Ve G A(5 \ d); and 4. ad„ = avd = u>, Vv e S\ d. An inequality ay < a 0 for AT5'P(y) is said to be an ATSP Tree Inequality with 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 < a0 with respect to bud S is said to be a composable 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 auv = 0; and (54) there exists a Hamiltonian circuit d on V'\d, called aU-circuit, such that a(Cd) = a0. 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). Proposition 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 com-posable 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 = r2, the S-circuits are (b\b\b\b\vs2r2dh) and (b\b\b\b\vs2r\dh), respectively. The W-circuit is Cd = (b\b\rxs2r2b\b\h). Let a V < a£ (resp., a2y2 < al) be an ATSP Tree Inequality for ATSP(V[) (resp., ATSP(V2')) with respect to bud Si (resp., bud S2). Assume that V{ fl V2' = {di,/*i} = {d2, ^2}, d = di = d2 and h = h\ = ft2, where d\ G S\ and d2 G 5*2 are tips. Assume also w.l.o.g. that u = UJI = u2 (by scaling). Define V = V{ U V2\ S = Si U S2 and construct inequality ay < yo for ATSP(V) by the following Tree Composition: ' a'e, eG A{y!\hi), i = 1,2; w, eeA(S)\{A(S1)UA(S2)}; (5.14) 0, otherwise; and ao = aj + OQ. This composition is illustrated in Figure 5.4. After composition, two buds containing their corresponding tips di and d2 are combined into a single bud S in Fig. 5.4(3), and di and d2 (resp., nodes 1^ and h2), are merged into a single tip d (resp., node h). aP=< Chapter 5. Symmetric Inequalities for Asymmetric Travelling Salesman Polytopes 118 (1) Wheelbarrow Inequality (2) Chain Inequality < 15 = 9 + 6 (3) An ATSP Tree Inequality Figure 5.4: A Tree Composition Theorem 5.11 (Tree Composition Theorem) Let a1]/1 < aj anda2y2 < a2, be ATSP Tree Inequalities for ATSP(y() and ATSP(V^') w.r.t. buds Si and S2, respectively, and let ay < ao be obtained by the Tree Composition (5.14)- Then (i) ay < a0 is a valid inequality for ATSP(V), where V = V( U V{. (ii) if, furthermore, the composing inequalities are composable ATSP Tree Inequalities w.r.t. buds Si and S2, then the following statements hold: (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 S2. (C) If a^y1 < UQ is a composable Tree for ATSP(Vi) with respect to another bud S' with tip d', satisfying S'DSi = 0, then, the composed inequality ay < a0 is a composable ATSP Chapter 5. Symmetric Inequalities for Asymmetric Travelling Salesman Polytopes 119 Tree Inequality for ATSP(V) with respect to bud S'. The proof is given in Section 6. Statements (B) and (C) ensure that the Tree Composition procedure can be repeat-edly applied so as to construct a large class of tree-like facet-defining inequahties for ATSP polytopes. For instance, Theorem 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 cor-responding 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) + £ JWir ' ) < £ | A , | + J2Ni(\Bi\ - I) - \ E(fc, +1), (5.15) 9=1 t=l 9=1 i=l 1 9=1 where kq denotes the number of spikes intersected by circle q. By (Si') and (S2'), a 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 0 be such 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 aV ^ ao 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 Inequal-ity 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 in 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 < f0 are facet-defining inequalities that dominate cx < CQ. By Propo-sition 5.8 and the Symmetric Dominance Lemma, it suffices to show that their dominating facet-defining inequalities fx < f0 are symmetric. 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 < f0 for AffP(V), define the f-length of P by f(P) = f(vl...vl) = i£fViVi+1, l < l < n . (5.16) i=i 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 Proof of Theorem 5.5: Define Define also P/ = (b[...bni) for all / = 1 , s . b{ 6j_ bl, b> P(a) 0 6fc P(d) fti ' T 1 1 61. P(b) fl1 6* I I I P(e) 61. 6i P(c) 5 6fc L 1 9 -P(f) 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 = fxP ~ fxP = fb*b{ ~ fb{b[i yields = *c7. Replacing i, j, k in P(a) by k, i,j, we obtain as above that /t< bk = *c7. 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 (6t ,^ + 1 ) are /-symmetric for all 1 < t < rij — 1 and 1 < j < s, and /(P,) = / (P , ) for all 1 < / < s. (iii) Let 7 = fbj = /6j , due to (ii). From path P(e), we construct: p = (..<...6^i...6;^nj...6i), and from path P(c): P' = (&{...^...6^...616i...6g. 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' = (0i...6J l^...fe* f c...6j6i...^^....Df+ 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, b3^) is also /-symmetric for 1 < / < rij — 2. 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 (Vt, 6/+1) is /-symmetric for all 1 < t < I < 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+1) (cf. page 110 for the definition of M(*)), define c-tight paths: for t > 2, P(t, 1 + 1) = P(f); otherwise t = 1, we have P(*,Z + 1) = (6i...6^n....6f+1fei...6',....5...6^...6j). Observe that P(2,Z + 1) contains exactly one edge (6j, 6f+1) not shown to be / -symmetric, therefore comparing P(t, Z+l) with P (t, l+l) yields (6j, &/+1) as /-symmetric. For all b\ and bj+1 such that Af(oJ) > M(6f+ 1), exchange i and j, and then repeat (v). If node g exists, define c-tight paths P&) = (fe^..6;r..^...&Jfei...^^....6|+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 < f0 is a symmetric inequality. The proof Proof of Theorem 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 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 Ef = A(V). Envelope: Let a = f12, 0 = / 3 4 , *P = f*3, 7 = /24, 7" = f*2, Z = /se and T = / 6 5 . (i) Let C 1 = (124356) and C 2 = (214356). C 1 \ (1,2), C 1 \ (3,5) =^ > / 1 2 = /ss; C 2 \ (2,1), C 2 \ (3,5) = » / 2 1 = / 3 5 . Hence, / 2 1 = / 1 2 = a and let = {(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 cxc = CQ + 1. (For e = (3,5), let e' = (1,2) and C = C 1 above; for e = (1,4), let e' = (2,1) and C = C2 above; for e = (1,6), let e' = (2,1) and (216534).) Thus, comparing C \ e and C \ e', and then is complete. • implies V G Ef. For any subset E' C A(V), define the following operation 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, fe = a for all e E Ef. (ii) (4356 21), (12 4356) => / 6 2 = / 2 4 = 7-(2156 43), (156243) => / 6 4 = 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) "7 4- 27 - a + *J = 7 + 2*7 - a + /3; and (561243),(342165) £ + 7 + 7 = 7 + 7" + It follows that £ = £ . By symmetry, /? = /3 . Hence, 7 = 7^" and {(3,4), (5,6), (4,6), (2,4), (2,6)} 0Ey. (iii) For edges (1,3),(1,5),(2,3),(2,5),(3,6),(4,5), construct, respectively, the correspond-ing desired c-tight paths (213465), (215643), (123465), (125643), (124365), (345621). • Ladder: Let a = / 4 7 and Ef = 0. (i) Let C 1 = (7216534) and C 2 = (7432156). C 1 \ (7,2), C 1 \ (4,7) =>• / 7 2 = / 4 7 = a; it follows / 7 2 = fa = a by exchanging nodes 3,4 with 5,6. C 2 \ (7,4), C 2 \ (6,7) / 7 4 = / 6 7 . Hence, / 7 4 = / 4 7 = / 6 7 = f76 = 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 cx c = CQ + 1 (either C 1 or C 2 above). 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, fe — a for all e G Ef. (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 cor-responding 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 Ex by {(7,2), (1, <?)} U ({</}, {3,4,5,6}); • 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),(72143565), (7215643#),(7216534#),(5 643217)." 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 = (rq...st) on RUT such that c(P) = 2p - 1 (cf. Fig. 5.7(1)). Let (6^...6X) and (6f ...6*fc) denote two fixed subchains (rq...st) and (st...rq), respectively. Let n,- = 2 for all i. Thus, following (i), (ii), (iii) and (v) in the proof of Theorem 5.5, where n,- = 2 for all i, and the subchains P k and Pk are replaced by (rq • • • st) and (st • • • rq), respectively, we show that all edges in A\A(RUT) are /-symmetric. Construct the four c-tight paths on V, see Figure 5.7. P ( l ) 9 1 P(3) st St Tt 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 g 5 , ) . Thus, comparing P(l) with P', and P(l) with P', respectively, yields fSqrq = fTqaq. For any 1 < q < t < p, we obtain from path P(2) a c-tight path P" = P(2) U {(rt, V2), (st, rt)} \ {(sq, rt), ( r«, st)}. Chapter 5. Symmetric Inequalities for Asymmetric Travelling Salesman Polytopes 129 As above, comparing P(2) with P", and P (2) with P", respectively, yields fa r t = fr,aq-Finally, observe that all edges in paths P(3) and P(4) have been shown to be / -symmetric except edges {rq,rt) and (sq,st). Thus, comparing P(3) with P (3), and P(4) with P (4), respectively, implies that edges (rq, rt) and (sq, st) are /-symmetric. It follows 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 auv = 0 by (S2'). By (SI'), construct an a-tight circuit C containing (u, v). Thus, C contains a subchain (uv...qd). First, observe that aqd — u; otherwise replacing 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 adp = 0, then construct the desired S-circuit by moving h in C to the position between d and p; else, adp = u>, and moving d in C to the position immediately before h yields the desired «S"-circuit, since Cqd + a-dp = 2u < apq (due to (S2')) and ay < a0 is valid for ATSP(V). 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 ce > 2u for all e G 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 apd = a,dq = 0 for case (i); apq > 2u = apd + a.dq for case (ii). Therefore, Cd is the desired W-circuit. • To prove the Tree Composition Theorem, we need the following four auxiliary results. Let ay < a0 be a composable ATSP Tree Inequality with respect to a bud S for ATSP(V) and let {h, S, Z} be the corresponding partition. Define V = V \ h. Then, the restriction cx < CQ of ay < a0 w.r.t. h is called a composable Tree Component for AHP{V). Define the following special paths w.r.t. cx < CQ and tip d: Z-path: A c-tight path (t...vd...s) w.r.t. v 6 Z such that ce = 0, VeG ({t,v} : {d,s}). <S-path: A c-tight path (z...uv...qd) w.r.t. v E S \ d such that czv = cuv = 0 and ce>u 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 ce > 0, say e = (v,s), w.l.o.g., then a Hamiltonian path P = (t...vs...d) yields cxp > Co, a contradiction. (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 czv = 0 follows since (u...zv...qd) is also a c-tight path. The last condition follows by contradiction: if for some e in subchain (v...qd), ce < UJ, replacing 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 Lemma) 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,-...ut) be a Hamiltonian path on Ui, i = 1,2,3. Define Ep = {P, P, : i = 1,2,3}, E0 = l j ( { " ^ } = «,-}). If ce = 0 for all e € Eo and YA=I c(Pi) = co> then (i) f(P) = fCPi) for i = 1,2,3; and (ii) fe is a constant for all e G EQ. Proof, (i) From Pi, P2, P 3 , we obtain two Hamiltonian circuits on V: C = (u1...v1U2...v2u3...v3), C = {ui...viv2...u2u3...v3), (5.18) Chapter 5. Symmetric Inequalities for Asymmetric Travelling Salesman Polytopes 132 such that c(C) = c(C) = CQ. Comparing c-tight paths C \ (v3, ui) and C \ (t>i, u2) yields /«stn = f v 1 U 2 ; comparing C \ (u3, «i) with C \ {vx, v2) yields fviV2 = / v 3 " l = fv\U2- (5.19) Further, comparing P = (U3...V3U1...V1U2...V2) and P' = (U3...V3U1...V1V2...U2) yields 0 = f(P) - f(P') = fVlU2 + f(P2) - fVlV2 - / ( P 2) = /(P 2) - / ( P 2). Similarly, we show that P\ and P 3 are /-symmetric. Hence, (i) holds. (ii) Observe that for any eo G Eo, there exists a Hamiltonian circuit C C EP U EQ 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 \ (vx, U2), C \ (i>2, u3) and C \ (u3, «i) yields / " i « 2 = / " 2 U 3 = / f 3 « i = f ( C ) / o -Similarly, using C , we obtain fu2Vl = fu3V2 = fli\V3 = /( C ) /o-Further, by (i) and f(C \ (v\,u2)) = f(C \ (u2,i^)), we have «'=1 i=l Hence, all edges e 0 G Eo are /-symmetric. Since all elements in Eo U _EP are shown to be /-symmetric, repeating (5.19) for all permutations of indices of ux, u 2 , u 3 and exchanging the roles of the u and u nodes imply 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) defined in (5.14) is valid for ATSP(V). Proof. It suffices to show that its undirected version a'y < ao is valid for STSP(V). Let S[ = Si\ di and S'2 = S2\ d2. An edge e is called an w-edge if e 6 E(d : 5 J U ^ ) U E(S[ :S'2). Let C* be any solution to m&x{a'yc : C is a Hamiltonian cycle} = a^. Let C = C*. (i) [u>-Edge Reduction] Let E(V{ : V2 \ d2) be the set of all crossing edges, and let E(Si : S'2) be the set of all UJ-crossing edges. For any Hamiltonian cycle Co on V, let Nu(Co) = \Cof\E(Si : S'2) \ denote the number 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). (5.20) Since a'us + a'vt > 2u, we have a* = a'(C) < a'(C') = a*, and NW{C) = NW{C) - 2. Let C = C Observe that such a reduction is always possible whenever liV^C)! > 2. Hence, we repeat (i) until NW(C) < 2. (ii) Exchange sets S[ and S'2 in (i) and then apply (i). (iii) First, observe that C contains at most one edge in Ew — E(S[ : S'2). Otherwise, C contains exactly two edges (u,v), (t,s) £ Ew. Further, by (i) and (ii), C contains the subchain (pdq) with a'pd = a'dq = 0, where d is the common tip. Replacing subchains (uv) 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 P2 = C D E(Vj). Note that Px and P2 are subsets of some Hamiltonian cycles C\ on V{ and C 2 on V2, respectively. If C contains no edges in Ew, then a'(C*) = a'(C) = a'(Pi) 4- a'(P2) < a'(Ci) + a'(C2) < aj + a 2 = a0. Otherwise, C contains exactly one edge (u, v) £ Ew with u £ S[ and v £ 5j> and a subchain (pdq). Let Px' = Pi U (u,d) and P2' = P2 U (d,u). If p,q £ V/ (resp., p,g £ Vj), then, P2 (resp., P[) is a subset of some Hamiltonian cycle on V2 (resp., V{). Else, 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 P2 is on V2, since otherwise both P[ and P2 contain some sub-cycles covering d, and so does Pi U P2 U (u, u) C C, which contradicts that C is a Hamiltonian cycle on V. If P/ is contained in some Hamiltonian cycle C[ on V{, then a'(C*) = a'{C) = a'(Pi) + a'(P2) < a'(C[) + a'(C2) < a 0 4- a2 = a0; else the above holds by exchanging indices 1 and 2. • Let inequality ay < a0 for ATSP(V) be obtained by the Tree Composition (5.14) of two ATSP Tree Inequalities a1y1 < aj and a2y2 < OQ, relative to buds S\ and S2, respectively, and let {hi, Si, Z{\ and {h2, S2, Z2} be the corresponding partitions. Define Vi = V! \ hi, i = 1,2, and V = V'\h. Recall that Vi n V2 = {d} = {dx} = {d2}, where d is the common tip. The restrictions cx < CQ, C X X x < cj and c2x2 < c\ of ay < ao, a1y1 < aj and a2y2 < al, w.r.t. h, hi and h2, are called Tree Components, for AHP(V), AHP(Vi) and AHP(V2), respectively. Then, we say that cx < CQ is obtained by AHP Tree Composition of two Tree Components cxxx < c\ and c2x2 < 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, h2, h. Chapter 5. Symmetric Inequahties for Asymmetric Travelling Salesman Polytopes 135 Theorem 5.15 Inequality cx < CQ obtained by AHP Tree Composition of two composable Tree Components c1x1 < cj and c2x2 < CQ defines a facet of 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, V2 \ d2} be the partition of V, and by L e m m a 5.12(3), let P 2 = (u2...v2) be a W-path on V2 \ d2 with c(P2) = c\ and u 2 , v2 G Z2. (i) For every v\ G Zi , 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 3 = (d...si); for every vi G 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 2 and P 3 satisfying the conditions in L e m m a 5.13, and therefore we have fe = fU2d for all e 6 ({"2, v2} : Vi) U (Vi : {u2, v2}) and f(P2) = f(P 2). This further implies that for any c1-tight path P' on Vi, there exists a c-tight path P on V containing P' and P 2 such that fo = fxP = f(P') + f(P2) + fU2d. Since c1x1 < c\ is facet-defining for AHP(Vi) and the above equality holds for all c1-tight paths P', there exist real numbers ai > 0 and fi\ such that fe = a\ce + fa for all e G A(Vi). By partitioning V into {V2, Vi \ di}, we show by symmetry that for some real numbers a2 > 0 and /?2, / e = <*2Ce + /52 holds for all e G A(V2). (ii) For any v2 G Z 2 , construct a Z path (<2-"t>2d....s2) on V2. As in (i), for every v\ G Zi , 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 = (t2...v2), P 3 = (gi...d...s2), Chapter 5. Symmetric Inequalities for Asymmetric Travelling Salesman Polytopes 136 and for the latter case, Px = ( * i . . . u i ) , P2 = (t2...v2), P3 = ( u i . . . O i d . . . s 2 ) . Further, since cZlVl = cV2S2 = 0, by (i) and L e m m a 5.13, we have By symmetry, it follows fe = fl for all e € A(V) \ {A(Vi) U A(V2) U A(S)}. (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 ce > u> and cgij = u by definition. Possibly o,- = u,.) Comparing the following two c-tight paths: P' = (zx...uxz2...u2v2...q2dqi...v1), P" = (z1...u1z2...u2dq2...v2v1...qx) yields 0 = f(P') - f(P") = (3 + fdqi-/3- / ^ V l = aiuj + 0 - fV2Vl. Further, comparing P' and P" yields fVlV2 = a\to + fl, due to (i) and (ii). By exchanging V\ and V2, we show also / „ l V 2 = = cc2u> + fl. It follows that a = a i = a 2 , (i), (ii) and (iii) imply that fe = ace + fl for all e e A(V). • Now, we are in a position to prove the Tree Composition Theorem. Proof of the Tree Composition Theorem: Part (i) of the theorem is proved in L e m m a 5.14. For part (ii), Statement (A) follows from Theorem 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 (u2...v2z\...u\vx...q\dh) on V, where (u2...v2) is aZY-path on V2\d and (zi...UiVi...q1d) is an <S-path on V\. Similarly, we obtain a requisite «S-circuit for every v2 £ S2\ d. (S4) holds by exhibiting W-circuit (ux...v\U2...v2h) on V ' \ d , where (u,-...ut) is aW-path on Vi \ di, i = 1,2. For (C), Condition (S3) follows by constructing, for every »i 6 5' \ d', S-circuit {u2...v2z\...u\V\...q\d!h) on V, where (u2...v2) is a W-path on V2 \ d and (zi...uii>i...fl1d/) is an «S-path on Vi. (S4) holds by exhibiting ^ /-circuit (ui...viu2...v2h) on V \ d', where (ui...vi) (resp., (•U2...V2)) 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 Schedul-ing 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 Op-timization 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, Springer-Verlag 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: For-mulations, 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 Rout-ing Problem. MSRR No. 553, GSIA, Carnegie Mellon University, Pittsburgh, PA. [15] T. Christof, M. Junger and G. Reinelt (1990). A Complete Description of the Trav-elling 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 Trav-elling 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 Prob-lem. 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. Mathemat-ical 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 Sym-metric Travelling Salesman Problem. Math, of Operations Research 11, pp. 537-569. [30] A. Kearny (1980). Improving Productivity in Physical Distribution. Report Under-taken 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 Prob-lem. 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). Se-quencing 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 Travel-ling 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 Trav-elling 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 Resolu-tion 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 Com-pletion 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 Prob-lems. Integer Programming and Combinatorial Optimization, proceedings of a con-ference held at the University of Waterloo, May 1990, by the Mathematical Pro-gramming Society, edited by Raviv Kanan and W.R. Pulleyblank. [57] L.A. Wolsey (1989). Formulating Single Machine Scheduling Problems with Prece-dence Constraints. CORE Discussion Paper No. 8924. Center for Operations Re-search and Economics, Universite Catholique de Louvain, Belgium. Appendix A Generating the Sample of 280 scheduling problems This appendix contains all relevant information to generate the 280 scheduling problems used in the computational experiments in Chapter 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 = 100 in this study), the maximum job weight (IWMAX = 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 each ra, 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. Generating the Sample of 280 scheduling problems C PROGRAM FOR GENERATING THE SINGLE-MACHINE PRECEDENCE CONSTRAINED C JOB SEQUENCING PROBLEMS. (USING MICROSOFT FORTRAN 5.0) C PRECEDENCE MATRIX, PROCESSING TIMES AND JOB WEIGHTS. COMMON NP(200,200),P(200),W(200) INTEGER FR0M(3000),T0(3000) C INPUT C VARIABLE FORMAT DEFINITION K* C N 15 NO. OF JOBS C IPMAX 15 MAXIMUM PROCESSING TIME c IWMAX 15 MAXIMUM JOB WEIGHT c PROB F5.3 P VALUE FOR THE PRECEDENCE GRAPH c NSEED 110 SEED FOR THE RANDOM NUMBER GENERATOR C THE FOLLOWING 5 STATEMENTS MAY BE CHANGED IF C 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 FIND THE TRANSITIVE CLOSURE AHD REDUCTION OF THE PRECEDENCE DIGRAPH. CALL TRANSCR(N,NPOSA) C C 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 SUBROUTIHE TRANSCR(HOP.HPOSA) CONNOI NP(200,200),P(200),tf(200) C C FIID THE TRANSITIVE CLOSURE AND REDUCTION C OF THE GIVEH DIGRAPH REPRESENTED BY NP(I,J). C C INPUT C C THE PRECEDENCE GRAPH NP C C OUTPUT C C THE UPPER TRIANGULAR OF NP: THE TRANSITIVE CLOSURE C THE LOWER TRIAGULAR OF NP: THE TRANSITIVE REDUCTION C NPOSA: NO. OF ADDITIONAL ARCS USED IN CONSTRUCTING THE C TRANSITIVE CLOSURE C NPOSA=0 C 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 PORTABLE RANDOM NUMBER GENERATOR IMPLEMENTING THE RECURSION: C IX = 16807 * IX MOD (2**(31) - 1) C USING ONLY 32 BITS, INCLUDING SIGN. C CC REFERENCE: "A GUIDE TO SIMULATION", P. BRATLEY, C B.L. FOX AND L.E. SCHRAGE, 1983, C Springer-Verlag New York Inc. C C SOME COMPILERS REQUIRE THE DECLARATION: C INTEGERS IX, Kl C C INPUT: C IX = INTEGER GREATER THAN 0 AND LESS THAN 2147483647 C C OUTPUTS: C IX = NEW PSEUDORANDOM VALUE, C UNIF = A UNIFORM FRACTION BETWEEN 0 AND 1 C Kl = IX/127773 IX = 16807*(IX - Kl+127773) - Kl * 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 PORTABLE CODE TO GENERATE AH INTEGER UNIFORM OVER C THE INTERVAL 1,H USING INVERSION C CC REFERENCE: "A GUIDE TO SIMULATION", P. BRATLEY, C B.L. FOX AND L.E. SCHRAGE, 1983, C Springer-Verlag New York Inc. C C INPUTS: C IX = RANDOM NUMBER SEED C N = THE UPPER BOUND OF THE UNIFORM INTEGER C M = LARGEST VALUE FOR IX + 1 C C AUXILIARY ROUTINE: C UNIF C C OUTPUTS: C IX = NEW PSEUDORANDOM VALUE, C IVUNIF = A UNIFORM INTEGER BETWEEN 1 AND N C C THE RANDOM NUMBER GENERATOR IS ASSUMED TO USE THIS MODULUS DATA M/2147483647/ C JUNK = UNIF(IX) C C WE WANT INTEGER PART OF IX/(M/N) USING INFINITE PRECISION. C FORTRAN TRUNCATION UNDERSTATES M/N, THUS, FORTRAN MAY C OVERSTATES WHEN IT COMPUTES IX/(M/N). SO DECREASE JTRY C UNTIL JTRY <= IX/(M/N), I.E. M/IX <= N/JTRY. C 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 152 n=30 n=40 n=50 n=60 1 .001 8913445 47920113 19026 85617 2 .001 755493537 1617675166 1715650722 1664517790 3 .020 1809917341 1175781217 106619163 299964548 4 .020 1725092278 1058321011 946083291 1527627754 5 .040 1822638204 1046809820 1851494651 589620248 6 .040 1180075628 1112508140 35270033 305479182 7 .060 150617066 1562075571 890663124 13878902 8 .060 1548235839 678966767 2111398339 359148491 9 .080 373360250 1078420215 1642491473 554424631 10 .080 1157536406 234794403 1253273425 73982478 11 .100 94545423 1482029273 114463185 313191047 12 .100 1103566408 1539623401 1192173437 829336955 13 .150 206050178 2111547401 1080955147 1401168127 14 .150 1524763277 525300461 411821081 1088629889 15 .200 581095035 455447345 289919440 685524764 16 .200 1260330676 1553388927 1817182748 1898463718 17 .300 2069131884 2064816761 1622539993 2139336862 18 .300 930436326 849467010 228036027 49606783 19 .500 575844519 1762170024 765120123 1988304799 20 .500 1424549194 1310705738 1588399166 646765699 n=70 n=80 n=90 n=100 1 .001 76815623 4375178 350983217 2593 2 .001 1201897528 1611982795 1728743609 1468695453 3 .020 1630262163 697923001 236415471 1096690315 4 .020 1221144650 247554449 2056300857 1630069622 5 .040 18421799 439147435 668603022 1583467229 6 .040 417497068 234303362 873157283 782036086 7 .060 758772556 1679599250 1467748577 1798123704 8 .060 107891396 1669397446 1764811933 2043023199 9 .080 829805974 1558045213 387567746 486855177 10 .080 1807075147 1150686510 95713841 1991158124 11 .100 345975380 985796663 428865251 1426983424 12 .100 999548725 1837490202 427903940 71993197 13 .150 698081069 1344833772 349430181 133879335 14 .150 599774400 2128144389 1808998354 1365624620 15 .200 776266564 967140344 964298149 217047395 16 .200 2084721901 514443436 2089434947 1362135656 17 .300 984818336 2013815749 383679383 544616922 18 .300 1482079848 1460738242 757904826 2019009597 19 .500 1692157679 1748668138 728441454 513041050 20 .500 338192698 1739693055 1709478887 387185455 Table A . l : Seeds for the instances with n = 30,40,50,60,70,80, 90,100 Appendix A. Generating the Sample of 280 scheduling problems 153 n=110 n=120 n=130 1 .001 578 327819 7456673 2 .001 872858166 1896871566 2090383671 3 .020 1966911261 1879863869 613433542 4 .020 2035263084 1751592867 2002449486 5 .040 1077304999 927231622 1046463762 6 .040 1367175068 1907798662 818258585 7 .060 1810714895 1892363717 1970034241 8 .060 1350354151 1351713937 1274437629 9 .080 1145775358 1788610971 1473953588 10 .080 415529128 795452143 62622184 11 .100 1992218419 1633349205 2013606980 12 .100 120830678 1207063493 731735072 13 .150 115769795 302181295 1371935740 14 .150 392329467 278166407 830555894 15 .200 278009491 1189966678 646486032 16 .200 517310160 350462138 814653809 17 .300 1625666109 66273535 1787943512 18 .300 1168319371 710696277 162859647 19 .500 1497262303 1172431752 2131368145 20 .500 81858226 134821562 1849154095 n=140 n=150 n=160 1 .001 87485 1782437 7142 2 .001 347175951 153399920 661277793 3 .020 2040294373 1372129829 2105052591 4 .020 1031163234 451762956 1604032548 5 .040 1248974721 1730677699 1335044189 6 .040 1161785585 922885587 259379126 7 .060 147857977 1942371325 1562102629 8 .060 559322792 615429360 1301809084 9 .080 1142323614 2101567237 1795967001 10 .080 1994794676 1030042377 1083362231 11 .100 236427843 397005716 500851712 12 .100 309642129 2127352365 809794613 13 .150 628556917 185713150 1888704444 14 .150 67336514 499856450 623919773 15 .200 1546694624 747760362 266082890 16 .200 1908158645 1210383192 2086462989 17 .300 34474010 96454607 284799641 18 .300 601131006 799671032 1756198218 19 .500 405094013 2130125375 1023000068 20 .500 1210698212 1194121298 597523231 Table A.2: Seeds for the instances with n = 110,120,130,140,150,160
- 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 |
AggregatedSourceRepository | 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:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0101095/manifest