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, each of them returning a Pareto optimal point. 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, Marianna; Grani, Giorgio; Palagi, Laura. - (2019), pp. 1-36. - DEPARTMENT OF COMPUTER, CONTROL, AND MANAGEMENT ENGINEERING ANTONIO RUBERTI TECHNICAL REPORTS.

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

Marianna De Santis
;
Giorgio Grani
;
Laura Palagi
2019

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, each of them returning a Pareto optimal point. 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.
Technical Report n. 3, 2019
multiobjective optimization; integer programming; criterion space search
02 Pubblicazione su volume::02a Capitolo o Articolo
Branching with hyperplanes in the criterion space: the frontier partitioner algorithm for biobjective integer programming / DE SANTIS, Marianna; Grani, Giorgio; Palagi, Laura. - (2019), pp. 1-36. - DEPARTMENT OF COMPUTER, CONTROL, AND MANAGEMENT ENGINEERING ANTONIO RUBERTI TECHNICAL REPORTS.
File allegati a questo prodotto
File Dimensione Formato  
DeSantis_Branching_2019.pdf

accesso aperto

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Creative commons
Dimensione 674.88 kB
Formato Adobe PDF
674.88 kB Adobe PDF Visualizza/Apri PDF

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/1290884
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact