A polynomial-time-delay and polynomial-space algorithm for enumeration problems in multi-criteria optimization

作者：Okamoto Yoshio^*; Uno Takeaki

来源：European Journal of Operational Research, 2011, 210(1): 48-56.

DOI：10.1016/j.ejor.2010.10.008

• Combinatorial optimization
• Complexity theory
• Linear programming
• Multiple objective programming

We propose a polynomial-time-delay polynomial-space algorithm to enumerate all efficient extreme solutions of a multi-criteria minimum-cost spanning tree problem, while only the bi-criteria case was studied in the literature. The algorithm is based on the reverse search framework due to Avis and Fukuda. We also show that the same technique can be applied to the multi-criteria version of the minimum-cost basis problem in a (possibly degenerated) submodular system. As an ultimate generalization, we propose an algorithm to enumerate all efficient extreme solutions of a multi-criteria linear program. When the given linear program has no degeneracy, the algorithm runs in polynomial-time delay and polynomial space. To best of our knowledge, they are the first polynomial-time delay and polynomial-space algorithms for the problems.

• 出版日期2011-4-1