Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

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