Multicriteria Discrete Optimization – and Related Topics

By Christian Roed Pedersen
PhD Dissertations
September 2006

Most real-world economic applications are, by nature, imposed with more objectives to be simultaneously optimized over a finite or countable infinite number of alternatives. This supports the use of multicriteria discrete optimization models -- an important research area to which this thesis contributes. In the first part of the thesis, basic knowledge on this topic is provided.

In the second part of the thesis, new results on ranking the $K$ best solutions to a given combinatorial optimization problem are discussed. More specifically, for the assignment problem, improvements to a classical ranking method are given and validated through numerical tests. For the minimum cost integer flow problem and for the transportation problem, novel ideas for ranking the $K$ best solutions are provided.

In the third part, theoretical results and algorithmic developments for multicriteria discrete optimization problems are given. In particular, for a new bicriterion generalization of the assignment problem an efficient two-phase solution procedure is developed relying on the scheme for ranking assignments. Extensive numerical results validate the efficiency of the solution procedure. For the multicriteria minimum cost flow problem a review of existing knowledge is given along with a discussion of a new exact solution procedure. Finally, a structured way of generating a representative system for the nondominated set of general bicriterion discrete optimization problems is presented. Further research directions within these topics are suggested.

In the fourth and final part of the thesis, a practical job scheduling problem is presented. A heuristic solution procedure is developed providing a significantly improved solution. Extensive numerical results are given to validate the robustness of the solution procedure.

Thesis advisor: Kim Allan Andersen
Format available: PDF (1588.9 kb)