Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Criss-cross methods are pivot algorithms that solve linear programming problems in one phase starting with any basic solution. The first finite criss-cross method was invented by Chang, Terlaky and Wang independently. Unlike the simplex method that follows a monotonic edge path on the feasible region, the trace of a criss-cross method is neither monotonic (with respect to the objective function) nor feasibility preserving. The main purpose of this paper is to present mathematical ideas and proof techniques behind finite criss-cross pivot methods. A recent result on the existence of a short admissible pivot path to an optimal basis is given, indicating shortest pivot paths from any basis might be indeed short for criss-cross type algorithms. The origins and the history of criss-cross methods are also touched upon.
Volkan Cevher, Grigorios Chrysos, Efstratios Panteleimon Skoulakis
Corentin Jean Dominique Fivet, Jonas Warmuth, Jan Friedrich Georg Brütting