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 "graph.h"
#include "portab.h"
#include "branch_stp.h"
#include "prop_stp.h"
#include "sepaspecial.h"
#include "mincut.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	STP_SEPASPECIAL_USECLIQUE   FALSE
#define	STP_SEPASPECIAL_USECVTIMP   FALSE
Constraint handler properties
#define	CONSHDLR_NAME   "stp"
#define	CONSHDLR_DESC   "steiner tree constraint handler"
#define	CONSHDLR_SEPAPRIORITY   9999999
#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   20
#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_INFLOWSEP   TRUE
#define	DEFAULT_INFLOWTERMSEP   TRUE
#define	DEFAULT_OUTFLOWSEP   TRUE
#define	DEFAULT_BALANCEFLOWSEP   TRUE

Functions
Local methods
static SCIP_RETCODE	sep_flowIn (SCIP *scip, SCIP_CONSHDLR *conshdlr, const SCIP_Real *nodes_inflow, const GRAPH *g, const SCIP_Real *xval, int vertex, SCIP_VAR **vars, int *cutcount)
static SCIP_RETCODE	sep_flowTermIn (SCIP *scip, SCIP_CONSHDLR *conshdlr, const SCIP_Real *nodes_inflow, const GRAPH *g, const SCIP_Real *xval, const int *termorg, int vertex, SCIP_VAR **vars, int *cutcount)
static SCIP_RETCODE	sep_flowBalance (SCIP *scip, SCIP_CONSHDLR *conshdlr, const SCIP_Real *nodes_inflow, const GRAPH *g, const SCIP_Real *xval, int vertex, SCIP_VAR **vars, int *cutcount)
static SCIP_RETCODE	sep_flowEdgeOut (SCIP *scip, SCIP_CONSHDLR *conshdlr, const SCIP_Real *nodes_inflow, const GRAPH *g, const SCIP_Real *xval, int vertex, SCIP_VAR **vars, int *cutcount)
static SCIP_RETCODE	sep_flow (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_CONSDATA *consdata, const int *termorg, int maxcuts, int *ncuts)
Callback methods
static	SCIP_DECL_CONSHDLRCOPY (conshdlrCopyStp)
static	SCIP_DECL_CONSFREE (consFreeStp)
static	SCIP_DECL_CONSINITSOL (consInitsolStp)
static	SCIP_DECL_CONSEXITSOL (consExitsolStp)
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	SCIPStpAddContractionCut (SCIP *scip, SCIP_VAR *edge, SCIP_VAR *revedge, SCIP_Bool localcut)
void	SCIPStpConshdlrSetGraph (SCIP *scip)
const int *	SCIPStpGetPcImplStarts (SCIP *scip)
int	SCIPStpGetPcImplNstarts (SCIP *scip)
const int *	SCIPStpGetPcImplVerts (SCIP *scip)

Macro Definition Documentation

ADDCUTSTOPOOL

#define ADDCUTSTOPOOL   0

Definition at line 61 of file cons_stp.c.

STP_SEPASPECIAL_USECLIQUE

#define STP_SEPASPECIAL_USECLIQUE   FALSE

Definition at line 62 of file cons_stp.c.

STP_SEPASPECIAL_USECVTIMP

#define STP_SEPASPECIAL_USECVTIMP   FALSE

Definition at line 63 of file cons_stp.c.

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   9999999

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   20

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

Referenced by SCIPincludeConshdlrStp().

DEFAULT_BACKCUT

#define DEFAULT_BACKCUT   FALSE

Try Back-Cuts FALSE

Definition at line 91 of file cons_stp.c.

Referenced by SCIPincludeConshdlrStp().

DEFAULT_CREEPFLOW

#define DEFAULT_CREEPFLOW   TRUE

Use Creep-Flow

Definition at line 92 of file cons_stp.c.

Referenced by SCIPincludeConshdlrStp().

DEFAULT_DISJUNCTCUT

#define DEFAULT_DISJUNCTCUT   FALSE

Only disjunct Cuts FALSE

Definition at line 93 of file cons_stp.c.

Referenced by SCIPincludeConshdlrStp().

DEFAULT_NESTEDCUT

#define DEFAULT_NESTEDCUT   FALSE

Try Nested-Cuts FALSE

Definition at line 94 of file cons_stp.c.

Referenced by SCIPincludeConshdlrStp().

DEFAULT_FLOWSEP

#define DEFAULT_FLOWSEP   TRUE

Try Flow-Cuts

Definition at line 95 of file cons_stp.c.

Referenced by SCIPincludeConshdlrStp().

