Result: The two phases method: An efficient procedure to solve bi-objective combinatorial optimization problems

Summary: Since the set of feasibles solutions of multi-objective combinatorial optimization problems is not convex, we distinguish two kinds of efficient solutions: the so-called efficient ``supported'' solutions -- denoted by \({\mathcal S}{\mathcal E}({\mathcal P})\) -- and the efficient ``non-supported'' solutions -- denoted by \({\mathcal N}{\mathcal S}{\mathcal E}({\mathcal P})\) --; so that \({\mathcal E}({\mathcal P})= {\mathcal S}{\mathcal E}({\mathcal P})\cup {\mathcal N}{\mathcal S}{\mathcal E}({\mathcal P})\). We propose a method for solving such problems. This method proceeds in two phases as follows. (1) The first phase consists of generating the set \({\mathcal S}{\mathcal E}({\mathcal P})\) using Geoffrion's theorem. (2) The second stage generates subsets of \({\mathcal N}{\mathcal S}{\mathcal E}({\mathcal P})\) within the triangle underlying each pair of adjacent solutions belonging to \({\mathcal S}{\mathcal E}({\mathcal P})\). In this paper, the method is described for a multi-objective assignment problem in the bicriteria case. Finally, some concluding remarks are given.