Artículo
An exact algebraic ϵ-constraint method for bi-objective linear integer programming based on test sets
Autor/es | Hartillo Hermoso, Isabel
Jiménez Tafur, Haydee Ucha Enríquez, José María |
Departamento | Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) |
Fecha de publicación | 2020 |
Fecha de depósito | 2021-02-04 |
Publicado en |
|
Resumen | A new exact algorithm for bi-objective linear integer problems is presented, based on the classic - constraint method and algebraic test sets for single-objective linear integer problems. Our method pro- vides the complete ... A new exact algorithm for bi-objective linear integer problems is presented, based on the classic - constraint method and algebraic test sets for single-objective linear integer problems. Our method pro- vides the complete Pareto frontier N of non-dominated points and, for this purpose, it considers exactly |N | single-objective problems by using reduction with test sets instead of solving with an optimizer. Al- though we use Gröbner bases for the computation of test sets, which may provoke a bottleneck in princi- ple, the computational results are shown to be promising, especially for unbounded knapsack problems,for which any usual branch-and-cut strategy could be much more expensive. Nevertheless, this algorithmcan be considered as a potentially faster alternative to IP-based methods when test sets are available. |
Agencias financiadoras | Ministerio de Economía y Competitividad (MINECO). España Junta de Andalucía |
Identificador del proyecto | MTM2016-74983-C2-1-R
MTM2016-75024-P P12-FQM-2696 |
Cita | Hartillo Hermoso, I., Jiménez Tafur, H. y Ucha Enríquez, J.M. (2020). An exact algebraic ϵ-constraint method for bi-objective linear integer programming based on test sets. European Journal of Operational Research, 282 (2), 453-463. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
An exact algebraic constraint ... | 801.6Kb | [PDF] | Ver/ | |