DEFAULT_INFLOWSEP

#define DEFAULT_INFLOWSEP   TRUE

Try in-flow Cuts

Definition at line 96 of file cons_stp.c.

Referenced by SCIPincludeConshdlrStp().

DEFAULT_INFLOWTERMSEP

#define DEFAULT_INFLOWTERMSEP   TRUE

Try terminal in-flow Cuts

Definition at line 97 of file cons_stp.c.

Referenced by SCIPincludeConshdlrStp().

DEFAULT_OUTFLOWSEP

#define DEFAULT_OUTFLOWSEP   TRUE

Definition at line 98 of file cons_stp.c.

Referenced by SCIPincludeConshdlrStp().

DEFAULT_BALANCEFLOWSEP

#define DEFAULT_BALANCEFLOWSEP   TRUE

Definition at line 99 of file cons_stp.c.

Referenced by SCIPincludeConshdlrStp().

Function Documentation

sep_flowIn()

static SCIP_RETCODE sep_flowIn ( SCIP *  scip, SCIP_CONSHDLR *  conshdlr, const SCIP_Real *  nodes_inflow, const GRAPH *  g, const SCIP_Real *  xval, int  vertex, SCIP_VAR **  vars, int *  cutcount  )

static

separate in-flow cuts: input of a non-terminal vertex has to be <= 1.0

Parameters

scip	SCIP data structure
conshdlr	constraint handler
nodes_inflow	incoming flow per node
g	graph data structure
xval	LP-solution values
vertex	vertex
vars	variables
cutcount	counts cuts

Definition at line 244 of file cons_stp.c.

References EAT_LAST, FALSE, GRAPH::ieat, GRAPH::inpbeg, Is_term, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddPoolCut(), SCIPaddRow(), SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPcreateEmptyRowConshdlr(), SCIPflushRowExtensions(), SCIPinfinity(), SCIPisEQ(), SCIPisFeasGT(), SCIPreleaseRow(), sep_flowTermIn(), GRAPH::term, and TRUE.

Referenced by sep_flow().

sep_flowTermIn()

static SCIP_RETCODE sep_flowTermIn ( SCIP *  scip, SCIP_CONSHDLR *  conshdlr, const SCIP_Real *  nodes_inflow, const GRAPH *  g, const SCIP_Real *  xval, const int *  termorg, int  vertex, SCIP_VAR **  vars, int *  cutcount  )

static

separate terminal in-flow cuts at terminal input sum == 1 basically a cut (starcut)

Parameters

scip	SCIP data structure
conshdlr	constraint handler
nodes_inflow	incoming flow per node
g	graph data structure
xval	LP-solution values
termorg	original terminals or NULL
vertex	vertex
vars	variables
cutcount	counts cuts

Definition at line 303 of file cons_stp.c.

References EAT_LAST, FALSE, GRAPH::ieat, GRAPH::inpbeg, Is_term, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddPoolCut(), SCIPaddRow(), SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPcreateEmptyRowConshdlr(), SCIPflushRowExtensions(), SCIPisEQ(), SCIPisFeasEQ(), SCIPreleaseRow(), sep_flowBalance(), GRAPH::term, and TRUE.

Referenced by sep_flow(), and sep_flowIn().

sep_flowBalance()

static SCIP_RETCODE sep_flowBalance ( SCIP *  scip, SCIP_CONSHDLR *  conshdlr, const SCIP_Real *  nodes_inflow, const GRAPH *  g, const SCIP_Real *  xval, int  vertex, SCIP_VAR **  vars, int *  cutcount  )

static

separate flow-balance constraints incoming flow <= outgoing flow

Parameters

scip	SCIP data structure
conshdlr	constraint handler
nodes_inflow	incoming flow per node
g	graph data structure
xval	LP-solution values
vertex	vertex
vars	variables
cutcount	counts cuts

Definition at line 368 of file cons_stp.c.

References EAT_LAST, FALSE, GRAPH::ieat, GRAPH::inpbeg, Is_term, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddPoolCut(), SCIPaddRow(), SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPcreateEmptyRowConshdlr(), SCIPflushRowExtensions(), SCIPinfinity(), SCIPisEQ(), SCIPisFeasNegative(), SCIPreleaseRow(), sep_flowEdgeOut(), GRAPH::term, GRAPH::terms, and TRUE.

Referenced by sep_flow(), and sep_flowTermIn().

sep_flowEdgeOut()

static SCIP_RETCODE sep_flowEdgeOut ( SCIP *  scip, SCIP_CONSHDLR *  conshdlr, const SCIP_Real *  nodes_inflow, const GRAPH *  g, const SCIP_Real *  xval, int  vertex, SCIP_VAR **  vars, int *  cutcount  )

