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 "portab.h"
#include "scip/scip.h"
#include "scip/misc.h"
#include "scip/cons_linear.h"

Go to the source code of this file.

Macros
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   5
#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	FLOW_FACTOR   100000
#define	CREEP_VALUE   1

Functions
Local methods
static SCIP_RETCODE	cut_add (SCIP *scip, SCIP_CONSHDLR *conshdlr, const GRAPH *g, const int layer, const SCIP_Real *xval, int *capa, const int updatecapa, int *ncuts, SCIP_Bool *success)
static int	graph_next_term (int terms, int *term, const int *w)
static void	set_capacity (const GRAPH *g, const int layer, 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, int maxcuts, int *ncuts)
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)
SCIP_RETCODE	SCIPdualAscentStp (SCIP *scip, GRAPH *g, SCIP_Real *redcost, SCIP_Real *objval, SCIP_Bool addcuts, GNODE **gnodearrterms, int *edgearrint, int *nodearrint, int root, int nruns, char *edgearrchar, char *nodearrchar)
SCIP_RETCODE	SCIPdualAscentPcStp (SCIP *scip, GRAPH *g, SCIP_Real *redcost, SCIP_Real *objval, SCIP_Bool addcuts, int nruns)
SCIP_RETCODE	SCIPdualAscentAddCutsStp (SCIP *scip, GRAPH *g, int nruns)

Macro Definition Documentation

#define CONSHDLR_CHECKPRIORITY   9999999

priority of the constraint handler for checking feasibility

Definition at line 61 of file cons_stp.c.

Referenced by SCIPincludeConshdlrStp().

#define CONSHDLR_DELAYPROP   FALSE

should propagation method be delayed, if other propagators found reductions?

Definition at line 68 of file cons_stp.c.

Referenced by SCIPincludeConshdlrStp().

#define CONSHDLR_DELAYSEPA   FALSE

should separation method be delayed, if other separators found cuts?

Definition at line 67 of file cons_stp.c.

Referenced by SCIPincludeConshdlrStp().

#define CONSHDLR_DESC   "steiner tree constraint handler"

Definition at line 58 of file cons_stp.c.

Referenced by SCIPincludeConshdlrStp().

#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 64 of file cons_stp.c.

Referenced by SCIPincludeConshdlrStp().

#define CONSHDLR_ENFOPRIORITY   0

priority of the constraint handler for constraint enforcing

Definition at line 60 of file cons_stp.c.

Referenced by SCIPincludeConshdlrStp().

#define CONSHDLR_NAME   "stp"

Definition at line 57 of file cons_stp.c.

Referenced by SCIP_DECL_CONSDELETE(), SCIP_DECL_CONSFREE(), SCIP_DECL_CONSHDLRCOPY(), SCIP_DECL_CONSTRANS(), SCIPcreateConsStp(), and SCIPincludeConshdlrStp().

#define CONSHDLR_NEEDSCONS   TRUE

should the constraint handler be skipped, if no constraints are available?

Definition at line 69 of file cons_stp.c.

Referenced by SCIPincludeConshdlrStp().

#define CONSHDLR_PROP_TIMING   SCIP_PROPTIMING_BEFORELP

Definition at line 77 of file cons_stp.c.

Referenced by SCIPincludeConshdlrStp().

#define CONSHDLR_PROPFREQ   0

frequency for propagating domains; zero means only preprocessing propagation

Definition at line 63 of file cons_stp.c.

Referenced by SCIPincludeConshdlrStp().

#define CONSHDLR_SEPAFREQ   1

frequency for separating cuts; zero means to separate only in the root node

Definition at line 62 of file cons_stp.c.

Referenced by SCIPincludeConshdlrStp().

#define CONSHDLR_SEPAPRIORITY   0

priority of the constraint handler for separation

Definition at line 59 of file cons_stp.c.

Referenced by SCIPincludeConshdlrStp().

#define CREEP_VALUE   1

Definition at line 88 of file cons_stp.c.

Referenced by set_capacity().

#define DEFAULT_BACKCUT   FALSE

Try Back-Cuts FALSE

Definition at line 79 of file cons_stp.c.

Referenced by SCIPincludeConshdlrStp().

#define DEFAULT_CREEPFLOW   TRUE

Use Creep-Flow

Definition at line 80 of file cons_stp.c.

Referenced by SCIPincludeConshdlrStp().

