Efficient Storage of Pareto Points in Biobjective Mixed Integer Programming

Nathan Adelgren (), Pietro Belotti () and Akshay Gupte ()
Additional contact information
Nathan Adelgren: Department of Mathematics and Computer Science, Edinboro University of Pennsylvania, Edinboro, Pennsylvania 16444
Pietro Belotti: FICO, Birmingham B37 7GN, United Kingdom
Akshay Gupte: Department of Mathematical Sciences, Clemson University, Clemson, South Carolina 29634

INFORMS Journal on Computing, 2018, vol. 30, issue 2, 324-338

Abstract: In biobjective mixed integer linear programs (BOMILPs), two linear objectives are minimized over a polyhedron while restricting some of the variables to be integer. Since many of the techniques for finding or approximating the Pareto set of a BOMILP use and update a subset of nondominated solutions, it is highly desirable to efficiently store this subset. We present a new data structure, a variant of a binary tree that takes as input points and line segments in ℝ 2 and stores the nondominated subset of this input. When used within an exact solution procedure, such as branch and bound (BB), at termination this structure contains the set of Pareto optimal solutions.

We compare the efficiency of our structure in storing solutions to that of a dynamic list, which updates via pairwise comparison. Then we use our data structure in two biobjective BB techniques available in the literature and solve three classes of instances of BOMILP, one of which is generated by us. The first experiment shows that our data structure handles up to 10 7 points or segments much more efficiently than a dynamic list. The second experiment shows that our data structure handles points and segments much more efficiently than a list when used in a BB.

Keywords: biobjective mixed integer optimization; Pareto set; data structure (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2017.0783 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:30:y:2018:i:2:p:324-338

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().