A Criterion Space Search Algorithm for Biobjective Mixed Integer Programming: The Triangle Splitting Method

We present the first criterion space search algorithm, the triangle splitting method, for finding all nondominated points of a biobjective mixed integer program. The algorithm is relatively easy to implement and converges quickly to the complete set of nondominated points. The algorithm maintains, at any point in time, a diverse set of nondominated points, and is thus ideally suited for fast approximation of the nondominated frontier. An extensive computational study demonstrates the efficacy of the triangle splitting method.

Data, as supplemental material, are available at http://dx.doi.org/10.1287/ijoc.2015.0646.