Exploring Multi-Objective MILP Techniques in Gurobi
Answered
Hello everyone,
I am currently exploring various techniques for solving multi-objective mixed-integer linear programming (MILP) problems involving more than two objectives. So far, I have identified two promising approaches: multi-objective branch-and-bound and augmented epsilon constraints.
I would like to gather insights on the implementation of these methods in Gurobi. Specifically, I have a couple of questions:
-
Augmented Epsilon Constraints: How well do augmented epsilon constraints integrate with Gurobi's solution pools? Additionally, what strategies can I use to efficiently leverage previous solutions to identify further points on the Pareto front? How to realise different Epsilon bounds in Gurobi? Do I use e.g., Python and outer loops to determine points for different boundaries or is there an inner mechanism to iterate different Epsilon bounds?
-
Multi-Objective Branch-and-Bound: What is the best way to implement multi-objective branch-and-bound in Gurobi to effectively determine the Pareto front?
Thank you very much in advance!
-
Hi Benjamin,
As outlined in the documentation on multiple objectives, Gurobi provides an API to solve multi-objective optimization problems using three main approaches: 1) blending the objectives, 2) optimizing objectives hierarchically, or 3) combining approaches 1 and 2.
In the first approach, a single-objective optimization problem is solved where the objective function is a weighted sum of all objectives. The Gurobi Optimizer allows users to specify weights for each objective.
In the second approach, Gurobi optimizes objectives based on a user-defined priority order. When optimizing an objective of lower priority, the Gurobi Optimizer places constraints on higher-priority objectives to prevent them from degrading beyond a specified threshold. Gurobi’s API simplifies the implementation of this hierarchical approach.
It’s important to note that none of Gurobi’s supported approaches directly generate a Pareto frontier. To obtain a Pareto frontier, you would need to implement this manually. For instance, by adjusting weights in the blended approach, you can find different solutions, though this may not capture solutions in the non-convex parts of the Pareto frontier.
You could also adjust the priorities of different objectives in the hierarchical approach to explore various solutions.
Additionally, you can leverage Gurobi’s APIs to implement custom approaches tailored to your needs.
Please note that Gurobi does not support combining multi-objective optimization with a non-default value for the PoolSearchMode parameter.
Best regards,
Maliheh
0
Please sign in to leave a comment.
Comments
1 comment