Artículo
Partial Gröbner bases for multiobjective integer linear optimization
Autor/es | Blanco Izquierdo, Víctor
Puerto Albandoz, Justo |
Departamento | Universidad de Sevilla. Departamento de Estadística e Investigación Operativa |
Fecha de publicación | 2012 |
Fecha de depósito | 2016-02-25 |
Publicado en |
|
Resumen | This paper presents a new methodology for solving multiobjective integer linear programs (MOILP) using tools from algebraic geometry. We introduce the concept of partial Gr¨obner basis for a family of multiobjective programs ... This paper presents a new methodology for solving multiobjective integer linear programs (MOILP) using tools from algebraic geometry. We introduce the concept of partial Gr¨obner basis for a family of multiobjective programs where the right-hand side varies. This new structure extends the notion of Gr¨obner basis for the single objective case to the case of multiple objectives, i.e., when there is a partial ordering instead of a total ordering over the feasible vectors. The main property of these bases is that the partial reduction of the integer elements in the kernel of the constraint matrix by the different blocks of the basis is zero. This property allows us to prove that this new construction is a test family for a family of multiobjective programs. An algorithm “´a la Buchberger” is developed to compute partial Gr¨obner bases, and two different approaches are derived, using this methodology, for computing the entire set of Pareto-optimal solutions of any MOILP problem. Some examples illustrate the application of the algorithm, and computational experiments are reported on several families of problems. |
Agencias financiadoras | Ministerio de Educación y Ciencia (MEC). España |
Identificador del proyecto | MTM2007-67433-C02-01 |
Cita | Blanco Izquierdo, V. y Puerto Albandoz, J. (2012). Partial Gröbner bases for multiobjective integer linear optimization. SIAM Journal on Discrete Mathematics, 23 (2), 571-595. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
Partial Gröbner bases for ... | 354.3Kb | [PDF] | Ver/ | |