Detailed Description
Constraint handler for Steiner problems.
This file checks solutions for feasibility and separates violated model constraints. For more details see Separating violated constraints page.
Definition in file cons_stp.c.
#include <assert.h>
#include <string.h>
#include "cons_stp.h"
#include "probdata_stp.h"
#include "grph.h"
#include "heur_prune.h"
#include "heur_ascendprune.h"
#include "portab.h"
#include "branch_stp.h"
#include "scip/scip.h"
#include "scip/misc.h"
#include "scip/cons_linear.h"
#include <time.h>
Go to the source code of this file.
Functions | |
Local methods | |
static SCIP_Bool | is_active (const int *active, int realtail, int dfsbase) |
static SCIP_RETCODE | cut_add (SCIP *scip, SCIP_CONSHDLR *conshdlr, const GRAPH *g, const SCIP_Real *xval, int *capa, const int updatecapa, int *ncuts, SCIP_Bool local, SCIP_Bool *success) |
static int | graph_next_term (const GRAPH *g, int terms, int *term, const int *w, const SCIP_Bool firstrun) |
static void | set_capacity (const GRAPH *g, const SCIP_Bool creep_flow, const int flip, int *capa, const SCIP_Real *xval) |
static SCIP_RETCODE | sep_flow (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_CONSDATA *consdata, int maxcuts, int *ncuts) |
static SCIP_RETCODE | sep_2cut (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_CONSDATA *consdata, const int *termorg, int maxcuts, int *ncuts) |
static SCIP_RETCODE | dualascent_init (SCIP *scip, const GRAPH *g, const int *RESTRICT start, const int *RESTRICT edgearr, int root, SCIP_Bool is_pseudoroot, int ncsredges, int *gmark, int *RESTRICT active, SCIP_PQUEUE *pqueue, GNODE **gnodearr, SCIP_Real *RESTRICT rescap, SCIP_Real *dualobj, int *augmentingcomponent) |
Callback methods | |
static | SCIP_DECL_CONSHDLRCOPY (conshdlrCopyStp) |
static | SCIP_DECL_CONSFREE (consFreeStp) |
static | SCIP_DECL_CONSINITSOL (consInitsolStp) |
static | SCIP_DECL_CONSDELETE (consDeleteStp) |
static | SCIP_DECL_CONSTRANS (consTransStp) |
static | SCIP_DECL_CONSINITLP (consInitlpStp) |
static | SCIP_DECL_CONSSEPALP (consSepalpStp) |
static | SCIP_DECL_CONSENFOLP (consEnfolpStp) |
static | SCIP_DECL_CONSENFOPS (consEnfopsStp) |
static | SCIP_DECL_CONSCHECK (consCheckStp) |
static | SCIP_DECL_CONSPROP (consPropStp) |
static | SCIP_DECL_CONSLOCK (consLockStp) |
static | SCIP_DECL_CONSCOPY (consCopyStp) |
Interface methods | |
SCIP_RETCODE | SCIPincludeConshdlrStp (SCIP *scip) |
SCIP_RETCODE | SCIPcreateConsStp (SCIP *scip, SCIP_CONS **cons, const char *name, GRAPH *graph) |
void | SCIPStpConshdlrSetGraph (SCIP *scip, const GRAPH *g) |
SCIP_RETCODE | SCIPStpDualAscent (SCIP *scip, const GRAPH *g, SCIP_Real *RESTRICT redcost, SCIP_Real *RESTRICT nodearrreal, SCIP_Real *objval, SCIP_Bool addcuts, SCIP_Bool ascendandprune, GNODE **gnodearrterms, const int *result, int *RESTRICT edgearrint, int *RESTRICT nodearrint, int root, SCIP_Bool is_pseudoroot, SCIP_Real damaxdeviation, STP_Bool *RESTRICT nodearrchar) |
SCIP_RETCODE | SCIPStpDualAscentPcMw (SCIP *scip, GRAPH *g, SCIP_Real *redcost, SCIP_Real *objval, SCIP_Bool addcuts, SCIP_Bool ascendandprune, int nruns) |
Macro Definition Documentation
◆ ADDCUTSTOPOOL
#define ADDCUTSTOPOOL 0 |
Definition at line 61 of file cons_stp.c.
◆ Q_NULL
#define Q_NULL -1 /* NULL element of queue/list */ |
Definition at line 63 of file cons_stp.c.
Referenced by sep_2cut().
◆ CONSHDLR_NAME
#define CONSHDLR_NAME "stp" |
Definition at line 70 of file cons_stp.c.
Referenced by SCIP_DECL_CONSDELETE(), SCIP_DECL_CONSFREE(), SCIP_DECL_CONSHDLRCOPY(), SCIP_DECL_CONSTRANS(), SCIPcreateConsStp(), and SCIPincludeConshdlrStp().
◆ CONSHDLR_DESC
#define CONSHDLR_DESC "steiner tree constraint handler" |
Definition at line 71 of file cons_stp.c.
Referenced by SCIPincludeConshdlrStp().
◆ CONSHDLR_SEPAPRIORITY
#define CONSHDLR_SEPAPRIORITY 0 |
priority of the constraint handler for separation
Definition at line 72 of file cons_stp.c.
Referenced by SCIPincludeConshdlrStp().
◆ CONSHDLR_ENFOPRIORITY
#define CONSHDLR_ENFOPRIORITY 0 |
priority of the constraint handler for constraint enforcing
Definition at line 73 of file cons_stp.c.
Referenced by SCIPincludeConshdlrStp().
◆ CONSHDLR_CHECKPRIORITY
#define CONSHDLR_CHECKPRIORITY 9999999 |
priority of the constraint handler for checking feasibility
Definition at line 74 of file cons_stp.c.
Referenced by SCIPincludeConshdlrStp().
◆ CONSHDLR_SEPAFREQ
#define CONSHDLR_SEPAFREQ 1 |
frequency for separating cuts; zero means to separate only in the root node
Definition at line 75 of file cons_stp.c.
Referenced by SCIPincludeConshdlrStp().
◆ CONSHDLR_PROPFREQ
#define CONSHDLR_PROPFREQ 0 |
frequency for propagating domains; zero means only preprocessing propagation
Definition at line 76 of file cons_stp.c.
Referenced by SCIPincludeConshdlrStp().
◆ CONSHDLR_EAGERFREQ
#define CONSHDLR_EAGERFREQ 1 |
frequency for using all instead of only the useful constraints in separation, propagation and enforcement, -1 for no eager evaluations, 0 for first only
Definition at line 77 of file cons_stp.c.
Referenced by SCIPincludeConshdlrStp().
◆ CONSHDLR_DELAYSEPA
#define CONSHDLR_DELAYSEPA FALSE |
should separation method be delayed, if other separators found cuts?
Definition at line 80 of file cons_stp.c.
Referenced by SCIPincludeConshdlrStp().
◆ CONSHDLR_DELAYPROP
#define CONSHDLR_DELAYPROP FALSE |
should propagation method be delayed, if other propagators found reductions?
Definition at line 81 of file cons_stp.c.
Referenced by SCIPincludeConshdlrStp().
◆ CONSHDLR_NEEDSCONS
#define CONSHDLR_NEEDSCONS TRUE |
should the constraint handler be skipped, if no constraints are available?
Definition at line 82 of file cons_stp.c.
Referenced by SCIPincludeConshdlrStp().
◆ DEFAULT_MAXROUNDS
#define DEFAULT_MAXROUNDS 10 |
maximal number of separation rounds per node (-1: unlimited)
Definition at line 84 of file cons_stp.c.
Referenced by SCIPincludeConshdlrStp().
◆ DEFAULT_MAXROUNDSROOT
#define DEFAULT_MAXROUNDSROOT -1 |
maximal number of separation rounds in the root node (-1: unlimited)
Definition at line 85 of file cons_stp.c.
Referenced by SCIPincludeConshdlrStp().
◆ DEFAULT_MAXSEPACUTS
#define DEFAULT_MAXSEPACUTS INT_MAX |
maximal number of cuts separated per separation round
Definition at line 86 of file cons_stp.c.
Referenced by SCIPincludeConshdlrStp().
◆ DEFAULT_MAXSEPACUTSROOT
#define DEFAULT_MAXSEPACUTSROOT INT_MAX |
maximal number of cuts separated per separation round in the root node
Definition at line 87 of file cons_stp.c.
Referenced by SCIPincludeConshdlrStp().
◆ CONSHDLR_PROP_TIMING
#define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP |
Definition at line 90 of file cons_stp.c.
Referenced by SCIPincludeConshdlrStp().
◆ DEFAULT_BACKCUT
#define DEFAULT_BACKCUT FALSE |
Try Back-Cuts FALSE
Definition at line 92 of file cons_stp.c.
Referenced by SCIPincludeConshdlrStp().
◆ DEFAULT_CREEPFLOW
#define DEFAULT_CREEPFLOW TRUE |
◆ DEFAULT_DISJUNCTCUT
#define DEFAULT_DISJUNCTCUT FALSE |
Only disjunct Cuts FALSE
Definition at line 94 of file cons_stp.c.
Referenced by SCIPincludeConshdlrStp().
◆ DEFAULT_NESTEDCUT
#define DEFAULT_NESTEDCUT FALSE |
Try Nested-Cuts FALSE
Definition at line 95 of file cons_stp.c.
Referenced by SCIPincludeConshdlrStp().
◆ DEFAULT_FLOWSEP
#define DEFAULT_FLOWSEP TRUE |
◆ DEFAULT_DAMAXDEVIATION
#define DEFAULT_DAMAXDEVIATION 0.25 |
max deviation for dual ascent
Definition at line 98 of file cons_stp.c.
Referenced by SCIPStpDualAscent(), and SCIPStpDualAscentPcMw().
◆ DA_MAXDEVIATION_LOWER
#define DA_MAXDEVIATION_LOWER 0.01 |
lower bound for max deviation for dual ascent
Definition at line 99 of file cons_stp.c.
Referenced by SCIPStpDualAscent().
◆ DA_MAXDEVIATION_UPPER
#define DA_MAXDEVIATION_UPPER 0.9 |
upper bound for max deviation for dual ascent
Definition at line 100 of file cons_stp.c.
Referenced by SCIPStpDualAscent().
◆ DA_EPS
#define DA_EPS (5.0 * 1e-7) |
Definition at line 101 of file cons_stp.c.
Referenced by SCIPStpDualAscent().
◆ FLOW_FACTOR
#define FLOW_FACTOR 1000000 |
Definition at line 108 of file cons_stp.c.
Referenced by cut_add(), sep_2cut(), and set_capacity().
◆ CREEP_VALUE
#define CREEP_VALUE 10 |
Definition at line 109 of file cons_stp.c.
Referenced by sep_2cut(), and set_capacity().
◆ DFS
#define DFS |
Definition at line 112 of file cons_stp.c.
Function Documentation
◆ is_active()
|
static |
returns whether node realtail is active or leads to active node other than dfsbase
- Parameters
-
active active nodes array realtail vertex to start from dfsbase DFS source vertex
Definition at line 157 of file cons_stp.c.
References active, and cut_add().
Referenced by SCIPStpDualAscent().
◆ cut_add()
|
static |
add a cut
- Parameters
-
scip SCIP data structure conshdlr constraint handler g graph data structure xval edge values capa edges capacities (scaled) updatecapa update capacities? ncuts pointer to store number of cuts local is the cut local? success pointer to store whether add cut be added
Definition at line 177 of file cons_stp.c.
References GRAPH::edges, FALSE, FLOW_FACTOR, graph_next_term(), GRAPH::head, GRAPH::knots, GRAPH::mark, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddPoolCut(), SCIPaddRow(), SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPcreateEmptyRowConshdlr(), SCIPdebug, SCIPdebugMessage, SCIPflushRowExtensions(), SCIPinfinity(), SCIPisCutEfficacious(), SCIPisFeasGE(), SCIPprintRow(), SCIPprobdataGetVars(), SCIPreleaseRow(), GRAPH::source, GRAPH::tail, and TRUE.
Referenced by is_active(), and sep_2cut().
◆ graph_next_term()
|
static |
- Parameters
-
g graph data structure terms number of terminals term terminal array w awake level firstrun first run?
Definition at line 277 of file cons_stp.c.
References GRAPH::knots, GRAPH::mincut_dist, NULL, set_capacity(), and w.
Referenced by cut_add(), and sep_2cut().
◆ set_capacity()
|
static |
- Parameters
-
g graph data structure creep_flow creep flow? flip reverse the flow? capa edges capacities (scaled) xval edge values
Definition at line 349 of file cons_stp.c.
References CREEP_VALUE, GRAPH::edges, FLOW_FACTOR, NULL, and sep_flow().
Referenced by graph_next_term(), and sep_2cut().
◆ sep_flow()
|
static |
separate
- Parameters
-
scip SCIP data structure conshdlr constraint handler conshdlrdata constraint handler data consdata constraint data maxcuts maximal number of cuts ncuts pointer to store number of cuts
Definition at line 392 of file cons_stp.c.
References EAT_LAST, GRAPH::edges, FALSE, GRAPH::ieat, GRAPH::inpbeg, GRAPH::knots, GRAPH::layers, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddPoolCut(), SCIPaddRow(), SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPcreateEmptyRowConshdlr(), SCIPdebugMessage, SCIPflushRowExtensions(), SCIPinfinity(), SCIPisFeasEQ(), SCIPisFeasGT(), SCIPisFeasNegative(), SCIPprobdataGetVars(), SCIPprobdataGetXval(), SCIPreleaseRow(), sep_2cut(), GRAPH::source, GRAPH::term, GRAPH::terms, and TRUE.
Referenced by SCIP_DECL_CONSSEPALP(), and set_capacity().
◆ sep_2cut()
|
static |
separate 2-cuts
- Parameters
-
scip SCIP data structure conshdlr constraint handler conshdlrdata constraint handler data consdata constraint data termorg original terminals or NULL maxcuts maximal number of cuts ncuts pointer to store number of cuts
Definition at line 649 of file cons_stp.c.
References CREEP_VALUE, cut_add(), dualascent_init(), EAT_LAST, GRAPH::edges, FALSE, flipedge, FLOW_FACTOR, graph_mincut_exec(), graph_next_term(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::mark, GRAPH::mincut_e, GRAPH::mincut_head, GRAPH::mincut_head_inact, GRAPH::mincut_numb, GRAPH::mincut_r, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, Q_NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPgetDepth(), SCIPisFeasGE(), SCIPisFeasLT(), SCIPisStopped(), SCIPprobdataGetVars(), SCIPprobdataGetXval(), SCIPvarGetUbLocal(), set_capacity(), GRAPH::source, GRAPH::term, GRAPH::terms, TRUE, and w.
Referenced by SCIP_DECL_CONSSEPALP(), and sep_flow().
◆ dualascent_init()
|
static |
- Parameters
-
scip SCIP g graph data structure start CSR start array [0,...,nnodes] edgearr CSR ancestor edge array root the root is_pseudoroot is the root a pseudo root? ncsredges number of CSR edges gmark array for marking nodes active active vertices mark pqueue priority queue gnodearr array containing terminal nodes rescap residual capacity dualobj dual objective augmentingcomponent augmenting component
Definition at line 1081 of file cons_stp.c.
References a, active, GRAPH::cost, Graph_Node::dist, EAT_LAST, FALSE, GRAPH::grad, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, nnodes, Graph_Node::number, SCIP_Bool, SCIP_CALL, SCIP_DECL_CONSHDLRCOPY(), SCIP_OKAY, SCIP_Real, SCIPpqueueInsert(), GRAPH::tail, GRAPH::term, and TRUE.
Referenced by SCIPStpDualAscent(), and sep_2cut().
◆ SCIP_DECL_CONSHDLRCOPY()
|
static |
copy method for constraint handler plugins (called when SCIP copies plugins)
Definition at line 1208 of file cons_stp.c.
References CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_DECL_CONSFREE(), SCIP_OKAY, SCIPconshdlrGetName(), SCIPincludeConshdlrStp(), and TRUE.
Referenced by dualascent_init().
◆ SCIP_DECL_CONSFREE()
|
static |
destructor of constraint handler to free constraint handler data (called when SCIP is exiting)
Definition at line 1224 of file cons_stp.c.
References CONSHDLR_NAME, NULL, SCIP_DECL_CONSINITSOL(), SCIP_OKAY, SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPconshdlrSetData(), and SCIPfreeMemory.
Referenced by SCIP_DECL_CONSHDLRCOPY().
◆ SCIP_DECL_CONSINITSOL()
|
static |
solving process initialization method of constraint handler (called when branch and bound process is about to begin)
Definition at line 1245 of file cons_stp.c.
References SCIP_DECL_CONSDELETE(), SCIP_OKAY, SCIPprobdataGetGraph2(), and SCIPStpConshdlrSetGraph().
Referenced by SCIP_DECL_CONSFREE().
◆ SCIP_DECL_CONSDELETE()
|
static |
frees specific constraint data
Definition at line 1255 of file cons_stp.c.
References CONSHDLR_NAME, NULL, SCIP_DECL_CONSTRANS(), SCIP_OKAY, SCIPconshdlrGetName(), and SCIPfreeBlockMemory.
Referenced by SCIP_DECL_CONSINITSOL().
◆ SCIP_DECL_CONSTRANS()
|
static |
transforms constraint data into data belonging to the transformed problem
Definition at line 1269 of file cons_stp.c.
References CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_DECL_CONSINITLP(), SCIP_OKAY, SCIP_STAGE_TRANSFORMING, SCIPallocBlockMemory, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPcreateCons(), and SCIPgetStage().
Referenced by SCIP_DECL_CONSDELETE().
◆ SCIP_DECL_CONSINITLP()
|
static |
LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved)
Definition at line 1301 of file cons_stp.c.
References NULL, SCIP_CALL, SCIP_DECL_CONSSEPALP(), SCIP_OKAY, SCIP_Real, SCIPgetProbData(), SCIPprobdataGetGraph(), and TRUE.
Referenced by SCIP_DECL_CONSTRANS().
◆ SCIP_DECL_CONSSEPALP()
|
static |
separation method of constraint handler for LP solutions
Definition at line 1323 of file cons_stp.c.
References BMScopyMemoryArray, BRANCH_STP_VERTEX_TERM, graph_knot_chg(), Is_term, GRAPH::knots, nnodes, nterms, NULL, SCIP_Bool, SCIP_CALL, SCIP_DECL_CONSENFOLP(), SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_SEPARATED, SCIPallocBufferArray, SCIPconsGetData(), SCIPconshdlrGetData(), SCIPfreeBufferArrayNull, SCIPgetCurrentNode(), SCIPnodeGetDepth(), SCIPStpBranchruleApplyVertexChgs(), SCIPStpBranchruleInitNodeState(), sep_2cut(), sep_flow(), STP_SPG, GRAPH::stp_type, GRAPH::term, and GRAPH::terms.
Referenced by SCIP_DECL_CONSINITLP().
◆ SCIP_DECL_CONSENFOLP()
|
static |
constraint enforcing method of constraint handler for LP solutions
Definition at line 1401 of file cons_stp.c.
References NULL, SCIP_Bool, SCIP_CALL, SCIP_DECL_CONSENFOPS(), SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIPconsGetData(), SCIPprobdataGetXval(), and SCIPStpValidateSol().
Referenced by SCIP_DECL_CONSSEPALP().
◆ SCIP_DECL_CONSENFOPS()
|
static |
constraint enforcing method of constraint handler for pseudo solutions
Definition at line 1426 of file cons_stp.c.
References NULL, SCIP_Bool, SCIP_CALL, SCIP_DECL_CONSCHECK(), SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIPconsGetData(), SCIPprobdataGetXval(), and SCIPStpValidateSol().
Referenced by SCIP_DECL_CONSENFOLP().
◆ SCIP_DECL_CONSCHECK()
|
static |
feasibility check method of constraint handler for integral solutions
Definition at line 1451 of file cons_stp.c.
References NULL, SCIP_Bool, SCIP_CALL, SCIP_DECL_CONSPROP(), SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIPprobdataGetGraph2(), SCIPprobdataGetXval(), and SCIPStpValidateSol().
Referenced by SCIP_DECL_CONSENFOPS().
◆ SCIP_DECL_CONSPROP()
|
static |
domain propagation method of constraint handler
Definition at line 1473 of file cons_stp.c.
References Is_term, GRAPH::knots, MAX, GRAPH::maxdeg, nnodes, NULL, SCIP_CUTOFF, SCIP_DECL_CONSLOCK(), SCIP_DIDNOTFIND, SCIP_OKAY, SCIPgetProbData(), SCIPprobdataGetGraph(), STP_DCSTP, GRAPH::stp_type, and GRAPH::term.
Referenced by SCIP_DECL_CONSCHECK().
◆ SCIP_DECL_CONSLOCK()
|
static |
variable rounding lock method of constraint handler
Definition at line 1522 of file cons_stp.c.
References NULL, SCIP_CALL, SCIP_DECL_CONSCOPY(), SCIP_OKAY, SCIPaddVarLocksType(), SCIPprobdataGetNVars(), and SCIPprobdataGetVars().
Referenced by SCIP_DECL_CONSPROP().
◆ SCIP_DECL_CONSCOPY()
|
static |
constraint copying method of constraint handler
Definition at line 1544 of file cons_stp.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetName(), SCIPcreateConsStp(), SCIPgetProbData(), SCIPincludeConshdlrStp(), SCIPprobdataGetGraph(), and TRUE.
Referenced by SCIP_DECL_CONSLOCK().
◆ SCIPincludeConshdlrStp()
SCIP_RETCODE SCIPincludeConshdlrStp | ( | SCIP * | scip | ) |
creates the handler for stp constraints and includes it in SCIP
- Parameters
-
scip SCIP data structure
Definition at line 1575 of file cons_stp.c.
References CONSHDLR_CHECKPRIORITY, CONSHDLR_DELAYPROP, CONSHDLR_DELAYSEPA, CONSHDLR_DESC, CONSHDLR_EAGERFREQ, CONSHDLR_ENFOPRIORITY, CONSHDLR_NAME, CONSHDLR_NEEDSCONS, CONSHDLR_PROP_TIMING, CONSHDLR_PROPFREQ, CONSHDLR_SEPAFREQ, CONSHDLR_SEPAPRIORITY, DEFAULT_BACKCUT, DEFAULT_CREEPFLOW, DEFAULT_DISJUNCTCUT, DEFAULT_FLOWSEP, DEFAULT_MAXROUNDS, DEFAULT_MAXROUNDSROOT, DEFAULT_MAXSEPACUTS, DEFAULT_MAXSEPACUTSROOT, DEFAULT_NESTEDCUT, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPaddBoolParam(), SCIPaddIntParam(), SCIPallocMemory, SCIPcreateConsStp(), SCIPincludeConshdlrBasic(), SCIPsetConshdlrCopy(), SCIPsetConshdlrDelete(), SCIPsetConshdlrFree(), SCIPsetConshdlrInitlp(), SCIPsetConshdlrInitsol(), SCIPsetConshdlrProp(), SCIPsetConshdlrSepa(), SCIPsetConshdlrTrans(), and TRUE.
Referenced by runShell(), SCIP_DECL_CONSCOPY(), and SCIP_DECL_CONSHDLRCOPY().
◆ SCIPcreateConsStp()
SCIP_RETCODE SCIPcreateConsStp | ( | SCIP * | scip, |
SCIP_CONS ** | cons, | ||
const char * | name, | ||
GRAPH * | graph | ||
) |
creates and captures a stp constraint
- Parameters
-
scip SCIP data structure cons pointer to hold the created constraint name name of constraint graph graph data structure
Definition at line 1636 of file cons_stp.c.
References CONSHDLR_NAME, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_PLUGINNOTFOUND, SCIPallocBlockMemory, SCIPcreateCons(), SCIPerrorMessage, SCIPfindConshdlr(), SCIPStpConshdlrSetGraph(), and TRUE.
Referenced by SCIP_DECL_CONSCOPY(), SCIPincludeConshdlrStp(), and SCIPprobdataCreate().
◆ SCIPStpConshdlrSetGraph()
sets graph
- Parameters
-
scip SCIP data structure g graph data structure
Definition at line 1666 of file cons_stp.c.
References NULL, SCIPconsGetData(), SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPfindConshdlr(), SCIPprobdataGetGraph2(), and SCIPStpDualAscent().
Referenced by SCIP_DECL_CONSINITSOL(), and SCIPcreateConsStp().
◆ SCIPStpDualAscent()
SCIP_RETCODE SCIPStpDualAscent | ( | SCIP * | scip, |
const GRAPH * | g, | ||
SCIP_Real *RESTRICT | redcost, | ||
SCIP_Real *RESTRICT | nodearrreal, | ||
SCIP_Real * | objval, | ||
SCIP_Bool | addcuts, | ||
SCIP_Bool | ascendandprune, | ||
GNODE ** | gnodearrterms, | ||
const int * | result, | ||
int *RESTRICT | edgearrint, | ||
int *RESTRICT | nodearrint, | ||
int | root, | ||
SCIP_Bool | is_pseudoroot, | ||
SCIP_Real | damaxdeviation, | ||
STP_Bool *RESTRICT | nodearrchar | ||
) |
dual ascent heuristic
- Parameters
-
scip SCIP data structure g graph data structure redcost array to store reduced costs or NULL nodearrreal real vertices array for internal computations or NULL objval pointer to store objective value addcuts should dual ascent add Steiner cuts? ascendandprune should the ascent-and-prune heuristic be executed? gnodearrterms gnode terminals array for internal computations or NULL result solution array or NULL edgearrint int edges array for internal computations or NULL nodearrint int vertices array for internal computations or NULL root the root is_pseudoroot is the root a pseudo root? damaxdeviation maximum deviation for dual-ascent ( -1.0 for default) nodearrchar STP_Bool vertices array for internal computations or NULL
Definition at line 1687 of file cons_stp.c.
References a, active, CONNECT, GRAPH::cost, DA_EPS, DA_MAXDEVIATION_LOWER, DA_MAXDEVIATION_UPPER, DEFAULT_DAMAXDEVIATION, Graph_Node::dist, dualascent_init(), GRAPH::edges, FALSE, FARAWAY, GNODECmpByDist(), GRAPH::grad, graph_get_csr(), is_active(), Is_term, GRAPH::knots, nnodes, nterms, NULL, Graph_Node::number, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_STAGE_INITSOLVE, SCIPaddCoefLinear(), SCIPaddCons(), SCIPaddRow(), SCIPaddVarToRow(), SCIPallocBlockMemory, SCIPallocBufferArray, SCIPallocMemoryArray, SCIPcacheRowExtensions(), SCIPcreateConsLinear(), SCIPcreateEmptyRowConshdlr(), SCIPdebugMessage, SCIPfindConshdlr(), SCIPflushRowExtensions(), SCIPfreeBlockMemory, SCIPfreeBufferArray, SCIPfreeMemoryArray, SCIPgetStage(), SCIPinfinity(), SCIPisGE(), SCIPisLT(), SCIPisStopped(), SCIPisZero(), SCIPpqueueCreate(), SCIPpqueueFirst(), SCIPpqueueFree(), SCIPpqueueInsert(), SCIPpqueueNElems(), SCIPpqueueRemove(), SCIPprobdataGetVars(), SCIPreleaseCons(), SCIPreleaseRow(), SCIPStpDualAscentPcMw(), SCIPStpHeurAscendPruneRun(), GRAPH::source, GRAPH::tail, GRAPH::term, GRAPH::terms, and TRUE.
Referenced by computePertubedSol(), reduce_da(), reduce_daPcMw(), reduce_daSlackPrune(), reduce_daSlackPruneMw(), SCIPprobdataCreate(), and SCIPStpConshdlrSetGraph().
◆ SCIPStpDualAscentPcMw()
SCIP_RETCODE SCIPStpDualAscentPcMw | ( | SCIP * | scip, |
GRAPH * | g, | ||
SCIP_Real * | redcost, | ||
SCIP_Real * | objval, | ||
SCIP_Bool | addcuts, | ||
SCIP_Bool | ascendandprune, | ||
int | nruns | ||
) |
dual ascent heuristic for PCSPG and MWCSP
- Parameters
-
scip SCIP data structure g graph data structure redcost array to store reduced costs or NULL objval pointer to store objective value addcuts should dual-ascent add Steiner cuts? ascendandprune perform ascend-and-prune and add solution? nruns number of dual ascent runs
Definition at line 2268 of file cons_stp.c.
References a, active, GRAPH::cost, DEFAULT_DAMAXDEVIATION, Graph_Node::dist, EAT_LAST, GRAPH::edges, FALSE, FARAWAY, GNODECmpByDist(), GRAPH::grad, graph_free(), graph_pc_getSap(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::mark, nnodes, nterms, NULL, Graph_Node::number, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_STAGE_INITSOLVE, SCIPaddCoefLinear(), SCIPaddCons(), SCIPaddRow(), SCIPaddVarToRow(), SCIPallocBuffer, SCIPallocBufferArray, SCIPcacheRowExtensions(), SCIPcreateConsLinear(), SCIPcreateEmptyRowConshdlr(), SCIPdebugMessage, SCIPfindConshdlr(), SCIPflushRowExtensions(), SCIPfreeBuffer, SCIPfreeBufferArray, SCIPgetStage(), SCIPinfinity(), SCIPisEQ(), SCIPisGE(), SCIPisLE(), SCIPisLT(), SCIPisStopped(), SCIPisZero(), SCIPpqueueCreate(), SCIPpqueueFree(), SCIPpqueueInsert(), SCIPpqueueNElems(), SCIPpqueueRemove(), SCIPprobdataGetOffset(), SCIPprobdataGetVars(), SCIPreleaseCons(), SCIPreleaseRow(), SCIPStpHeurAscendPruneRun(), GRAPH::source, GRAPH::tail, GRAPH::term, GRAPH::terms, and TRUE.
Referenced by SCIPprobdataCreate(), and SCIPStpDualAscent().