Development of a Bi-objective Branch and Bound Algorithm

Linear programming based branch and bound is a standard algorithm to solve integer programming problems. A branch and bound algorithm solves linear programming relaxations at every node of the branch and bound tree and then performs branching to eliminate fractional variables from the solution.

This project concerns the development of a linear programming based branch and bound algorithm for integer programmes with two objective functions. In such an algorithm, a bi-objective linear programme needs to be solved at every node of the branch and bound tree. The lower bound now becomes a lower bound set and comparison of bound sets is required. At the end of the procedure, a set of so-called supported efficient solutions of the bi-objective integer programme is obtained. The algorithm then needs to enter a second phase to identify the non-supported efficient solutions, whose existence is caused by the presence of two objective functions. This phase requires new techniques for branching and bounding that are specific to bi-objective problems and that are to be developed in this project.

For further information contact Matthias Ehrgott.

Return to the Optimisation Research Group page.