A branch-and-bound method for biobjective MILP

Pietro Belotti


Solving a biobjective optimization problem amounts to enumerating all of its Pareto-optimal solutions. If the problem is a continuous linear program, the  Pareto set can be obtained by applying techniques such as the parametric simplex method. For the mixed integer linear programming (MILP) case, one needs an implicit enumeration technique such as branch and bound (BB). Among the main features of such a BB algorithm is a set of fathoming rules to eliminate portions of the feasible set by proving that they contain no Pareto optimal solutions. I will describe effective fathoming rules that only require a simple modification of the node problem and can be carried out very efficiently.