#define DEFAULT_DAMAXDEVIATION   0.25

max deviation for dual ascent

Definition at line 85 of file cons_stp.c.

Referenced by SCIPdualAscentPcStp(), and SCIPdualAscentStp().

#define DEFAULT_DISJUNCTCUT   FALSE

Only disjunct Cuts FALSE

Definition at line 81 of file cons_stp.c.

Referenced by SCIPincludeConshdlrStp().

#define DEFAULT_FLOWSEP   TRUE

Try Flow-Cuts

Definition at line 83 of file cons_stp.c.

Referenced by SCIPincludeConshdlrStp().

#define DEFAULT_MAXROUNDS   5

maximal number of separation rounds per node (-1: unlimited)

Definition at line 71 of file cons_stp.c.

Referenced by SCIPincludeConshdlrStp().

#define DEFAULT_MAXROUNDSROOT   -1

maximal number of separation rounds in the root node (-1: unlimited)

Definition at line 72 of file cons_stp.c.

Referenced by SCIPincludeConshdlrStp().

#define DEFAULT_MAXSEPACUTS   INT_MAX

maximal number of cuts separated per separation round

Definition at line 73 of file cons_stp.c.

Referenced by SCIPincludeConshdlrStp().

#define DEFAULT_MAXSEPACUTSROOT   INT_MAX

maximal number of cuts separated per separation round in the root node

Definition at line 74 of file cons_stp.c.

Referenced by SCIPincludeConshdlrStp().

#define DEFAULT_NESTEDCUT   FALSE

Try Nested-Cuts FALSE

Definition at line 82 of file cons_stp.c.

Referenced by SCIPincludeConshdlrStp().

#define FLOW_FACTOR   100000

Definition at line 87 of file cons_stp.c.

Referenced by cut_add(), sep_2cut(), and set_capacity().

Function Documentation

static SCIP_RETCODE cut_add ( SCIP *  scip, SCIP_CONSHDLR *  conshdlr, const GRAPH *  g, const int  layer, const SCIP_Real *  xval, int *  capa, const int  updatecapa, int *  ncuts, SCIP_Bool *  success  )

static

add a cut

Parameters

scip	SCIP data structure
conshdlr	constraint handler
g	graph data structure
layer	current layer, set to zero usually
xval	edge values
capa	edges capacities (scaled)
updatecapa	update capacities?
ncuts	pointer to store number of cuts
success	pointer to store whether add cut be added

Definition at line 124 of file cons_stp.c.

References GRAPH::edges, FALSE, FLOW_FACTOR, graph_next_term(), GRAPH::head, GRAPH::mark, SCIPprobdataGetVars(), GRAPH::source, GRAPH::tail, and TRUE.

Referenced by sep_2cut().

static int graph_next_term ( int  terms, int *  term, const int *  w  )

static

Definition at line 211 of file cons_stp.c.

References set_capacity().

Referenced by cut_add(), and sep_2cut().

static SCIP_DECL_CONSCHECK ( consCheckStp  )

static

feasibility check method of constraint handler for integral solutions

Definition at line 945 of file cons_stp.c.

References SCIP_DECL_CONSPROP(), SCIPprobdataGetXval(), and SCIPvalidateStpSol().

Referenced by SCIP_DECL_CONSENFOPS().

static SCIP_DECL_CONSCOPY ( consCopyStp  )

static

constraint copying method of constraint handler

Definition at line 1039 of file cons_stp.c.

References SCIP_ConsData::graph, SCIPcreateConsStp(), SCIPincludeConshdlrStp(), SCIPprobdataGetGraph(), and TRUE.

Referenced by SCIP_DECL_CONSLOCK().

static SCIP_DECL_CONSDELETE ( consDeleteStp  )

static

frees specific constraint data

Definition at line 791 of file cons_stp.c.

References CONSHDLR_NAME, and SCIP_DECL_CONSTRANS().

Referenced by SCIP_DECL_CONSINITSOL().

static SCIP_DECL_CONSENFOLP ( consEnfolpStp  )

static

constraint enforcing method of constraint handler for LP solutions

Definition at line 895 of file cons_stp.c.

References SCIP_DECL_CONSENFOPS(), SCIPprobdataGetXval(), and SCIPvalidateStpSol().

Referenced by SCIP_DECL_CONSSEPALP().

