A method for optimizing over the integer efficient set
Djamal Chaabane, Marc Pirlot, ,UMONS, Faculté Polytechnique, 9 Rue Houdain-Mons, Mons 7000 · Journal of Industrial and Management Optimization · 2010
In this paper, we are interested in optimizing a linear function onthe set of efficient solutions of a Multiple Objective Integer LinearProgramming problem ($MOILP $). We propose an exact algorithm formaximizing a linear function denoted $ \phi $ on the set ofefficient solutions of a $MOILP$ problem without having toenumerate explicitly all the elements of this set. Two techniquesare used: the first is to reduce progressively the admissibledomain by adding more constraints eliminating all the dominatedpoints by the current solution; the second, when the new solutionobtained by maximizing the function $\phi $ in the reduced area isnot efficient, an exploration procedure is applied over the edgesincident to this solution in order to find new alternativeefficient solutions if they exist. The algorithm produces not onlyan optimal value of the linear function but also a subset ofnon-dominated solutions in the direction of $\phi$ that can behelpful in the practice.