column-and-row generation

An exact price-cut-and-enumerate method for the capacitated multi-trip vehicle routing problem with time windows

  • Yu Yang
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Transportation Tags , , ,

    We consider the capacitated multi-trip vehicle routing problem with time windows (CMTVRPTW), where vehicles are allowed to make multiple trips. The ability to perform multiple trips is necessary for some real-world applications where the vehicle capacity, the trip duration, or the number of drivers or vehicles is limited. However, it substantially increases the solution difficulty … Read more

    Provably High-Quality Solutions for the Meal Delivery Routing Problem

  • Martin Savelsbergh
  • Barış Yıldız
    • Categories Integer Programming, Optimization of Systems modeled by PDEs, Transportation Tags , , , , ,

    Online restaurant aggregators with integrated meal delivery networks have become more common and more popular in the past few years. Meal delivery is arguably the ultimate challenge in last mile logistics: a typical order is expected to be delivered within an hour (much less if possible), and within minutes of the food becoming ready. We … Read more

    Column Generation for Extended Formulations

  • Ruslan Sadykov
  • François Vanderbeck
    • Categories Integer Programming Tags , ,

    Working in an extended variable space allows one to develop tight reformulations for mixed integer programs. However, the size of the extended formulation grows rapidly too large for a direct treatment by a MIP-solver. Then, one can use projection tools and derive valid inequalities for the original formulation, or consider an approximate extended formulation (f.i., … Read more

    Computational study of large-scale p-Median problems

  • Pasquale Avella
  • Antonio Sassano
  • Igor Vasil'ev
    • Categories Branch and Cut Algorithms Tags , ,

    Given a directed graph G(V,A), the p-Median problem consists of determining p nodes (the median nodes) minimizing the total distance from the other nodes of the graph. We present a Branch-and-Cut algorithm yielding provably good solutions for instances up to 3795 nodes (14,402,025 variables). Key ingredients of our approach are: lagrangian relaxation, a simple procedure … Read more