static SCIP_DECL_CONSENFOPS ( consEnfopsStp  )

static

constraint enforcing method of constraint handler for pseudo solutions

Definition at line 920 of file cons_stp.c.

References SCIP_DECL_CONSCHECK(), SCIPprobdataGetXval(), and SCIPvalidateStpSol().

Referenced by SCIP_DECL_CONSENFOLP().

static SCIP_DECL_CONSFREE ( consFreeStp  )

static

destructor of constraint handler to free constraint handler data (called when SCIP is exiting)

Definition at line 751 of file cons_stp.c.

References CONSHDLR_NAME, and SCIP_DECL_CONSINITSOL().

Referenced by SCIP_DECL_CONSHDLRCOPY().

static SCIP_DECL_CONSHDLRCOPY ( conshdlrCopyStp  )

static

copy method for constraint handler plugins (called when SCIP copies plugins)

Definition at line 735 of file cons_stp.c.

References CONSHDLR_NAME, SCIP_DECL_CONSFREE(), SCIPincludeConshdlrStp(), and TRUE.

Referenced by sep_2cut().

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 837 of file cons_stp.c.

References SCIP_ConsData::graph, SCIP_DECL_CONSSEPALP(), SCIPdualAscentPcStp(), SCIPprobdataGetGraph(), and TRUE.

Referenced by SCIP_DECL_CONSTRANS().

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 772 of file cons_stp.c.

References SCIP_ConsData::graph, SCIP_DECL_CONSDELETE(), SCIPdualAscentStp(), and SCIPprobdataGetGraph().

Referenced by SCIP_DECL_CONSFREE().

static SCIP_DECL_CONSLOCK ( consLockStp  )

static

variable rounding lock method of constraint handler

Definition at line 1019 of file cons_stp.c.

References SCIP_DECL_CONSCOPY(), SCIPprobdataGetNVars(), and SCIPprobdataGetVars().

Referenced by SCIP_DECL_CONSPROP().

static SCIP_DECL_CONSPROP ( consPropStp  )

static

domain propagation method of constraint handler

Definition at line 970 of file cons_stp.c.

References SCIP_ConsData::graph, Is_term, GRAPH::knots, GRAPH::maxdeg, SCIP_DECL_CONSLOCK(), SCIPprobdataGetGraph(), STP_DEG_CONS, GRAPH::stp_type, and GRAPH::term.

Referenced by SCIP_DECL_CONSCHECK().

static SCIP_DECL_CONSSEPALP ( consSepalpStp  )

static

separation method of constraint handler for LP solutions

Definition at line 860 of file cons_stp.c.

References SCIP_DECL_CONSENFOLP(), sep_2cut(), and sep_flow().

Referenced by SCIP_DECL_CONSINITLP().

static SCIP_DECL_CONSTRANS ( consTransStp  )

static

transforms constraint data into data belonging to the transformed problem

Definition at line 805 of file cons_stp.c.

References CONSHDLR_NAME, and SCIP_DECL_CONSINITLP().

Referenced by SCIP_DECL_CONSDELETE().

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 1131 of file cons_stp.c.

References CONSHDLR_NAME, FALSE, SCIP_ConsData::graph, SCIPdualAscentStp(), and TRUE.

Referenced by SCIP_DECL_CONSCOPY(), SCIPincludeConshdlrStp(), and SCIPprobdataCreate().

SCIP_RETCODE SCIPdualAscentAddCutsStp	(	SCIP *	scip,
		GRAPH *	g,
		int	nruns
	)

dual ascent heuristic

Parameters

scip	SCIP data structure
g	graph data structure
nruns	number of dual ascent runs

Definition at line 2012 of file cons_stp.c.

References GRAPH::edges, FALSE, GRAPH::grad, Is_term, GRAPH::knots, SCIPdualAscentStp(), GRAPH::source, GRAPH::term, GRAPH::terms, and TRUE.

Referenced by SCIPdualAscentPcStp(), and SCIPprobdataCreate().

SCIP_RETCODE SCIPdualAscentPcStp	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Real *	redcost,
		SCIP_Real *	objval,
		SCIP_Bool	addcuts,
		int	nruns
	)

dual ascent heuristic

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?
nruns	number of dual ascent runs

Definition at line 1602 of file cons_stp.c.

