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

#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

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

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 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

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(), SCIPcreateEmptyRowCons(), 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

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 void set_capacity	(	const GRAPH *	g,
		const SCIP_Bool	creep_flow,
		const int	flip,
		int *	capa,
		const SCIP_Real *	xval
	)

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 SCIP_RETCODE sep_flow	(	SCIP *	scip,
		SCIP_CONSHDLR *	conshdlr,
		SCIP_CONSHDLRDATA *	conshdlrdata,
		SCIP_CONSDATA *	consdata,
		int	maxcuts,
		int *	ncuts
	)

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(), SCIPcreateEmptyRowCons(), 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

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 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

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 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()

static SCIP_DECL_CONSTRANS ( consTransStp )

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 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()

static SCIP_DECL_CONSSEPALP ( consSepalpStp )

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 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_LOCKTYPE_MODEL, 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 1542 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 1573 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 1634 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

scip	SCIP data structure
g	graph data structure

Definition at line 1664 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 1685 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, RESTRICT, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_STAGE_INITSOLVE, SCIPaddCoefLinear(), SCIPaddCons(), SCIPaddRow(), SCIPaddVarToRow(), SCIPallocBlockMemory, SCIPallocBufferArray, SCIPallocMemoryArray, SCIPcacheRowExtensions(), SCIPcreateConsLinear(), SCIPcreateEmptyRowCons(), 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 2266 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(), SCIPcreateEmptyRowCons(), 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().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ ADDCUTSTOPOOL

◆ Q_NULL

◆ CONSHDLR_NAME

◆ CONSHDLR_DESC

◆ CONSHDLR_SEPAPRIORITY

◆ CONSHDLR_ENFOPRIORITY

◆ CONSHDLR_CHECKPRIORITY

◆ CONSHDLR_SEPAFREQ

◆ CONSHDLR_PROPFREQ

◆ CONSHDLR_EAGERFREQ

◆ CONSHDLR_DELAYSEPA

◆ CONSHDLR_DELAYPROP

◆ CONSHDLR_NEEDSCONS

◆ DEFAULT_MAXROUNDS

◆ DEFAULT_MAXROUNDSROOT

◆ DEFAULT_MAXSEPACUTS

◆ DEFAULT_MAXSEPACUTSROOT

◆ CONSHDLR_PROP_TIMING

◆ DEFAULT_BACKCUT

◆ DEFAULT_CREEPFLOW

◆ DEFAULT_DISJUNCTCUT

◆ DEFAULT_NESTEDCUT

◆ DEFAULT_FLOWSEP

◆ DEFAULT_DAMAXDEVIATION

◆ DA_MAXDEVIATION_LOWER

◆ DA_MAXDEVIATION_UPPER

◆ DA_EPS

◆ FLOW_FACTOR

◆ CREEP_VALUE

◆ DFS

Function Documentation

◆ is_active()

◆ cut_add()

◆ graph_next_term()

◆ set_capacity()

◆ sep_flow()

◆ sep_2cut()

◆ dualascent_init()

◆ SCIP_DECL_CONSHDLRCOPY()

◆ SCIP_DECL_CONSFREE()

◆ SCIP_DECL_CONSINITSOL()

◆ SCIP_DECL_CONSDELETE()

◆ SCIP_DECL_CONSTRANS()

◆ SCIP_DECL_CONSINITLP()

◆ SCIP_DECL_CONSSEPALP()

◆ SCIP_DECL_CONSENFOLP()

◆ SCIP_DECL_CONSENFOPS()

◆ SCIP_DECL_CONSCHECK()

◆ SCIP_DECL_CONSPROP()

◆ SCIP_DECL_CONSLOCK()

◆ SCIP_DECL_CONSCOPY()

◆ SCIPincludeConshdlrStp()

◆ SCIPcreateConsStp()

◆ SCIPStpConshdlrSetGraph()

◆ SCIPStpDualAscent()

◆ SCIPStpDualAscentPcMw()