Defines all the functionality needed to find a heuristic solution to the Bayesian network problem. More...
#include <string.h>#include "heur_sinks.h"#include "scip/scip.h"#include "pedigrees.h"#include "parent_set_data.h"#include "metadata.h"#include "utils.h"#include "scip/pub_var.h"
Macros | |
| #define | DEFAULT_ASSUMENOPOSOBJ TRUE |
| whether to assume that no problem variable has a positive objective coefficient | |
| #define | DEFAULT_MAXDIVEDEPTH 100 |
| maximum dive depth when probing | |
| #define | DEFAULT_NRUNS 1 |
| how often to run the heuristic on each LP solution | |
| #define | DEFAULT_PALIM -1 |
| only DAGS with parent sets of size at most this will be considered (-1 is unlimited) | |
| #define | DEFAULT_PROBING FALSE |
| whether to use probing | |
| #define | DEFAULT_SEED 0 |
| the seed to use for random values. More... | |
| #define | EPSILON 1e-9 |
| How much improvement a candidate parent set to add must have before we chose it. More... | |
| #define | HEUR_DESC "primal heuristic template" |
| A description of the heuristic. More... | |
| #define | HEUR_DISPCHAR 'k' |
| The character to display in the solver when the heuristic is used. More... | |
| #define | HEUR_FREQ 1 |
| The heurstic is called only in the root. | |
| #define | HEUR_FREQOFS 0 |
| The heurstic is called from the first node onwards. More... | |
| #define | HEUR_MAXDEPTH -1 |
| Set no depth limit for calling the heuristic. More... | |
| #define | HEUR_NAME "sinks" |
| The name of the heuristic. More... | |
| #define | HEUR_PRIORITY 10 |
| The calling priority of the heuristic. More... | |
| #define | HEUR_TIMING SCIP_HEURTIMING_DURINGLPLOOP | SCIP_HEURTIMING_AFTERLPNODE |
| Call the heuristic after each LP solve during the cut-and-price loop. More... | |
| #define | HEUR_USESSUBSCIP FALSE |
| The heuristic doesn't use a secondary SCIP instance. More... | |
| #define | heurCopySinks NULL |
| There is no copy method. More... | |
| #define | heurExitSinks NULL |
| There is no deinitialization method. More... | |
| #define | heurExitsolSinks NULL |
| There is no deinitialization method. More... | |
| #define | heurInitsolSinks NULL |
| There is no initialization method. More... | |
| #define | max(A, B) ((A) > (B) ? (A) : (B)) |
Functions | |
| SCIP_RETCODE | HS_includePrimal (SCIP *scip) |
| creates the sinks primal heuristic and includes it in SCIP. More... | |
| static | SCIP_DECL_HEUREXEC (heurExecSinks) |
| execution method of primal heuristic More... | |
| static | SCIP_DECL_HEURFREE (heurFreeSinks) |
| destructor of primal heuristic to free user data (called when SCIP is exiting) | |
| static | SCIP_DECL_HEURINIT (heurInitSinks) |
| initialization method of primal heuristic (called after problem was transformed) | |
Detailed Description
Defines all the functionality needed to find a heuristic solution to the Bayesian network problem.
The heurstic is based on repeatedly choosing the best parent set for a node to add to the network in a greedy manner, subject to the constraint that adding the new edges doesn't result in a cycle being formed.
Macro Definition Documentation
◆ DEFAULT_SEED
| #define DEFAULT_SEED 0 |
the seed to use for random values.
Referenced by HS_includePrimal().
◆ EPSILON
| #define EPSILON 1e-9 |
How much improvement a candidate parent set to add must have before we chose it.
Referenced by SCIP_DECL_HEUREXEC().
◆ HEUR_DESC
| #define HEUR_DESC "primal heuristic template" |
A description of the heuristic.
Referenced by HS_includePrimal().
◆ HEUR_DISPCHAR
| #define HEUR_DISPCHAR 'k' |
The character to display in the solver when the heuristic is used.
Referenced by HS_includePrimal().
◆ HEUR_FREQOFS
| #define HEUR_FREQOFS 0 |
The heurstic is called from the first node onwards.
Referenced by HS_includePrimal().
◆ HEUR_MAXDEPTH
| #define HEUR_MAXDEPTH -1 |
Set no depth limit for calling the heuristic.
Referenced by HS_includePrimal().
◆ HEUR_NAME
| #define HEUR_NAME "sinks" |
The name of the heuristic.
Referenced by HS_includePrimal(), and SCIP_DECL_HEUREXEC().
◆ HEUR_PRIORITY
| #define HEUR_PRIORITY 10 |
The calling priority of the heuristic.
Referenced by HS_includePrimal().
◆ HEUR_TIMING
| #define HEUR_TIMING SCIP_HEURTIMING_DURINGLPLOOP | SCIP_HEURTIMING_AFTERLPNODE |
Call the heuristic after each LP solve during the cut-and-price loop.
Referenced by HS_includePrimal().
◆ HEUR_USESSUBSCIP
| #define HEUR_USESSUBSCIP FALSE |
The heuristic doesn't use a secondary SCIP instance.
Referenced by HS_includePrimal().
◆ heurCopySinks
| #define heurCopySinks NULL |
There is no copy method.
Referenced by HS_includePrimal().
◆ heurExitSinks
| #define heurExitSinks NULL |
There is no deinitialization method.
Referenced by HS_includePrimal().
◆ heurExitsolSinks
| #define heurExitsolSinks NULL |
There is no deinitialization method.
Referenced by HS_includePrimal().
◆ heurInitsolSinks
| #define heurInitsolSinks NULL |
There is no initialization method.
Referenced by HS_includePrimal().
Function Documentation
◆ HS_includePrimal()
| SCIP_RETCODE HS_includePrimal | ( | SCIP * | scip | ) |
creates the sinks primal heuristic and includes it in SCIP.
- Returns
- SCIP_OKAy if the operation suceeded, or an appropriate error message otherwise.
- Parameters
-
scip SCIP data structure
References DEFAULT_ASSUMENOPOSOBJ, DEFAULT_MAXDIVEDEPTH, DEFAULT_NRUNS, DEFAULT_PALIM, DEFAULT_PROBING, DEFAULT_SEED, HEUR_DESC, HEUR_DISPCHAR, HEUR_FREQ, HEUR_FREQOFS, HEUR_MAXDEPTH, HEUR_NAME, HEUR_PRIORITY, HEUR_TIMING, HEUR_USESSUBSCIP, heurCopySinks, heurExitSinks, heurExitsolSinks, and heurInitsolSinks.
Referenced by BN_includePlugins().
◆ SCIP_DECL_HEUREXEC()
|
static |
execution method of primal heuristic
parent set data (or NULL if not set)
needed for storing the LP solution asking for values from NULL using SCIPgetSolVals (at the wrong point) will render the pseudo-solution
incumbent solution (NULL if none found so far )
objective value of incumbent solution
running value of solution under construction
bestparents[j] is the index for the best ( highest scoring ) remaining parentset for node j
not_sinks[i] is the ith remaining non-sink
sink[i] = TRUE if i has been chosen as a sink
loss_lb[j] is a lower bound on the 'local' loss incurred by chosing a parent set for variable j
indexes not_sinks array
indexes a BN vertex
indexes parent sets
indexes parents in a parent set
number of sinks remaining to be found
TRUE is a feasible solution good enough to keep is constructed
solution being constructed (if not probing)
best solution so far (over multiple runs)
objective value of best solution so far (over multiple runs)
heuristic data
TRUE if a vertex rejected as a sink because it is the parent of a vertex which is not yet a sink
number of family variables fixed to 1
child vertices of family variables fixed to 1
indices of parent sets of family variables fixed to 1
an element of fixedc
an element of fixedp
best vertex (so far) to choose as next sink
best family variable (so far) to set to 1 since child is best vertex to choose as next sink
loss associated with choosing bestvariable as next sink
index of bestvariable in not_sinks array
a family variable
loss associated with choosing a vertex 'j' as the next sink
improvement in loss if currently considered vertex were chosen as next sink rather than current best sink
whether the current best parent set of vertex 'j' are allowed, now that a new sink has been chosen
if probing, records whether probing node can be cutoff
if probing, stores pseudo branching candidates
if probing, stores number of pseudo branching candidates
if probing, first pseudo branching candidate variable
if probing, records depth of dive
current run of the heuristic
a parent to check not to already be a sink
References EPSILON, get_arrowedge(), HEUR_NAME, is_dr_feasible(), MD_getParentSetData(), ParentSetData::n, ParentSetData::nodeNames, ParentSetData::nParents, ParentSetData::nParentSets, ParentSetData::ParentSets, and ParentSetData::PaVars.