References GRAPH::cost, DEFAULT_DAMAXDEVIATION, Graph_Node::dist, EAT_LAST, GRAPH::edges, FALSE, FARAWAY, GNODECmpByDist(), GRAPH::grad, graph_free(), graph_PcSapCopy(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::mark, Graph_Node::number, GRAPH::oeat, GRAPH::outbeg, SCIPdualAscentAddCutsStp(), SCIPprobdataGetOffset(), SCIPprobdataGetVars(), GRAPH::source, GRAPH::tail, GRAPH::term, GRAPH::terms, and TRUE.

Referenced by SCIP_DECL_CONSINITLP(), SCIPdualAscentStp(), and SCIPprobdataCreate().

SCIP_RETCODE SCIPdualAscentStp	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Real *	redcost,
		SCIP_Real *	objval,
		SCIP_Bool	addcuts,
		GNODE **	gnodearrterms,
		int *	edgearrint,
		int *	nodearrint,
		int	root,
		int	nruns,
		char *	edgearrchar,
		char *	nodearrchar
	)

dual ascent heuristic for the STP

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?
gnodearrterms	gnode terminals array for internal computations or NULL
edgearrint	int edges array for internal computations or NULL
nodearrint	int vertices array for internal computations or NULL
root	the root
nruns	number of dual ascent runs
edgearrchar	char edges array for internal computations or NULL
nodearrchar	char vertices array for internal computations or NULL

Definition at line 1161 of file cons_stp.c.

References GRAPH::cost, DEFAULT_DAMAXDEVIATION, Graph_Node::dist, EAT_LAST, GRAPH::edges, FALSE, FARAWAY, GNODECmpByDist(), GRAPH::grad, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::mark, Graph_Node::number, GRAPH::outbeg, SCIPdualAscentPcStp(), SCIPprobdataGetVars(), GRAPH::source, GRAPH::tail, GRAPH::term, GRAPH::terms, and TRUE.

Referenced by da_reduce(), daPc_reduce(), SCIP_DECL_CONSINITSOL(), SCIPcreateConsStp(), SCIPdualAscentAddCutsStp(), and SCIPprobdataCreate().

SCIP_RETCODE SCIPincludeConshdlrStp

(

SCIP *

scip

)

creates the handler for stp constraints and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 1070 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, SCIPcreateConsStp(), and TRUE.

Referenced by runShell(), SCIP_DECL_CONSCOPY(), and SCIP_DECL_CONSHDLRCOPY().

static SCIP_RETCODE sep_2cut ( SCIP *  scip, SCIP_CONSHDLR *  conshdlr, SCIP_CONSHDLRDATA *  conshdlrdata, SCIP_CONSDATA *  consdata, int  maxcuts, int *  ncuts  )

static

separate 2-cuts

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 519 of file cons_stp.c.

References cut_add(), GRAPH::edges, FALSE, FLOW_FACTOR, FSP_MODE, graph_mincut_exec(), graph_next_term(), graph_path_exec(), GRAPH::knots, GRAPH::layers, GRAPH::locals, GRAPH::mark, SCIP_DECL_CONSHDLRCOPY(), SCIPprobdataGetXval(), set_capacity(), GRAPH::source, STP_MAX_NODE_WEIGHT, GRAPH::stp_type, GRAPH::term, GRAPH::terms, and TRUE.

Referenced by SCIP_DECL_CONSSEPALP(), and 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 289 of file cons_stp.c.

References EAT_LAST, GRAPH::edges, FALSE, GRAPH::ieat, GRAPH::inpbeg, GRAPH::knots, GRAPH::layers, GRAPH::locals, GRAPH::oeat, GRAPH::outbeg, SCIPprobdataGetVars(), SCIPprobdataGetXval(), sep_2cut(), GRAPH::source, GRAPH::term, and TRUE.

Referenced by SCIP_DECL_CONSSEPALP(), and set_capacity().

static void set_capacity ( const GRAPH *  g, const int  layer, const SCIP_Bool  creep_flow, const int  flip, int *  capa, const SCIP_Real *  xval  )

static

Parameters

g	graph data structure
layer	current layer, usually set to zero
creep_flow	creep flow?
flip	reverse the flow?
capa	edges capacities (scaled)
xval	edge values

Definition at line 248 of file cons_stp.c.

References CREEP_VALUE, GRAPH::edges, FLOW_FACTOR, and sep_flow().

Referenced by graph_next_term(), and sep_2cut().