Optimization Online


Branching with Hyperplanes in the Criterion Space: the Frontier Partitioner Algorithm for Biobjective Integer Programming

Marianna De Santis (marianna.desantis***at***uniroma1.it)
Giorgio Grani (g.grani***at***uniroma1.it)
Laura Palagi (laura.palagi***at***uniroma1.it)

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.

Keywords: Multiobjective Optimization; Integer Programming; Criterion Space Search

Category 1: Other Topics (Multi-Criteria Optimization )

Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 3: Combinatorial Optimization (Branch and Cut Algorithms )


Download: [PDF]

Entry Submitted: 07/25/2018
Entry Accepted: 07/25/2018
Entry Last Modified: 07/31/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society