static

separate the value of each outgoing edge needs to be smaller than the sum of the in-going edges

Parameters

scip	SCIP data structure
conshdlr	constraint handler
nodes_inflow	incoming flow per node
g	graph data structure
xval	LP-solution values
vertex	vertex
vars	variables
cutcount	counts cuts

Definition at line 435 of file cons_stp.c.

References EAT_LAST, FALSE, flipedge, GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddPoolCut(), SCIPaddRow(), SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPcreateEmptyRowConshdlr(), SCIPflushRowExtensions(), SCIPinfinity(), SCIPisEQ(), SCIPisFeasNegative(), SCIPreleaseRow(), sep_flow(), GRAPH::tail, and TRUE.

Referenced by sep_flow(), and sep_flowBalance().

sep_flow()

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

static

separate flow-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 500 of file cons_stp.c.

References graph_get_nNodes(), GRAPH::ieat, GRAPH::inpbeg, Is_term, nnodes, NULL, SCIP_Bool, SCIP_CALL, SCIP_DECL_CONSHDLRCOPY(), SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPprobdataGetVars(), SCIPprobdataGetXval(), sep_flowBalance(), sep_flowEdgeOut(), sep_flowIn(), sep_flowTermIn(), GRAPH::source, and GRAPH::term.

Referenced by SCIP_DECL_CONSSEPALP(), and sep_flowEdgeOut().

SCIP_DECL_CONSHDLRCOPY()

static SCIP_DECL_CONSHDLRCOPY ( conshdlrCopyStp  )

static

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

Definition at line 603 of file cons_stp.c.

References CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_DECL_CONSFREE(), SCIP_OKAY, SCIPconshdlrGetName(), SCIPincludeConshdlrStp(), and TRUE.

Referenced by sep_flow().

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

References CONSHDLR_NAME, NULL, SCIP_DECL_CONSINITSOL(), SCIP_OKAY, SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPconshdlrSetData(), SCIPfreeMemory, and SCIPfreeRandom().

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

References SCIP_DECL_CONSEXITSOL(), SCIP_OKAY, and SCIPStpConshdlrSetGraph().

Referenced by SCIP_DECL_CONSFREE().

SCIP_DECL_CONSEXITSOL()

static SCIP_DECL_CONSEXITSOL ( consExitsolStp  )

static

Definition at line 651 of file cons_stp.c.

References SCIP_DECL_CONSDELETE(), SCIP_OKAY, SCIPconshdlrGetData(), sepaspecial_pacliquesFree(), sepaspecial_pcimplicationsFree(), and sepaspecial_vtimplicationsFree().

Referenced by SCIP_DECL_CONSINITSOL().

SCIP_DECL_CONSDELETE()

static SCIP_DECL_CONSDELETE ( consDeleteStp  )

static

frees specific constraint data

Definition at line 672 of file cons_stp.c.

References CONSHDLR_NAME, NULL, SCIP_DECL_CONSTRANS(), SCIP_OKAY, SCIPconshdlrGetName(), and SCIPfreeBlockMemory.

Referenced by SCIP_DECL_CONSEXITSOL().

SCIP_DECL_CONSTRANS()

static SCIP_DECL_CONSTRANS ( consTransStp  )

static

transforms constraint data into data belonging to the transformed problem

Definition at line 686 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 717 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 739 of file cons_stp.c.

References BMScopyMemoryArray, BRANCH_STP_VERTEX_TERM, FALSE, graph_knot_chg(), graph_pc_2org(), graph_pc_2trans(), graph_pc_isPcMw(), Is_term, GRAPH::knots, mincut_separateLp(), nnodes, nterms, NULL, SCIP_Bool, SCIP_CALL, SCIP_DECL_CONSENFOLP(), SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_SEPARATED, SCIPallocBufferArray, SCIPconsGetData(), SCIPconshdlrGetData(), SCIPdebugMessage, SCIPfreeBufferArrayNull, SCIPgetCurrentNode(), SCIPnodeGetDepth(), SCIPStpBranchruleGetVertexChgs(), SCIPStpBranchruleInitNodeState(), SCIPStpBranchruleIsActive(), SCIPStpBranchruleProbIsCompatible(), sep_flow(), sepaspecial_pacliquesInit(), sepaspecial_pacliquesSeparate(), sepaspecial_pcimplicationsInit(), sepaspecial_pcimplicationsSeparate(), sepaspecial_vtimplicationsInit(), sepaspecial_vtimplicationsSeparate(), STP_BRMWCSP, STP_TERM, 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 873 of file cons_stp.c.

