Return to Colloquia & Seminar listing
MADDD Watch Party: Discrete Optimization Talks
Mathematics of Data & DecisionsSpeaker: | Anirudh Subramanyam, Sophie Huiberts |
Related Webpage: | https://talks.discreteopt.com/ |
Location: | Zoom/Discord |
Start time: | Fri, Oct 28 2022, 10:00AM |
Anirudh Subramanyam (Penn State): Branch-price-and-cut algorithms for robust vehicle routing under uncertainty
Abstract: Robust vehicle routing problems aim to identify a set of cost-effective routes for vehicles to traverse, such that all vehicle capacity and customer time window constraints are respected under any demand and travel time realization from given postulated uncertainty sets. To tackle such problems, this talk proposes a novel approach that embeds robust cutting planes within a branch-price-and-cut algorithm. Specifically, it uses deterministic pricing procedures to generate 'partially robust' vehicle routes, and robust versions of classical inequalities to guarantee 'complete robust feasibility' of routing designs. In contrast to recent approaches that modify the pricing algorithm, this approach is both modular and versatile. It permits the use of advanced branch-price-and-cut technology without significant modification, while also admitting a variety of commonly used uncertainty sets that could not be previously employed in a branch-price-and-cut framework.
Sophie Huiberts (Columbia University): Combinatorial Diameter of Random Polytopes
Abstract: The (combinatorial) diameter diam(P) of a polytope P is the maximum shortest path distance between any pair of vertices. This number comes up when studying the simplex method. We prove upper and lower bounds on the combinatorial diameter of a random "spherical" polytope, which is tight to within one factor of dimension when the number of inequalities is large compared to the dimension.
MADDD Watch Party: https://discord.gg/DxVG2GPY