EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
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:00Room: 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
- Programming, Multi-Objective
- Programming, Mixed-Integer
- Programming, Linear
Status: accepted
Back to the list of papers