Branch-and-bound for bi-objective integer programming

In Pareto bi-objective integer optimization the optimal result corresponds to a set of non- dominated solutions. We propose a generic bi-objective branch-and-bound algorithm that uses a problem-independent branching rule exploiting available integer solutions, and cutting plane generation taking advantage of integer objective values. The developed algorithm is applied to the bi-objective team orienteering problem with time windows, considering two minimization objectives. Lower bound sets are computed by means of column generation, while initial upper bound sets are generated by means of multi-directional local search. Comparison to using the same ingredients in an ε-constraint scheme shows the effectiveness of the proposed branch-and-bound algorithm.



View Branch-and-bound for bi-objective integer programming