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.h.
Go to the source code of this file.
Functions | |
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) |
Function Documentation
◆ SCIPincludeConshdlrStp()
SCIP_RETCODE SCIPincludeConshdlrStp | ( | SCIP * | scip | ) |
creates the handler for element constraints and includes it in 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 (solution needs to be provided) 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 number of dual ascent runs nodearrchar char 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 the PCSPG and the MWCSP
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().