Contributed Session Mon.1.H 1029

Monday, 10:30 - 12:00 h, Room: H 1029

Cluster 15: Multi-objective optimization [...]

Linear and integer multiobjective optimization


Chair: Matthias Ehrgott



Monday, 10:30 - 10:55 h, Room: H 1029, Talk 1

Markku Kallio
Reference point method for multi-criteria optimization with integer variables

Coauthor: Merja Halme


An interactive approach for multi-objective optimization with integer variables is introduced. In each iteration, the decision maker (DM) is asked to give a reference point (new aspiration levels). Subsequent Pareto optimal point is the reference point projected into the set of feasible objective vectors using a suitable scalarizing function.
Thereby, the procedure solves a sequence of optimization problems with integer variables. In such process, the DM provides preference information via pair-wise comparisons of Pareto-optimal points identified. Using such preference information and assuming a quasi-concave utility function of the DM we restrict the set of admissible objective vectors by excluding subsets, which cannot improve over the solutions already found. Infeasibility in an iteration implies convergence and the best Pareto point found is an optimal solution. We also propose a procedure to test whether or not a solution is a supported Pareto point (optimal under some linear value function). Our reference point optimization procedure runs in AMPL/MOSEK. Numerical tests with multi criteria facility location models and knapsack problems indicate reasonably fast convergenc



Monday, 11:00 - 11:25 h, Room: H 1029, Talk 2

Matthias Ehrgott
A multi-objective linear programming approach to data envelopment analysis

Coauthors: Maryam Hassanasab, Andrea Raith


Data envelopment analysis (DEA) is a very popular parameter free method for performance measurement of decision making units. Based on linear programming (LP), DEA is closely related to multi-objective linear programming (MOLP) in the sense that efficient decision making units represent efficient solutions of some MOLP. We exploit this relationship and apply the primal and dual variants of Benson's outer approximation algorithm for MOLP as presented in Ehrgott, Löhne and Shao (2012) in order to solve DEA problems. We show that when applied to DEA many of the LPs that need to be solved in these algorithms reduce to trivial problems of finding the minima of finite sets. The geometric duality of multi-objective linear programming furthermore allows us to identify all efficient DMUs without solving a linear programme for every DMU using the dual outer approximation algorithm. Moreover the primal outer approximation algorithm directly finds all hyperplanes defining the efficient frontier of the production possibility set. We demonstrate the efficiency of our algorithm on a number of standard DEA reference problems.


  cash loans . Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Cialis is the one that definitely differs from all other products.