EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

2953. On the extension of branch-and-bound methods formixed-integer linear programs

Invited abstract in session MC-52: Multi-objective Combinatorial Optimization, stream Combinatorial Optimization.

Monday, 12:30-14:00
Room: 8003 (building: 202)

Authors (first author is the speaker)

1. Nicolas Forget
Institute of Production and Logistics Management, Johannes Kepler University Linz
2. Sophie Parragh
Institute of Production and Logistics Management, Johannes Kepler University Linz

Abstract

In the recent years, a lot of attention was given to branch-and-bound techniques for solving pure integer linear programs with an arbitrary number of objectives. Significant progress and contributions were made. On the other hand, the efficiency and practicality of branch-and-bound methods for bi-objective mixed-integer linear was shown through a variety of works in the past decade. Intuitively, the next step is to address mixed-integer linear programs with three or more objective functions. Again, linear-relaxation based branch-and-bound frameworks appear to be the methods of choice because of the continuous nature of some variables. Unfortunately, due to the complex structure of the non-dominated set of such problems, straightforward extension of existing branch-and-bound frameworks to solve multi-objective mixed-integer linear programs is not possible. In this talk, we identify some of these obstacles(representation and navigation of the non-dominated set, update of the upper bound set, dominance test, etc.), and present various solutions we explored to address these issues. Moreover, we highlight implementation-related and performance-related difficulties, and conclude with future works.

Keywords

Status: accepted

Back to the list of papers