Lecture Notes in Computer Science 3064 CommencedPublicationin1973 FoundingandFormerSeriesEditors: GerhardGoos,JurisHartmanis,andJanvanLeeuwen EditorialBoard TakeoKanade CarnegieMellonUniversity,Pittsburgh,PA,USA JosefKittler UniversityofSurrey,Guildford,UK JonM.Kleinberg CornellUniversity,Ithaca,NY,USA FriedemannMattern ETHZurich,Switzerland JohnC.Mitchell StanfordUniversity,CA,USA OscarNierstrasz UniversityofBern,Switzerland C.PanduRangan IndianInstituteofTechnology,Madras,India BernhardSteffen UniversityofDortmund,Germany MadhuSudan MassachusettsInstituteofTechnology,MA,USA DemetriTerzopoulos NewYorkUniversity,NY,USA DougTygar UniversityofCalifornia,Berkeley,CA,USA MosheY.Vardi RiceUniversity,Houston,TX,USA GerhardWeikum Max-PlanckInstituteofComputerScience,Saarbruecken,Germany Daniel Bienstock George Nemhauser (Eds.) Integer Programming and Combinatorial Optimization 10th International IPCO Conference NewYork, NY, USA, June 7-11, 2004 Proceedings 1 3 VolumeEditors DanielBienstock ColumbiaUniversity,DepartmentofIEOR 500West120thStreet,NewYork,NY10027,USA E-mail:[email protected] GeorgeNemhauser SchoolofIndustrialandSystemsEngineering,GeorgiaInstituteofTechnology Atlanta,GA30332,USA E-mail:[email protected] LibraryofCongressControlNumber:2004106214 CRSubjectClassification(1998):G.1.6,G.2.1,F.2.2,I.3.5 ISSN0302-9743 ISBN3-540-22113-1Springer-VerlagBerlinHeidelbergNewYork Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,re-useofillustrations,recitation,broadcasting, reproductiononmicrofilmsorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9,1965, initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer-Verlag.Violationsare liabletoprosecutionundertheGermanCopyrightLaw. Springer-VerlagisapartofSpringerScience+BusinessMedia springeronline.com ©Springer-VerlagBerlinHeidelberg2004 PrintedinGermany Typesetting:Camera-readybyauthor,dataconversionbyBollerMediendesign Printedonacid-freepaper SPIN:11008705 06/3142 543210 Preface ThisvolumecontainsthepapersacceptedforpublicationatIPCOX,the Tenth InternationalConferenceonIntegerProgrammingandCombinatorialOptimiza- tion,heldinNewYorkCity,NewYork,USA,June7–11,2004.The IPCOseries ofconferencespresentsrecentresultsintheory,computationandapplicationsof integer programming and combinatorialoptimization. TheseconferencesaresponsoredbytheMathematicalProgrammingSociety, andareheldinthoseyearsinwhichnoInternationalSymposiumonMathemati- calProgrammingtakesplace.IPCOVIIIwasheldinUtrecht(TheNetherlands) and IPCO IX was held in Cambridge (USA). A total of 109 abstracts, mostly of very high quality, were submitted. The ProgramCommittee accepted32,inorderto meetthe goalofhavingthreedays of talks with no parallel sessions. Thus, many excellent abstracts could not be accepted. Thepapersinthisvolumehavenotbeenrefereed.Itisexpectedthatrevised versionsof the accepted papers will be submitted to standardscientific journals for publication. The Program Committee thanks all authors of submitted manuscripts for their support of IPCO. March 2004 George Nemhauser Daniel Bienstock Organization IPCO X was hosted by the Computational Optimization Research Center (CORC), Columbia University. Program Committee Egon Balas Daniel Bienstock Robert E. Bixby William Cook Gerard Cornu´ejols William Cunningham Bert Gerards Ravi Kannan George Nemhauser, Chair William Pulleyblank Laurence A. Wolsey Organizing Committee Daniel Bienstock, Chair Garud Iyengar Jay Sethuraman Cliff Stein Sponsoring Institutions Bob and Betty Bixby IBM ILOG The Fu Foundation School of Engineering and Applied Science, Columbia Uni- versity Mathematical Programming Society Table of Contents Session 1 Robust Branch-and-Cut-and-Pricefor the Capacitated Vehicle Routing Problem ......................................................... 1 R. Fukasawa, J. Lysgaard, M. Poggi de Arag˜ao, M. Reis, E. Uchoa, R.F. Werneck Metric Inequalities and the Network Loading Problem ................. 16 P. Avella, S. Mattia, A. Sassano Valid Inequalities Based on Simple Mixed-Integer Sets ................. 33 S. Dash, O. Gu¨nlu¨k Session 2 The Price of Anarchy when Costs Are Non-separable and Asymmetric ... 46 G. Perakis Computational Complexity, Fairness, and the Price of Anarchy of the Maximum Latency Problem ........................................ 59 J.R. Correa, A.S. Schulz, N.E. Stier Moses Polynomial Time Algorithm for Determining Optimal Strategies in Cyclic Games..................................................... 74 D. Lozovanu Session 3 A Robust Optimization Approach to Supply Chain Management........ 86 D. Bertsimas, A. Thiele Hedging Uncertainty: Approximation Algorithms for Stochastic Optimization Problems ............................................ 101 R. Ravi, A. Sinha Scheduling an Industrial Production Facility.......................... 116 E. Asgeirsson, J. Berry, C.A. Phillips, D.J. Phillips, C. Stein, J. Wein Session 4 Three Min-Max Theorems Concerning Cyclic Orders of Strong Digraphs . 132 S. Bessy, S. Thomass´e X Table of Contents A TDI Description of Restricted 2-Matching Polytopes ................ 139 G. Pap Enumerating Minimal Dicuts and Strongly Connected Subgraphs and Related Geometric Problems ....................................... 152 E. Boros, K. Elbassioni, V. Gurvich, L. Khachiyan Session 5 Semi-continuous Cuts for Mixed-Integer Programming................. 163 I.R. de Farias Jr. Combinatorial Benders’ Cuts ....................................... 178 G. Codato, M. Fischetti A Faster Exact Separation Algorithm for Blossom Inequalities .......... 196 A.N. Letchford, G. Reinelt, D.O. Theis Session 6 LP-based Approximation Algorithms for Capacitated Facility Location .. 206 R. Levi, D.B. Shmoys, C. Swamy A Multi-exchange Local Search Algorithm for the Capacitated Facility Location Problem................................................. 219 J. Zhang, B. Chen, Y. Ye Separable Concave Optimization Approximately Equals Piecewise Linear Optimization............................................... 234 T.L. Magnanti, D. Stratila Session 7 Three Kinds of Integer Programming Algorithms Based on Barvinok’s Rational Functions................................................ 244 J.A. De Loera, D. Haws, R. Hemmecke, P. Huggins, R. Yoshida The Path-PackingStructure of Graphs .............................. 256 A. Seb˝o, L. Szego˝ More on a Binary-Encoded Coloring Formulation ..................... 271 J. Lee, F. Margot Session 8 Single Machine Scheduling with Precedence Constraints................ 283 J.R. Correa, A.S. Schulz Table of Contents XI The Constrained Minimum Weighted Sum of Job Completion Times Problem ......................................................... 298 A. Levin, G.J. Woeginger Session 9 Near-Optimum Global Routing with Coupling, Delay Bounds, and Power Consumption............................................... 308 J. Vygen A Flow-Based Method for Improving the Expansion or Conductance of Graph Cuts ...................................................... 325 K. Lang, S. Rao AllRationalPolytopesAre TransportationPolytopesandAllPolytopal Integer Sets Are Contingency Tables ................................ 338 J. De Loera, S. Onn Session 10 A Capacity Scaling Algorithm for M-convex Submodular Flow.......... 352 S. Iwata, S. Moriguchi, K. Murota Integer Concave Cocirculations and Honeycombs...................... 368 A.V. Karzanov Minsquare Factors and Maxfix Covers of Graphs...................... 388 N. Apollonio, A. Sebo˝ Session 11 Low-Dimensional Faces of Random 0/1-Polytopes..................... 401 V. Kaibel On Polyhedra Related to Even Factors .............................. 416 T. Kira´ly, M. Makai Optimizing over Semimetric Polytopes............................... 431 A. Frangioni, A. Lodi, G. Rinaldi Author Index ................................................ 445 Robust Branch-and-Cut-and-Price for the Capacitated Vehicle Routing Problem Ricardo Fukasawa1, Jens Lysgaard2, Marcus Poggide Araga˜o3, Marcelo Reis3, Eduardo Uchoa4(cid:2), and Renato F. Werneck5 1 School of Industrialand SystemsEngineering, GeorgiaTech, USA [email protected]. 2 Department of Management Science and Logistics, AarhusSchool of Business, Denmark [email protected] 3 Departamento deInforma´tica, PUC Riode Janeiro, Brazil {poggi,mreis}@inf.puc-rio.br 4 Departamento deEngenharia deProdu¸ca˜o, UniversidadeFederal Fluminense, Brazil. [email protected] 5 Departmentof Computer Science, Princeton University,USA [email protected] Abstract. ThebestexactalgorithmsfortheCapacitatedVehicleRout- ing Problem (CVRP) have been based on either branch-and-cut or La- grangean relaxation/column generation. This paper presents an algo- rithm that combines both approaches: it works over the intersection of two polytopes, one associated with a traditional Lagrangean relax- ation over q-routes, the other defined by bound, degree and capacity constraints. This is equivalent to a linear program with exponentially many variables and constraints that can lead to lower bounds that are superior tothose given bypreviousmethods. Theresulting branch-and- cut-and-price algorithm can solve to optimality all instances from the literature with up to 135 vertices. This doublesthesize of theinstances that can be consistently solved. 1 Introduction LetG=(V,E)be anundirectedgraphwithverticesV ={0,1,...,n}.Vertex0 representsthedepot,whereasallothersrepresentclients,eachwithanassociated demand d(·). Each edge e∈E has a nonnegative length (cid:2)(e). Given G and two positive integers (K and C), the Capacitated Vehicle Routing Problem (CVRP) consists of finding routes for K vehicles satisfying the following constraints: (i) each route starts and ends at the depot, (ii) each client is visited by a single vehicle, and (iii) the total demand of all clients in any route is at most C. The goal is to minimize the sum of the lengths of all routes. This classical NP-hard problem is a natural generalization of the Travelling Salesman Problem (TSP), (cid:2) Corresponding author. D.BienstockandG.Nemhauser(Eds.):IPCO2004,LNCS3064,pp.1–15,2004. (cid:2)c Springer-VerlagBerlinHeidelberg2004