Biobjective Mixed-Integer Linear Programming

In a biobjective mixed-integer linear program, the objectives are two linear functions that are subject to the same set of linear constraints. These objectives are often conflicting, i.e., we can't improve the value of one of the objectives without a deterioration in the value of the other objective. Considering that we have two objectives, and also that we may observe the presence of integer decision variables, this problem is a difficult one to solve.

The nondominated (also known as Pareto) frontier for a biobjective mixed-integer linear program may contain Isolated points and closed, half-open, and open segments. Even if we find a way to create a representation of the entire nondominated frontier, the number of points may be infinite and overwhelming to make a comprehensive analysis.

This is why we came up with the following idea:

• A New Algorithm to Optimize a Function over the Set of Efficient Solutions for Biobjective Mixed Integer Linear Programming

  We develop a new criterion space search algorithm for optimizing a linear function over the set of efficient solutions for biobjective mixed-integer linear programming problems. This algorithm reduces the representation of the entire nondominated frontier to just one point. The algorithm is easy to implement and because it maintains a lower and an upper bound on the value of the linear function at any point in time, it often does not have to explore the entire nondominated frontier, and it can be used to quickly generate a provably high-quality approximate solution.

  
  

  We develop two implementations for the algorithms, both available at:

• OOES_Algorithm.cpp (C++ Implementation): Designed to use CPLEX. Is fast and memory friendly, Recommended for CPUs with limited capacity.
• OOESAlg.jl (Julia Implementation): Designed to use any single-objective mixed-integer linear solver supported by MathProgBase.jl. It naturally exploits parallelization. Recommended for high-capacity workstations.



Our instances are available at:

• Optimization-over-efficient-set-for-BOMILP-instances



Our algorithms were developed as part of academic research. If you would like to help support it, we would be grateful if you could cite:

• Sierra-Altamiranda, A., & Charkhgard, H. (2018) A New Exact Algorithm to Optimize a Linear Function Over the Set of Efficient Solutions for Bi-objective Mixed Integer Linear Programming. Accepted for publication at INFORMS Journal on Computing.
• Sierra-Altamiranda, A., & Charkhgard, H. (2018) OOES. jl: A julia package for optimizing a linear function over the set of efficient solutions for bi-objective mixed integer linear programming. Submitted to International Transactions in Operational Research.