1 Presentation

• 
  10:30 AM - 12:10 PM

  Cycles, pricing, and pivots

  • Jacques Desrosiers, presenter, GERAD, HEC Montréal
  • Jean-Bertrand Gauthier, GERAD - HEC Montréal

  Within the realm of linear programming, iterative algorithms that maintain feasibility throughout the solution process all identify a direction and then move along the latter with some non-negative step-size. We call the oracle used to identify a direction the pricing problem. Since this oracle maintains its form across the various algorithms, it is a common denominator whose canonical form is first observed in the minimum mean cycle-cancelling algorithm, the average cost of a cycle being taken over the number of arcs. In this respect, the network flow nomenclature is heavily borrowed thus contributing to the intuitive understanding of the pricing problem. It is well known that all directed cycles necessary to reach an optimal minimum cost flow solution can be observed on the residual network. Furthermore, each of these can individually accommodate some strictly positive flow. In optimization terms, each of these directed cycles, or combination of, forms a direction. A degenerate pivot is therefore induced when the selected cycle does not actually exist on the residual network. The concepts of paths and cycles along with some network flow properties can be transferred to linear programs and alternative necessary and sufficient optimality conditions expressed on the so-called residual problem are obtained in the process. We propose a family of algorithms with non-degenerate pivots and also show that the local search heuristics for vehicle routing problems, such as 2-opt, 3-opt, swap, relocate, … are indeed directed cycles on the residual network.