Stabilizing Column Generation via Dual Optimal Inequalities with Applications in Logistics and Robotics

Simple item page
dc.contributor.advisorBalan, Raduen_US
dc.contributor.authorHaghani, Naveeden_US
dc.contributor.departmentApplied Mathematics and Scientific Computationen_US
dc.contributor.publisherDigital Repository at the University of Marylanden_US
dc.contributor.publisherUniversity of Maryland (College Park, Md.)en_US
dc.date.accessioned2021-02-15T06:30:20Z
dc.date.available2021-02-15T06:30:20Z
dc.date.issued2020en_US
dc.description.abstractThis work addresses the challenge of stabilizing column generation (CG) via dual optimal inequalities (DOI). We present two novel classes of DOI for the general context of set cover problems. We refer to these as Smooth DOI (S-DOI) and Flexible DOI (F-DOI). S-DOI can be interpreted as allowing for the undercovering of items at the cost of overcovering others and incurring an objective penalty. SDOI leverage the fact that dual values associated with items should change smoothly over space. F-DOI can be interpreted as offering primal objective rewards for the overcovering of items. We combine these DOI to produce a joint class of DOI called Smooth-Flexible DOI (SF-DOI). We apply these DOI to three classical problems in logistics and operations research: the Single Source Capacitated Facility Location Problem, the Capacitated p-Median Problem, and the Capacitated Vehicle Routing Problem. We prove that these DOI are valid and are guaranteed to not alter the optimal solution of CG. We also present techniques for their use in the case of solvingCG with relaxed column restrictions. This work also introduces a CG approach to Multi-Robot Routing (MRR). MRR considers the problem of routing a fleet of robots in a warehouse to collectively complete a set of tasks while prohibiting collisions. We present two distinct formulations that tackle unique problem variants. The first we model as a set packing problem, while the second we model as a set cover problem. We show that the pricing problem for both approaches amounts to an elementary resource constrained shortest path problem (ERCSPP); an NP-hard problem commonly studied in other CG problem contexts. We present an efficient implementation of our CG approach that radically reduces the state size of the ERCSPP. Finally, we present a novel heuristic algorithm for solving the ERCSPP and offer probabilistic guarantees forits likelihood to deliver the optimal solution.en_US
dc.identifierhttps://doi.org/10.13016/yiy5-tgnf
dc.identifier.urihttp://hdl.handle.net/1903/26845
dc.language.isoenen_US
dc.subject.pqcontrolledOperations researchen_US
dc.subject.pquncontrolledColumn Generationen_US
dc.subject.pquncontrolledDual Optimal Inequalitiesen_US
dc.subject.pquncontrolledOperations Researchen_US
dc.subject.pquncontrolledOptimizationen_US
dc.subject.pquncontrolledRobot Routingen_US
dc.subject.pquncontrolledStabilizationen_US
dc.titleStabilizing Column Generation via Dual Optimal Inequalities with Applications in Logistics and Roboticsen_US
dc.typeDissertationen_US

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Haghani_umd_0117E_21298.pdf
Size:
3.53 MB
Format:
Adobe Portable Document Format
Download

Collections

UMD Theses and Dissertations
Computer Science Theses and Dissertations
Mathematics Theses and Dissertations