A Criterion Space Search Algorithm for Biobjective Integer Programming: The Balanced Box Method
Natashia Boland, Hadi Charkhgard, Martin Savelsbergh
INFORMS Journal on Computing · 2015 · Volume 27 · Issue 4
Abstract
We present a new criterion space search algorithm, the balanced box method, for finding all nondominated points of a biobjective integer program. The method extends the box algorithm, is easy to implement, and converges quickly to the complete set of nondominated points. Because the method maintains, at any point in time, a diverse set of nondominated points, it is ideally suited for fast approximation of the efficient frontier. In addition, we present several enhancements of the well-known ε -constraint, augmented weighted Tchebycheff, and perpendicular search methods. An extensive computational study, using instances from different classes of combinatorial optimization problems, demonstrates the efficacy of the balanced box method.
Keywords
biobjective integer programming, criterion space search algorithm, balanced box method
Enable JavaScript for citation tools and additional paper interactions.