What is phase 1 solution?
Answered
Dear community,
Below is a screenshot of a section of the log produced by Gurobi. I want to understand what this means, especially what a phase-1 solution is, and how I can use that information. I welcome any recommendations from you. Thank you.
-
The NoRel heuristic has 2 phases. In the first phase, the heuristic focuses on finding a feasible solution. The relaxation value tells how far the current infeasible solution is from a feasible one. The lower the value, the closer the heuristic is to shifting to phase 2. In phase 2, a feasible point is available and the heuristics tries to improve the objective value.
Best regards,
Jaromił1 -
Thank you. I also notice that this phase 1 solution is later ignored when the solver calculates the root relaxation and the starting best bound. Do you know why? If I understand correctly if the phase 1 solution provides a higher bound than the root relaxation, we can use it at the start to reduce the tree search. What do you think?
0 -
I also notice that this phase 1 solution is later ignored when the solver calculates the root relaxation and the starting best bound.
What exactly do you mean by phase 1 solution? Do you mean the relaxation value printed in phase 1? This is not a bound for the original model. The No Relaxation Heuristic does not compute a relaxation of the root node. The relaxation value you see in phase 1 is just an indicator of how far away the algorithm is from finding a first feasible point.
0 -
Thank you for the clarification. I thought NoRel heuristic generated a relaxed solution.
0 -
Dear Jaromil, May I also clarify the meaning of "relaxation" in "Found phase-1 solution: relaxation 32"? Thank you.
0 -
In phase 1, the no relaxation heuristic searches for a feasible point via trying to decrease the sum of infeasibilities. The relaxation value you see in phase one is the value of the current infeasibilities in the current candidate solution. For example if a current candidate has violates constraint 1 by 5 and constraint 2 by 8 and no other constraints then its relaxation value would be printed as 13.
1 -
In other words, relaxation = 0 means it is a feasible solution, right?
0 -
In other words, relaxation = 0 means it is a feasible solution, right?
Correct. However, note that a line with relaxation = 0 would not be printed, but the algorithm would proceed with phase 2. If you see a relaxation = 0 line, then it is probably not exactly 0 but some value slightly above 0 which is truncated in the output.
0 -
Related to your answer Jaromił, for very big problems, I think it would be nice to know not only the relaxation as the total cost of violations, but also information about which constraints are still violated. This might give insights about problem formulation. Is it possible to query this information?
Is it also possible to inject a feasible solution and combine it with norel heuristic for improving the feasible solution/having better bounds before root relaxation?
0 -
Is it possible to query this information?
No, it is currently not possible to query this information. My question would be, what would be the benefit of knowing which constraints are still violated? The violated constraints can change between iterations of the heuristic.
Is it also possible to inject a feasible solution and combine it with norel heuristic for improving the feasible solution/having better bounds before root relaxation?
Yes, if you provide a feasible initial solution, the No Relaxation Heuristic will start directly in phase 2.
0
Please sign in to leave a comment.
Comments
10 comments