We present an algorithm for finding the complete Pareto frontier of biobjective integer programming problems. The method is based on the solution of a finite number of integer programs. The feasible sets of the integer programs are built from the original feasible set, by adding cuts that separate efficient solutions. Providing the existence of an oracle to solve suitably defined single objective integer subproblems, the algorithm can handle biobjective nonlinear integer problems, in particular biobjective convex quadratic integer optimization problems. Our numerical experience on a benchmark of biobjective integer linear programming instances shows the efficiency of the approach in comparison with existing state-of-the-art methods. Further experiments on biobjective integer quadratic programming instances are reported.

Branching with hyperplanes in the criterion space: The frontier partitioner algorithm for biobjective integer programming / De Santis, M.; Grani, G.; Palagi, L.. - In: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH. - ISSN 0377-2217. - 283:(2020), pp. 57-69. [10.1016/j.ejor.2019.10.034]

Branching with hyperplanes in the criterion space: The frontier partitioner algorithm for biobjective integer programming

De Santis M.
;
Grani G.
;
Palagi L.
2020

Abstract

We present an algorithm for finding the complete Pareto frontier of biobjective integer programming problems. The method is based on the solution of a finite number of integer programs. The feasible sets of the integer programs are built from the original feasible set, by adding cuts that separate efficient solutions. Providing the existence of an oracle to solve suitably defined single objective integer subproblems, the algorithm can handle biobjective nonlinear integer problems, in particular biobjective convex quadratic integer optimization problems. Our numerical experience on a benchmark of biobjective integer linear programming instances shows the efficiency of the approach in comparison with existing state-of-the-art methods. Further experiments on biobjective integer quadratic programming instances are reported.
Criterion space search; Integer programming; Multiobjective optimization
01 Pubblicazione su rivista::01a Articolo in rivista
Branching with hyperplanes in the criterion space: The frontier partitioner algorithm for biobjective integer programming / De Santis, M.; Grani, G.; Palagi, L.. - In: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH. - ISSN 0377-2217. - 283:(2020), pp. 57-69. [10.1016/j.ejor.2019.10.034]
File allegati a questo prodotto
File Dimensione Formato  
DeSantis_Preprint_Branching-with-hyperplanes_2020.pdf

accesso aperto

Note: https://doi.org/10.1016/j.ejor.2019.10.034
Tipologia: Documento in Pre-print (manoscritto inviato all'editore, precedente alla peer review)
Licenza: Creative commons
Dimensione 562 kB
Formato Adobe PDF
562 kB Adobe PDF Visualizza/Apri PDF
DeSantis_Branching-with-hyperplanes_2020.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 907.08 kB
Formato Adobe PDF
907.08 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1345013
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 6
social impact