2021/10/03 by Julian Yarkony, Yarkony, Julian, Naveed Haghani +3
Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Search Problems #Transportation and Mobility Innovations #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.2110.01070
openalex publication_date 2021/10/03 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
In this article we introduce Graph Generation, an enhanced Column Generation\n(CG) algorithm for solving expanded linear programming relaxations of mixed\ninteger linear programs. To apply Graph Generation, we must be able to map any\ngiven column to a small directed acyclic graph for which any path from source\nto sink describes a feasible column. This structure is easily satisfied for\nvehicle routing and crew scheduling problems; and other such problems where\npricing is a resource constrained shortest path problem. Such graphs are then\nadded to the restricted master problem (RMP) when the corresponding column is\ngenerated during pricing. The use of Graph Generation does not weaken the\nlinear programming relaxation being solved. At any given iteration of CG\nenhanced by Graph Generation; the technique permits the RMP to express a much\nwider set of columns than those generated during pricing, leading to faster\nconvergence of CG. Graph Generation does not change the structure of the CG\npricing problem. We show how the method can be applied in a general way, and\nthen demonstrate the effectiveness of our approach on the classical Capacitated\nVehicle Routing Problem.\n