Theory and algorithms for multi-objective integer programming

This thesis presents new theoretical and algorithmic results for generating the nondominated frontier of a multi-objective integer program. The new algorithms presented in this thesis work in criterion space, they can be implemented relatively easily, they do not require a lot of memory, and they are faster than existing algorithms in the literature. The thesis contains three parts. In Part I, we focus on biobjective optimisation problems. We first introduce a new criterion space search method, the balanced box method, for solving biobjective integer programs. We then present the first criterion space search algorithm, the triangle splitting method, for solving biobjective mixed integer programs. In Part II, we focus on optimisation problems with more than two objective functions. We first introduce two new criterion space search methods, the L-shape search method and the quadrant shrinking method, for solving triobjective integer programs. We then present an extension of the L-shape search method, which can solve multi objective integer programs with an arbitrary number of objective functions. Finally, we show how this algorithm can be modified in order to efficiently optimise a linear function over the set of nondominated points in the efficient frontier. This implies that the algorithm can also be used to rapidly compute the nadir point of a multi-objective integer program. In Part III, we investigate the connection of multi-objective optimisation with other fields. We first show that the balanced box method can be used efficiently to compute the nondominated Nash points of a normal form game with two players. We then investigate a class of optimisation problems with a multi-linear objective function and affine constraints. An optimal solution of such a problem is efficient (Pareto-optimal), and we present a polynomial time LP-based approach to compute it.