2018 Optimization Days
HEC Montréal, Québec, Canada, 7 — 9 May 2018
WA1 Tutorial  J. Desrosiers
May 9, 2018 10:30 AM – 12:10 PM
Location: BDC (110) tutorials
Chaired by Fausto Errico
1 Presentation

10:30 AM  12:10 PM
Cycles, pricing, and pivots
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 nonnegative stepsize. 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 cyclecancelling 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 socalled residual problem are obtained in the process. We propose a family of algorithms with nondegenerate pivots and also show that the local search heuristics for vehicle routing problems, such as 2opt, 3opt, swap, relocate, … are indeed directed cycles on the residual network.