Linear optimization and extensions (Q1892405): Difference between revisions

Written by a leading expert of the field, this textbook is a very detailed, complete and up-to-date presentation of linear optimization and its extensions (such as large scale combinatorial or mixed-integer problem solving). We feel that the most informative way to review the book in this context would be to indicate the, slightly modified, table of its contents: 1. Introduction (historical remarks - examples); 2. The linear programming problem (standard, canonical forms - matrices, vectors, scalars); 3. Basic concepts (the fundamental role of basic feasible solutions - notational conventions, illustrations on the example problems); 4. Further preliminaries (bases and basic feasible solutions - detecting optimality and unboundedness - a rank one update of a matrix' inverse - changing bases); 5. Simplex algorithms (notation, reading instructions, updating - Big M or how to get started - selecting a pivot row and column - data structures - tolerances in problem data - product form of a basis - equation format and cycling - finiteness - canonical form - block pivots); 6. Primal dual pairs (weak and strong duality - economic interpretation and applications - solvability, redundancy, separability - a dual simplex algorithm - post optimality - a dynamic simplex algorithm (in which both row and column generation are permitted); 7. Analytical geometry (points, lines, subspaces - polyhedra - ideal (i.e. minimal and complete) descriptions - cones - point sets - affine transformations - minimal generators - double description algorithms (including an all integer version) - digital sizes of rational polyhedra and linear optimization - geometry and complexity of simplex algorithms - circles, spheres, ellipsoids); 9. Ellipsoid algorithms (matrix norms, approximate inverses, matrix inequalities - ellipsoid ``halving'' in approximate arithmetic - polynomial time algorithms for linear programming (including linear programming and binary search) - deep cuts, sliding objective, large steps, line search and the corresponding DCS ellipsoid algorithm - optimal separators, most violated separators, separation - \(\varepsilon\) solidification of flats, polytopal norms, rouding - optimization and separation (including \(\varepsilon\) optimal sets and \(\varepsilon\) optimal solutions, finding direction vectors in the asymptotic cone, a CCS ellipsoid algorithm, linear optimization and polyhedral separation); 10. Combinatorial optimization (the Berlin airlift model revisited - complete formulations and their implications - extremal characterizations of ideal formulations (including blocking and antiblocking polyhedra) - polyhedra with the integrality property; Appendices A: Short-term financial management; B: Operations management in a refinery and C: Automatized production: PCBs and Ulysses' problem. As the author states in his Preface, ``purely theoretical complexity issues of linear programming play a definite minor role in our development; my interest, besides theory, is numerical problem solving and computation''. The thorough treatment of ellipsoid algorithms allows to show the polynomial-time solvability of linear programs as well as the polynomial-time equivalence of optimization and separation thus providing a sound theoretical basis for the currently most successful approach in solving large scale combinatorial optimization problems, the branch-and-out method. A series of historical side-remarks make the text a pleasure to read and a number of well-posed exercises should contribute to a comprehensive understanding.