Branch-and-bound for bi-objective mixed integer programming
Sprache des Vortragstitels:
Englisch
Original Tagungtitel:
Operation Research (OR 2022)
Sprache des Tagungstitel:
Englisch
Original Kurzfassung:
In bi-objective mixed integer optimization, the Pareto frontier can be composed of closed, open, half-open line segments or even isolated points. In this work, we generalize an existing branch-and-bound algorithm designed for
bi-objective integer linear programming to bi-objective mixed integer linear programming. We show that some of its key ingredients like filtering and branching can easily be adapted to the mixed integer case. Furthermore, we integrate several recently proposed enhancements
such as presolving and probing and we propose to use the fact that each objective space point corresponding to a solution from the decision space may have multiple different inverse images in the decision space, which will allow us to compare their variables and potentially
allowing us to discard non-interesting areas of the objective space. The proposed algorithm is tested on instances from the literature and compared to other recently proposed exact methods for bi-objective mixed integer programming