Topics in computational linear optimization | Tim Helge Hultberg
| | Abstract | Linear optimization has been an active area of research ever since the pioneering work of G. Dantzig more than 50 years ago. This research has produced a long sequence of practical as well as theoretical improvements of the solution techniques avilable for solving linear optimization problems.
Linear optimization problems covers both linear programming problems, which are polynomially solvable, and mixed integer linear programming problems, which belong to the class of NP-hard problems.
The three main reasons for the practical succes of linear optimization are: wide applicability, availabilty of high quality solvers and the use of algebraic modelling systems to handle the communication between the modeller and the solver.
This dissertation features four topics in computational linear optimization: A) automatic reformulation of mixed 0/1 linear programs, B) direct solution of sparse unsymmetric systems of linear equations, C) reduction of linear programs and D) integration of algebraic modelling of linear optimization problems in C++. Each of these topics is treated in a separate paper included in this dissertation.
The efficiency of solving mixed 0-1 linear programs by linear programming based branch-and-bound algorithms depends heavily on the formulation of the problem. In seeking a better formulation, automatic reformulation employs a range of different techniques for obtaining an equivalent formulation of a given pure or mixed integer programming problem, such that the new formulation has a tighter LP-relaxation than the original formulation.
The first paper surveys the use of automatic reformulation techniques for general mixed 0-1 linear programs. An implementation, Spiky, of a direct method for solving large sparse unsymmetric systems of linear equations is presented in the second paper. The method is based on a matrix modification approach applied to a spiked
triangular permutation of the system. The factorization consists of 3 steps.
1) a reordering of the matrix, such that only a small number, 's', of spike columns reach above the diagonal is determined.
2) a block LU factorization of an augmented system is computed. This involves the solution of a sparse triangular system with 's' right-hand sides. Solution sparsity is exploited in the sparse triangular solves of the block LU factorization.
3) a factorization of the Schur complement matrix, of order 's', is computed. The idea of this factorization method comes from Gondzio (Gondzio:94c), but has been improved in several ways. Most importantly: a) A new fast reordering algorithm is used. b) Sparsity of the Schur complement is exploited.
Simple techniques for reducing the size of linear programs prior to the application of a solution algorithm are incorporated as important parts of most LP solvers. The usual LP reduction techniques require a very limited effort but nevertheless often result in substantial reductions. One of the reasons for this good performance is the way LP models are typically formulated using algebraic modelling languages. The third paper presents a common framework for LP reduction algorithms and shows how the usual LP reduction techniques fit into this framework. It also demonstrate how a stronger bound strengthening and the use of primal information to improve the dual bounds can be used to obtain further reductions.
In the fourth and last paper, a prototype implementation of a C++ class library, FLOPC++, for formulating linear optimization problems is presented. Using FLOPC++, linear optimization models can be specified in a declarative style, similar to algebraic modelling languages such as GAMS and AMPL. While preserving the traditional strengths of algebraic modelling languages, FLOPC++ eases the integration of linear optimization models with other software components. The class library implements a full-fledged algebraic modelling language with indexed variables and constraints, repeated sums, index arithmetic and conditional exceptions.
Besides the articles the thesis features six introductory chapters, including a description of two real-world applications of linear optimization, in which I have been involved during my Ph.D. study. | | Type | Ph.D. thesis [Academic thesis] | | Year | 2000 | | Publisher | Informatics and Mathematical Modelling, Technical University of Denmark, DTU | | Address | Richard Petersens Plads, Building 321, DK-2800 Kgs. Lyngby | | Series | IMM-PHD-2000-78 | | Electronic version(s) | [pdf] [ps] | | BibTeX data | [bibtex] | | IMM Group(s) | Operations Research |
|