MIP start is an infeasible solution
Answered
Hello, I am trying to solve my model using Gurobi in python. My problem is a Maximization problem. From solving another model with the same variables, I can find a good upper bound for my current problem (the variables associated with this upper bound are infeasible for my current model). I want to give this upper bound to the model to speed up the solving process in Gurobi. What I do is to give this infeasible solution as MIP start to my model. But, I don't see any improvement in solving time (I attached the log file).
My questions are:
1- What happens if I give an infeasible solution as a start decision variables to my model? How does Gurobi handle it?
2- Is there any other way that I can give an upper bound to my maximization model to speed up the solving process in Gurobi?
Thank you in advance for your help.
-
- A MIP start always needs to be feasible for Gurobi to use it. When you pass it an infeasible MIP start, you should see something like this in the log:
MIP start did not produce a new incumbent solution
- I am not aware of any way to do this (and I am not sure how it would help the solver). Are you sure you are looking for an upper bound? A feasible MIP start would yield a lower bound on the optimal objective in a maximation model.
Is there maybe a heuristic way to get a feasible solution for the second problem from the infeasible one that you could apply yourself before passing the MIP start to the solver?
0 - A MIP start always needs to be feasible for Gurobi to use it. When you pass it an infeasible MIP start, you should see something like this in the log:
-
Hi Silke, thank you for your response.
2: isn't it the case that if you find a lower upper bound for your maximization problem, it will speed up the process of finding an optimal solution?
3: I have another question. Is it possible for gurobi to find all the feasible solutions of a model? instead of an optimal solution? If yes, is this process of finding feasible solutions faster than finding an optimal solution?
I am asking this question because it takes 1.5 hours for gurobi to find the optimal solution for my MIP problem (on a real case study). Hence, I need to apply a faster heuristic to find a near-optimal solution (Like Tabu search or Simulated annealing). However, all these heuristics need a set of finite feasible solutions as an input, to find a good feasible solution among them. I don't know how am I able to find a large set of feasible solutions for my problem.
I do appreciate your help.
0 -
Hi Monir.
It is possible for Gurobi to find a feasible solution faster. Pay attention to this parameter when solving MIP: MIPFocus. The refman says:
" If you are more interested in finding feasible solutions quickly, you can select MIPFocus=1. If you believe the solver is having no trouble in finding good quality solutions, and wish to focus more attention on proving optimality, select MIPFocus=2. If the best objective bound is moving very slowly (or not at all), you may want to try MIPFocus=3 to focus on the bound. "
Then you may set another parameter MIPGap = (an acceptable gap, i.e., 0.1). After setting these parameter, it is likely that a feasible solution will be found faster.
IF you know a good upper bound for the maxi-problem, I think you may add a cut in the model: OBJ <= GoodUpperBound. I hope this will be useful for your problem.
0 -
Hi Silke,
Just confirming, if we provide infeasible solution then Gurobi completely reject the provided initial start and search the solution in its own way without considering the given initial start.
0 -
Yes, that is correct
0
Please sign in to leave a comment.
Comments
5 comments