How to find optimal range of decision variables?
AnsweredI have a MILP problem modelled on MATLAB, where the objective function is not very sensitive to some of the decision variables (the continuous ones to be precise). I know that because by solving the problem using Gurobi and the MATLAB native solver intlinprog, I get two different solutions that have the same optimum value. However, in this particular work, it can be very helpful if I can find out the entire range for each decision variable that can lead to the same optimum value. I don't know if there is a technical term for what I'm looking for, but I was curious if Gurobi had a way of providing this info that is better than brute force (i.e. changing the decision varaible into a parameter and doing the optimisation for a range of values of this parameter, noting which range returns the same optimum)
-
-
Gurobi Staff
I think what you are look for are Solution Pools. Via Solution Pool settings, you can make Gurobi search for the \(n\) best solution points.
1 -
-
Thank you! This is what I was looking for. If I understand this correctly, by setting the poolgap to a very small number, you can essentially search for a range of equally optimal solutions.
The question now is whether a good graphical way to display such results. I can display the maximum and minimum of each decision variable, essentially giving a range for their possible values that retain the optimum result. However, that would imply that all the decision variables are free to move around their ranges when in reality, setting some of them to a more extreme value would probably limit the other decision variables very much.
0 -
-
I want to add that I came across this answer:
How do I find additional solutions to a model? – Gurobi Help Center
It seems like solution pools only help you find solutions that are different combinations of the integer decision variables, and that trying to find the range of continuous variables is expensive and falls outside the scope of Gurobi.
0 -
-
-
Hi Ahmed,
I think the following fact may help here. A linear program can have either no solutions, exactly one optimal solution, or an infinite amount of optimal solutions. This is because if we have two solutions with the same objective value, any convex combination of these solutions will be valid and also have the same objective value (a nice little math exercise in properties of linear functions). So the existence of multiple optimal solutions to a linear program means there are infinite optimal solutions! Similarly, for a mixed integer linear model, if you have two optimal solutions whose integer and binary variable values are equal (and only differ in continuous variable values) then any convex combination of these solutions is optimal and there will be a infinite number of optimal solutions.
If this is the type of scenario you have then perhaps you could try the following:- solve the model to optimality
- create a copy of the model and fix binary and integer variables to their values found in the optimal solution. You can let them be continuous if you're fixing the value, or let Gurobi presolve handle it but either way the result will be linear program.
- add a constraint to force your original objective function to be equal to the value found in the optimal solution
then for each variable \(\texttt{x}\) you are interested in:- set a new objective function which maximizes the value of the variable \(\texttt{x}\) and optimize to get an upper bound
- set a new objective function which minimizes the value of the variable \(\texttt{x}\) and optimize to get a lower bound
You could also implement this approach using our multiple objective functionality, where you would optimize the original objective in the first step, and then one of these new objectives in the second step.
Whether this approach is practical will depend on i) whether your optimal solutions only differ in the continuous variables ii) the solve time of the linear program iii) how many continuous variables you want to examine.
- Riley
1 -
-
Thank you Riley for the detailed explanation. I understand the approach you layed out here and it seems to be a good way to tackle what I need. However, what strikes me as bothersome is that, for each variable x_i that I am interested in (around 4-6 depending on scenario) I will have to repeat the maximum and minimum optimisation for every integer combination found through the solution pools. Only then can I truly say I found the entire range allowed for that variable. The individual solve time of any these optimisations is quite fast; however, when running large amounts of simulations it will add up.
0 -
-
-
You're welcome Ahmed. If you are adding a constraint for the original objective, instead of the approach using multiple objective functionality, then you could use multiple scenarios where each scenario corresponds to a max (or min) for a particular variable*, so that you are only changing the objective coefficients between scenarios. This may give you a performance increase but you would still have to do this for each optimum solution in the solution pool with unique values for the binary/integer variables.
- Riley
* keep the problem as a maximization problem but use coefficients of 1 or -1 to artificially switch between max and min problems.1 -
Please sign in to leave a comment.
Comments
6 comments