References FALSE, 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 901 of file cons_stp.c.

References FALSE, 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 927 of file cons_stp.c.

References FALSE, 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 949 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 998 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 1020 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 1051 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_BALANCEFLOWSEP, DEFAULT_CREEPFLOW, DEFAULT_DISJUNCTCUT, DEFAULT_FLOWSEP, DEFAULT_INFLOWSEP, DEFAULT_INFLOWTERMSEP, DEFAULT_MAXROUNDS, DEFAULT_MAXROUNDSROOT, DEFAULT_MAXSEPACUTS, DEFAULT_MAXSEPACUTSROOT, DEFAULT_NESTEDCUT, DEFAULT_OUTFLOWSEP, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPaddBoolParam(), SCIPaddIntParam(), SCIPallocMemory, SCIPcreateConsStp(), SCIPcreateRandom(), SCIPincludeConshdlrBasic(), SCIPsetConshdlrCopy(), SCIPsetConshdlrDelete(), SCIPsetConshdlrExitsol(), SCIPsetConshdlrFree(), SCIPsetConshdlrInitlp(), SCIPsetConshdlrInitsol(), SCIPsetConshdlrProp(), SCIPsetConshdlrSepa(), SCIPsetConshdlrTrans(), and TRUE.

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

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

References CONSHDLR_NAME, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_PLUGINNOTFOUND, SCIPallocBlockMemory(), SCIPcreateCons(), SCIPerrorMessage, SCIPfindConshdlr(), SCIPStpAddContractionCut(), and TRUE.

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

SCIPStpAddContractionCut()

SCIP_RETCODE SCIPStpAddContractionCut	(	SCIP *	scip,
		SCIP_VAR *	edge,
		SCIP_VAR *	revedge,
		SCIP_Bool	localcut
	)

add cut corresponding to contraction

Parameters

scip	SCIP data structure
edge	edge
revedge	reversed edge
localcut	add local cut?

Definition at line 1165 of file cons_stp.c.

References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPaddPoolCut(), SCIPaddRow(), SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPconshdlrGetNConss(), SCIPcreateEmptyRowConshdlr(), SCIPfindConshdlr(), SCIPflushRowExtensions(), SCIPinfinity(), SCIPreleaseRow(), SCIPStpConshdlrSetGraph(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.

Referenced by SCIPcreateConsStp().

SCIPStpConshdlrSetGraph()

void SCIPStpConshdlrSetGraph

(

SCIP *

scip

)

sets graph

Parameters

scip	SCIP data structure

Definition at line 1208 of file cons_stp.c.

References NULL, SCIPconsGetData(), SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPfindConshdlr(), SCIPprobdataGetGraph2(), and SCIPStpGetPcImplStarts().

Referenced by SCIP_DECL_CONSINITSOL(), and SCIPStpAddContractionCut().

SCIPStpGetPcImplStarts()

const int* SCIPStpGetPcImplStarts

(

SCIP *

scip

)

returns implications start array

Parameters

scip	SCIP data structure

Definition at line 1231 of file cons_stp.c.

References NULL, SCIPconshdlrGetData(), SCIPfindConshdlr(), SCIPStpGetPcImplNstarts(), and sepaspecial_pcimplicationsGetStarts().

Referenced by propgraphApplyImplicationsPcMw(), SCIPStpConshdlrSetGraph(), and SCIPStpHeurLocalExtendPcMwImp().

SCIPStpGetPcImplNstarts()

int SCIPStpGetPcImplNstarts

(

SCIP *

scip

)

returns number implications starts

Parameters

scip	SCIP data structure

Definition at line 1250 of file cons_stp.c.

References NULL, SCIPconshdlrGetData(), SCIPfindConshdlr(), SCIPStpGetPcImplVerts(), and sepaspecial_pcimplicationsGetNstarts().

Referenced by propgraphApplyImplicationsPcMw(), and SCIPStpGetPcImplStarts().

SCIPStpGetPcImplVerts()

const int* SCIPStpGetPcImplVerts

(

SCIP *

scip

)

returns implications vertices array

Parameters

scip	SCIP data structure

Definition at line 1269 of file cons_stp.c.

References NULL, SCIPconshdlrGetData(), SCIPfindConshdlr(), and sepaspecial_pcimplicationsGetVerts().

Referenced by propgraphApplyImplicationsPcMw(), SCIPStpGetPcImplNstarts(), and SCIPStpHeurLocalExtendPcMwImp().