Abstract: We consider the capacitated vehicle routing problem (VRP): a fixed fleet of delivery vehicles of uniform capacity must service at minimal transit cost from a common depot known customer demand for a single commodity. This problem is modeled as a side-constrained traveling salesman problem (TSP). Among the additional constraints are the vehicle capacity restrictions, analogous to TSP subtour elimination constraints. We present several variants of a branch-and-cut algorithm for this VRP model, with separation methodology for the capacity restrictions based on the TSP polyhedral relaxation. Specifically, when standard procedures fail to separate a candidate point, we attempt to separate it via decomposition into a convex combination of TSP tours; if successful, the tours present in this decomposition are examined for violated capacity restrictions, and if not, the Farkas Theorem provides a hyperplane separating the point from the TSP polytope. Computational results are given for an implementation within the parallel branch-and-cut framework COMPSys; the platform is the IBM SP2 of the Cornell Theory Center.
Kolloquium - 16 Uhr s.t.
Abstract: We give a brief survey of the theory of lattice packings and present some new developments and results in this field. Of particular interest will be an algorithm for computing the density of a densest lattice packing of an arbitrary 3-polytope.