Scippy

SCIP

Solving Constraint Integer Programs

cons_stp.h File Reference

Detailed Description

Constraint handler for Steiner problems.

Author
Gerald Gamrath
Daniel Rehfeldt
Michael Winkler

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.

#include "scip/scip.h"
#include "grph.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()

◆ SCIPcreateConsStp()

SCIP_RETCODE SCIPcreateConsStp ( SCIP scip,
SCIP_CONS **  cons,
const char *  name,
GRAPH graph 
)

creates and captures a stp constraint

Parameters
scipSCIP data structure
conspointer to hold the created constraint
namename of constraint
graphgraph 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()

void SCIPStpConshdlrSetGraph ( SCIP scip,
const GRAPH g 
)

sets graph

Parameters
scipSCIP data structure
ggraph 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
scipSCIP data structure
ggraph data structure
redcostarray to store reduced costs or NULL
nodearrrealreal vertices array for internal computations or NULL
objvalpointer to store objective value
addcutsshould dual ascent add Steiner cuts?
ascendandpruneshould the ascent-and-prune heuristic be executed?
gnodearrtermsgnode terminals array for internal computations or NULL
resultsolution array (solution needs to be provided)
edgearrintint edges array for internal computations or NULL
nodearrintint vertices array for internal computations or NULL
rootthe root
is_pseudorootis the root a pseudo root?
damaxdeviationnumber of dual ascent runs
nodearrcharchar 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
scipSCIP data structure
ggraph data structure
redcostarray to store reduced costs or NULL
objvalpointer to store objective value
addcutsshould dual-ascent add Steiner cuts?
ascendandpruneperform ascend-and-prune and add solution?
nrunsnumber 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().