In this talk, we give an overview on our recent work on the multiobjective linear programming problem (MOLP) which is motivated by the fact that in the MOLP literature we rarely find theoretical performance guarantees of proposed algorithms. From a paper by Khachiyan, Boros, Borys, Elbassioni and Gurvich (2008), we see that if P is not equal to NP then we cannot enumerate all nondominated basic feasible solutions of an MOLP in polynomial total time. Instead, we suggest a model which got its motivation from the multicriteria decision making community: The goal is to find for each nondominated extreme point y in the objective space one solution x, such that Cx = y.
Thus, we analyze the running times of a popular MOLP algorithm, called Benson’s “outer approximation algorithm”, and of a recently discovered geometric dual variant. We show that both algorithms run in polynomial total time for a fixed but arbitrary number of objectives in this model. Additionally, we suggest improvements for both algorithms removing an exponential running time burden from them and revealing the individual advantages of both algorithms.
Moreover, we show that there is an application of the dual algorithm in solving multiobjective combinatorial optimization problems. Using this algorithm, we prove that enumerating all nondominated extreme value vectors can be done in polynomial total time if the number of objectives is fixed and the single objective optimization problem can be solved in polynomial time. Additionally, using our improvements and under the slight restriction of solving the lexicographic variant of the problem, we can further improve the running time.
This enables us to present---to the best of our knowledge---the first computational study for enumerating the extreme nondominated value vectors of the multiobjective assignment and spanning tree problem with more than four objectives. The results show that this algorithm is very competitive compared to the small number of algorithms available to solve this problem for more than two objectives. |