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

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

Functions

Function Documentation

◆ SCIPincludeConshdlrStp()

◆ SCIPcreateConsStp()

◆ SCIPStpConshdlrSetGraph()

◆ SCIPStpDualAscent()

◆ SCIPStpDualAscentPcMw()