ABSTRACT
This chapter considers integer linear. Programming problems only i.e. linear programming problems of the form (4.1)–(4.3) to which the integer condition has been added. Turning to possible solution methods for integer programming problems, one approach which immediately suggests itself is to solve the problem to hand as a straightforward linear programming problem using the simplex method and then to round the non-integer optimal solution values downwards in the case of maximisation and upwards in the case of minimisation. The foregoing comments demonstrate the process by which cutting plane methods for solving integer programming problems work. The chapter aims to demonstrate a specific version of the second major method for solving integer programming problems, branch and bound, by using it to solve the formulation. One feature of the branch and bound approach which offers an advantage over the cutting plane approach is that ‘good’ all-integer solutions emerge before the optimal solution.
