Sesión Análisis Numérico y Optimización

Diciembre 14, 16:10 ~ 16:30

An exact algebraic $\epsilon$-constraint method for multi-objective linear integer programming based on test-sets

Hartillo, María Isabel

We present a new exact algorithm for multi-objective linear integer problems based in the classical $\epsilon$-constraint method and in the algebraic test-sets for single-objective linear integer problems. Our method is exact in two senses for the bi-objective case: it provides the complete Pareto frontier ${\mathcal N}$ of nondominated points and, for this purpose, we solve exactly $|{\mathcal N}|$ single-objective problems. This is very important for huge feasible regions with comparatively few nondominated points. For the multi-objective case the algorithm solves the problem, and although it may require some redundant calculation (as it is usual in the $\epsilon$-constraint approaches), the method is still very effective. Although our method depends on the computation of test-sets and this could be a bottleneck in principle, we show that the computational results are very promising, especially for unbounded knapsack problems, for which any usual branch and cut strategy could be much more expensive. We can manage examples of hundreds variables with hundreds of thousands nondominated points.

Autores: Hartillo, María Isabel / Jiménez, Haydee / Ucha, José María.