Adding cuts within Gurobi callback only once.
回答済みReading the Callback Codes documentation, I noticed that when `where == MIPNODE` the MIPNODE_PHASE infomation is available, which is described as follows:
Current phase in the MIP solution process. Possible values are 0 (in the NoRel heuristic), 1 (in the standard MIP search), or 2 (performing MIP solution improvement). Predefined constants are available (e.g., GRB.PHASE_MIP_SEARCH).
So far I have always assumed that whenever my callback is called with `where == MIPNODE`, it would be related to a distinct branch-and-bound node and, hence, to a different relaxed solution.
Does the above description mean that my callback will be called more than once for the same branch-and-bound node but with different MIPNODE_PHASE values?
When my callback is called with `where == MIPNODE` I want to check if some cuts are violated and load the violated ones, however I would like to do so only once per mip node. So, how can I be sure not to evaluate the same relaxed solution twice looking for violated constraints/cuts?
-
-
Gurobi Staff
Hi Lorenzo,
The different MIP search phases are the following:
- NoRel phase: This optional heuristic starts immediately after presolving, but only if it is activated via parameters NoRelHeurTime or NoRelHeurWork.
- Standard MIP search: This is the classical branch-and-bound algorithm that runs for every MIP and that you most probably refer to.
- Solution improvement phase: This phase can be optionally started after the standard MIP search with the parameters ImproveStartGap, ImproveStartNodes, or ImproveStartTime. It will essentially continue with branch-and-bound but put a significant focus on heuristics.
If you do not activate phases 1 and 3 with the according parameters, they will not run. Additionally, since those phases are very different from each other, the chance is low that you get the same relaxation solution twice.
But note that the MIPNODE callback can be called multiple times per branch-and-bound node. This is because after each internal cut pass, the relaxation solution is re-computed, leading to a different solution and a new call to your cut procedure. But this should be fine for you, I guess.
Best regards,
Mario0 -
-
Hi Mario,
thank you for the detailed explanation. Is there some standard (meaningful) technique in Gurobi to check for violated cuts only once in a while rather than on each MIPNODE call? (checking all potentially violated cuts may be expensive in my case). Or should I just rely on some trivial strategy (such as a simple random generator to decide whether to check or not)?
0 -
-
-
The solver, unfortunately, does not include any such strategies, but you could use the information that can be queried in the callback to build your own strategies.
For example, MIPNODE_NODCNT gives you the number of branch-and-bound nodes already processed:
- If the number has not changed since the last callback, then you are still in the same node and probably do not want to add more violated cuts.
- You could also use the value to separate cuts only in every x-th node.
- Usually, it is more important to add cuts early in the branch-and-bound tree since those might be effective for larger parts of the tree. So, in the beginning, you could separate cuts in every node and then you increase the interval iteratively.
If you add cuts in multiple iterations within a single branch-and-bound node, the progress of the dual bound (MIPNODE_OPJBND) within the same node gives you some idea of how effective your cuts are. If there is not much improvement anymore, you might stop prematurely.
0 -
-
Very helpful, thank you!
0 -
サインインしてコメントを残してください。
コメント
4件のコメント