Model Solving in Mathematical Programming

In this sequel to "Model Building in Mathematical Programming", the author explains mathematical programming through numerical examples solved independently of any computer system, together with a commentary on the nature of the methods. The examples are intended to motivate the discussion and help with understanding, and definitions are introduced in context rather than formally. The same example is treated by different methods so that the temptation to tailor examples to methods is avoided. Moreover, the numerical examples used (some taken from MBMP) are sufficiently small to be solvable by hand, although computer packages will be of use in some of the exercises. The main aim of the text is to describe methods for solving the general models of linear programming, separable non-linear programming and integer programming.

Table of Contents:
Part 1 The nature of mathematical programming: linear programming; non-linear programming; integer programming; application areas; special types of model - networks, economic models, structured models, game theory models; computer data structures; measuring the number of computational steps; history, references and future developments; exercises. Part 2 General methods for linear programming: solving systems of linear equations; solving systems of linear inequalities and equations; the Simplex Algorithm I - finding an optimal solution; the simplex algorithm II - finding a feasible solution with bounded variables; the dual of a linear programme; the dual simplex algorithm; generating allvertices and extreme rays; the method of projective transformations; history, references and future developments; exercises. Part 3 Methods for specialist linear programming models: minimum cost and maximum flow through a network; the assignment problem; the shortest path problem and dynamic programming; history, references and future developments; exercises. Part 4 Computational implementation of the simplex algorithm: the revised simplex algorithm and product form of the inverse; reinverting the basis matrix; maintaining an L/U inverse between interations; numerical considerations; sensitivity analysis and parametric programming; computational implementation of the network form of the simplex algorithm; history, references and future developments; exercises. Part 5 Non-calculus methods for non-linear programming: separable models; separable programming for local optima; conversion of non-linear separable models to integer programmies; conditions for local optimality; history, references and future developments; exercises. Part 6 General methods for integer programming: total unimodularity and the integrality property; the branch-and-bound method; the importance of efficient formulations; generating cutting planes; duality and integer programming; history, references and future developments; exercices. Part 7 Computational implementation of the linear programming based branch-and-bound algorithm: updating the basis; priorities, penalties and pseudo-costs for branching variables; branching on special ordered sets of variables; tree search strategies; history, references and future developments; exercises. Part 8 Specialist methods for integer programming models: implicit enumeration for pure 0-1 models; Boolean algebra for pure 0-1 models; combinatorial problems; lagrangan, surrogate and cone relaxations; heuristic and local search methods; hisitory, references and future developments; exercises.