Mavrotas and Diakoulaki's Algorithm for Multiobjective Mixed 0-1 Linear programming Revisited

1 Problematic Many concrete and important problems can be formulated by a mixed-integer linear programme, for example the facility location problem [1]. For those problems, it is natural to consider the mul- tiobjective paradigm since several conflicting objectives have to be taken into account. For example, the common cost objective can be balanced by an objective of availability for the customers in the case of facility location problems. Although the field of multiobjective optimization has been extensively studied for the last fifteen years, efforts have been mainly focused on problems with variables exclusively continuous or discrete. The difficulties encountered with mixed integer programmes have caused this particular area to be barely investigated until now [2]. On the one hand, multiobjective linear programmes (MOLP) have convex solution sets and are solved thanks to methods such as the multiobjective simplex algorithm. On the other hand, multiob- jective integer linear programmes (MOILP) have discrete solution sets and require huge enumerations for their solution. MOLP and MOILP are particular cases of multiobjective mixed-integer linear pro- grammes (MOMILP), thus characteristics of both former classes of problems can also be observed in MOMILP. We can note that properties and solution methods for MOLP and MOILP are completely different. How to efficiently solve MOMILP ? Which properties can be used for this purpose ? 2 Literature and Proposal An exact solution method for MOMILP problems with binary variables has been introduced by Mavrotas and Diakoulaki to determine a discrete representation of the nondominated set [3]. This ROADEF 2010 - Toulouse method is a branch and bound algorithm that explores every possible combination of values for the binary variables and solves the MOLP problem generated when fixing all of them. In the original paper, some dominated points may remain in the output of the algorithm. In 2005, the authors have published a correction to their method in order to fix this aspect [4]. However, elements showing that the corrections are still not sufficient have been provided [5]. In particular, a way to represent correctly the set of nondominated points is required. In our talk, we will propose a way to correct Mavrotas and Diakoulaki's method in the biobjective case, based on an appropriate representation of the nondominated set. We will also discuss compu- tational improvements and finally present numerical results. 3 Perspectives This work is a first step with the aim to develop knowledge about MOMILP. Our goal is to propose methods for their exact solution that can handle large scale instances