Scippy

SCIP

Solving Constraint Integer Programs

cons_stp.c 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.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.

Macros

#define ADDCUTSTOPOOL   0
 
#define Q_NULL   -1 /* NULL element of queue/list */
 
Constraint handler properties
#define CONSHDLR_NAME   "stp"
 
#define CONSHDLR_DESC   "steiner tree constraint handler"
 
#define CONSHDLR_SEPAPRIORITY   0
 
#define CONSHDLR_ENFOPRIORITY   0
 
#define CONSHDLR_CHECKPRIORITY   9999999
 
#define CONSHDLR_SEPAFREQ   1
 
#define CONSHDLR_PROPFREQ   0
 
#define CONSHDLR_EAGERFREQ   1
 
#define CONSHDLR_DELAYSEPA   FALSE
 
#define CONSHDLR_DELAYPROP   FALSE
 
#define CONSHDLR_NEEDSCONS   TRUE
 
#define DEFAULT_MAXROUNDS   10
 
#define DEFAULT_MAXROUNDSROOT   -1
 
#define DEFAULT_MAXSEPACUTS   INT_MAX
 
#define DEFAULT_MAXSEPACUTSROOT   INT_MAX
 
#define CONSHDLR_PROP_TIMING   SCIP_PROPTIMING_BEFORELP
 
#define DEFAULT_BACKCUT   FALSE
 
#define DEFAULT_CREEPFLOW   TRUE
 
#define DEFAULT_DISJUNCTCUT   FALSE
 
#define DEFAULT_NESTEDCUT   FALSE
 
#define DEFAULT_FLOWSEP   TRUE
 
#define DEFAULT_DAMAXDEVIATION   0.25
 
#define DA_MAXDEVIATION_LOWER   0.01
 
#define DA_MAXDEVIATION_UPPER   0.9
 
#define DA_EPS   (5.0 * 1e-7)
 
#define FLOW_FACTOR   1000000
 
#define CREEP_VALUE   10
 
#define DFS
 

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

◆ 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

Use Creep-Flow

Definition at line 93 of file cons_stp.c.

Referenced by SCIPincludeConshdlrStp().

◆ 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

Try Flow-Cuts

Definition at line 96 of file cons_stp.c.

Referenced by SCIPincludeConshdlrStp().

◆ 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 SCIP_Bool is_active ( const int *  active,
int  realtail,
int  dfsbase 
)
static

returns whether node realtail is active or leads to active node other than dfsbase

Parameters
activeactive nodes array
realtailvertex to start from
dfsbaseDFS source vertex

Definition at line 157 of file cons_stp.c.

References active, and cut_add().

Referenced by SCIPStpDualAscent().

◆ cut_add()

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

add a cut

Parameters
scipSCIP data structure
conshdlrconstraint handler
ggraph data structure
xvaledge values
capaedges capacities (scaled)
updatecapaupdate capacities?
ncutspointer to store number of cuts
localis the cut local?
successpointer 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 int graph_next_term ( const GRAPH g,
int  terms,
int *  term,
const int *  w,
const SCIP_Bool  firstrun 
)
static
Parameters
ggraph data structure
termsnumber of terminals
termterminal array
wawake level
firstrunfirst 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 void set_capacity ( const GRAPH g,
const SCIP_Bool  creep_flow,
const int  flip,
int *  capa,
const SCIP_Real xval 
)
static
Parameters
ggraph data structure
creep_flowcreep flow?
flipreverse the flow?
capaedges capacities (scaled)
xvaledge 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 SCIP_RETCODE sep_flow ( SCIP scip,
SCIP_CONSHDLR conshdlr,
SCIP_CONSHDLRDATA conshdlrdata,
SCIP_CONSDATA consdata,
int  maxcuts,
int *  ncuts 
)
static

separate

Parameters
scipSCIP data structure
conshdlrconstraint handler
conshdlrdataconstraint handler data
consdataconstraint data
maxcutsmaximal number of cuts
ncutspointer 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 SCIP_RETCODE sep_2cut ( SCIP scip,
SCIP_CONSHDLR conshdlr,
SCIP_CONSHDLRDATA conshdlrdata,
SCIP_CONSDATA consdata,
const int *  termorg,
int  maxcuts,
int *  ncuts 
)
static

◆ dualascent_init()

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 
)
static
Parameters
scipSCIP
ggraph data structure
startCSR start array [0,...,nnodes]
edgearrCSR ancestor edge array
rootthe root
is_pseudorootis the root a pseudo root?
ncsredgesnumber of CSR edges
gmarkarray for marking nodes
activeactive vertices mark
pqueuepriority queue
gnodearrarray containing terminal nodes
rescapresidual capacity
dualobjdual objective
augmentingcomponentaugmenting 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 SCIP_DECL_CONSHDLRCOPY ( conshdlrCopyStp  )
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 SCIP_DECL_CONSFREE ( consFreeStp  )
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 SCIP_DECL_CONSINITSOL ( consInitsolStp  )
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 SCIP_DECL_CONSDELETE ( consDeleteStp  )
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()

◆ SCIP_DECL_CONSINITLP()

static SCIP_DECL_CONSINITLP ( consInitlpStp  )
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()

◆ SCIP_DECL_CONSENFOLP()

static SCIP_DECL_CONSENFOLP ( consEnfolpStp  )
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 SCIP_DECL_CONSENFOPS ( consEnfopsStp  )
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 SCIP_DECL_CONSCHECK ( consCheckStp  )
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 SCIP_DECL_CONSPROP ( consPropStp  )
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 SCIP_DECL_CONSLOCK ( consLockStp  )
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 SCIP_DECL_CONSCOPY ( consCopyStp  )
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()

◆ 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 or NULL
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?
damaxdeviationmaximum deviation for dual-ascent ( -1.0 for default)
nodearrcharSTP_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 
)