All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
How to implement a diving heuristic Diving heuristics are an important addon to the branch-and-cut search. A diving heuristic explores a single probing path down the search tree. In contrast to the regular search guided by branching rule(s) and the selected node selector, the diving is performed in an auxiliary tree originating from the focus node of the main search tree where the heuristic was called. The advantage of this approach is that many different scoring mechanisms can be safely tried as diving heuristic and may probably lead to better solutions. SCIP has a lot of diving heuristics included in its default plugin set. ## User parameters and properties for every divesetEvery diveset controls the diving behavior through a set of user-defined parameters, which are explained in the following: - MINRELDEPTH
- the minimal relative depth (to the maximum depth explored during regular search) of the current focus node to start diving
- MAXRELDEPTH
- the maximal relative depth (to the maximum depth explored during regular search) of the current focus node to start diving
- MAXLPITERQUOT
- maximal fraction of diving LP iterations compared to node LP iterations that this dive controller may consume
- MAXLPITEROFS
- an additional number of allowed LP iterations
- MAXDIVEUBQUOT
- maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) where diving is performed (0.0: no limit)
- MAXDIVEAVGQUOT
- maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound) where diving is performed (0.0: no limit)
- MAXDIVEUBQUOTNOSOL
- maximal UBQUOT when no solution was found yet (0.0: no limit)
- MAXDIVEAVGQUOTNOSOL
- maximal AVGQUOT when no solution was found yet (0.0: no limit)
- BACKTRACK
- use one level of backtracking if infeasibility is encountered?
- LPRESOLVEDOMCHGQUOT
- parameter to control LP resolve dynamically based on this percentage of observed bound changes relative to all variables or the LP branching candidates (integer variables with fractional solution values) from the last node where an LP has been solved. This property has no effect when the LPSOLVEFREQ is set to 1.
- LPSOLVEFREQ
- LP solve frequency for diveset, use a positive integer k to solve an LP at every k'th depth of the diving search (ie. 1 causes the diveset to solve
*all*intermediate LPs) or 0 to only resolve the LP relaxation after propagation found at least a certain percentage domain changes, see also the previous LPRESOLVEDOMCHGQUOT parameter.
- ONLYLPBRANCHCANDS
- Set this property to TRUE if only LP branching candidates be considered for the execution of the diving algorithm instead of the slower but more general constraint handler diving variable selection.
- DIVETYPES
- bit mask that represents all supported dive types. Irrelevant if only LP branching candidates should be scored, otherwise, different constraint handlers may ask the diveset if it supports their preferred divetype. See type_heur.h for a list of available dive types.
## Fundamental callbacks of a divesetOnly one callback is necessary to complete a diveset to guide the diving search performed: ## DIVESETGETSCOREThe scoring callback expects a candidate variable and calculates a score value and a preferred direction. The selected variable for diving will be one that ## Further informationThis is all there is to extend the SCIP set of diving heuristics by a new one. For further information, please see diveset related methods in type_heur.h, pub_heur.h, pub_dive.h, and heur_guideddiving.h or other diving heuristics that implement diving through a diveset. |