Published by Oxford University Press 1996 (ISBN 0 19 853856 1)
István Maros and Gautam Mitra 1 Introduction 2 Problem statement 2.1 The primal problem 2.2 The dual problem 3 The revised simplex method 4 The sparse simplex (SSX) algorithm and its developments 4.1 Data structures 4.2 Preprocessing 4.3 Starting basis 4.4 Pricing 4.5 Degeneracy 4.6 Basis factorization and sparse updates 5 Design and computational issues of SSX 5.1 Design objectives 5.2 Analysis of benchmark problems 5.3 CPU processing profile of SSX components 5.4 Performance summaries 6 SSX on parallel machines 7 Sparse simplex within an integrated solver 7.1 Integration of interior point methods and sparse simplex 7.2 Use of simplex within mixed-integer programming 7.3 The outline of information flow 8 Future directions Bibliography
A few pages from the start of this chapter are available in Postscript here and here in PDF
Back to start of contents list
Cornelis Roos and Jean-Philippe Vial 1 Introduction 2 Complexity and convergence 2.1 Complexity and global convergence 2.2 Quadratic convergence 2.3 Notation 3 The theory of linear programming revisited 3.1 Introduction 3.2 Problem definition and assumptions 3.3 The target map and its inverse 3.4 The central path 3.5 The optimal partition 3.6 Limiting behaviour of the central path 3.7 Relaxing the interior point assumption 4 Target-following methods 4.1 Approximating target points 4.2 Short-step methods 4.3 Long-step target-following methods 5 Asymptotic behaviour of the predictor-corrector method 5.1 The predictor-corrector method 5.2 Convergence analysis 5.3 Asymptotic convergence 6 An infeasible start version of Karmarkar's algorithm 6.1 Karmarkar's canonical problem 6.2 Projective feasibility algorithm 6.3 The infeasible start projective algorithm Bibliography
A few pages from the start of this chapter are available in Postscript here and here in PDF
Back to start of contents list
Jacek Gondzio and Tamás Terlaky 1 Overview 2 Introduction 3 A prototype primal-dual algorithm 4 Some tricks that make it work 4.1 Presolve 4.2 Starting point 4.3 The linear algebra 4.4 Stepsize 4.5 Centering and higher-order methods 4.6 Stopping criteria 4.7 Theoretical versus practical worst-case complexity 5 Remarks on numerical difficulties 5.1 Degeneracy and IPMs 5.2 Ill-conditioned normal equations matrix 6 Optimal basis identification 6.1 Do we need an optimal basis? 6.2 How to get an optimal basis 7 Problems to be solved 7.1 Correct postoptimal analysis 7.2 Unbounded optimal faces, infeasible problems 7.3 Warm start Bibliography
A few pages from the start of this chapter are available in Postscript here and here in PDF
Back to start of contents list
Mauricio G.C. Resende and Panos M. Pardalos 1 Introduction 2 Implementation of interior point network flow methods 2.1 Literature review 2.2 Complexity issues 3 Components of interior point network flow methods 3.1 The dual affine scaling algorithm 3.2 Computing the direction 3.3 Network preconditioners for conjugate gradient method 3.4 Identifying the optimal partition 3.5 Recovering the optimal flow 4 Computational challenge to the network simplex 5 Concluding remarks Bibliography
A few pages from the start of this chapter are available in Postscript here and here in PDF
Back to start of contents list
Abilio Lucena and John E. Beasley 1 Introduction 2 Solving the Minimum Spanning Tree problem by LP 2.1 Solving the MST problem by cutting planes 2.2 The separation problem for SECs 2.3 Example 2.4 The use of column generation 2.5 The early fixing of variables 2.6 Conclusions 3 Formulations for the Steiner problem in graphs 3.1 The STP as an MST with side constraints 3.2 A formulation with cut-set inequalities for terminals 3.3 A formulation with variables for vertices and edges 3.4 A bidirected formulation for the SPG 3.5 Comparing the different formulations 4 Preprocessing and upper bounds for the SPG 4.1 Tests from the literature 4.2 Lagrangian test and SPG upper bounds 4.3 Computational results 5 Combining row and column generation 5.1 A bidirected version of Beasley's SPG formulation 5.2 Computational results 6 Branching 6.1 Initial tree node 6.2 Other tree nodes 6.3 Computational results 7 Conclusions Bibliography
A few pages from the start of this chapter are available in Postscript here and here in PDF
Back to start of contents list
John E. Mitchell 1 Introduction 2 Interior point branch and cut algorithms 2.1 Interior point cutting plane algorithms 2.2 Interior point branch and bound methods 3 Extensions 3.1 Algorithms which only require positive dual iterates 3.2 Solving an equivalent quadratic programming problem 3.3 Parallel implementations 3.4 Theoretical behaviour of column generation algorithms 4 Conclusions Bibliography
A few pages from the start of this chapter are available in Postscript here and here in PDF
Back to start of contents list
H. Paul Williams and Sally C. Brailsford
1 Introduction
2 Representation as integer programming models
2.1 Representations of logic connectives by integer
programming variables and constraints
2.2 The formulation of IP models
2.3 Mixed-integer programming representability
2.4 Systematic integer programming formulation
3 Solution methods in computational logic
3.1 Resolution and absorption
3.2 Resolution and cutting planes
3.3 Generalized resolution
3.4 The Davis-Putnam procedure
4 Horn clause systems
5 Mathematical programming solution methods
6 Further considerations
Bibliography
A few pages from the start of this chapter are available in Postscript here and here in PDF