An exact algebraic ϵ-constraint method for bi-objective linear integer programming based on test sets

Abstract

A new exact algorithm for bi-objective linear integer problems is presented, based on the classic - constraint method and algebraic test sets for single-objective linear integer problems. Our method pro- vides the complete Pareto frontier N of non-dominated points and, for this purpose, it considers exactly |N | single-objective problems by using reduction with test sets instead of solving with an optimizer. Al- though we use Gröbner bases for the computation of test sets, which may provoke a bottleneck in princi- ple, the computational results are shown to be promising, especially for unbounded knapsack problems,for which any usual branch-and-cut strategy could be much more expensive. Nevertheless, this algorithmcan be considered as a potentially faster alternative to IP-based methods when test sets are available.