probdata_stp.c File Reference

Detailed Description

Problem data for Steiner problems.

Author

Gerald Gamrath

Thorsten Koch

Michael Winkler

Daniel Rehfeldt

This file implements the problem data for Steiner problems. For more details see Main problem data page.

Definition in file probdata_stp.c.

#include <string.h>
#include "probdata_stp.h"
#include <stdio.h>
#include "scip/scip.h"
#include "cons_stp.h"
#include "grph.h"
#include "scip/cons_linear.h"
#include "scip/cons_setppc.h"
#include "scip/misc.h"
#include "scip/struct_misc.h"
#include "branch_stp.h"

Go to the source code of this file.

Macros
#define	STP_AGG_SYM
#define	CENTER_OK   0
#define	CENTER_DEG   1
#define	CENTER_SUM   2
#define	CENTER_MIN   3
#define	CENTER_ALL   4
#define	MODE_CUT   0
#define	MODE_FLOW   1
#define	MODE_PRICE   2
#define	CONS_ALWAYS   1
#define	CONS_SPECIFIC   2
#define	FLOWB   FALSE
#define	USEOFFSETVAR   TRUE
#define	SYM_CONS_LIMIT   20000
#define	CYC_CONS_LIMIT   15000
#define	CUT_MAXNTERMINALS   500
#define	CUT_MAXNEDGES   10000
#define	CUT_MAXTOTNEDGES   50000

Functions
Local methods
static void	updateorgsol (GRAPH *graph, IDX *curr, STP_Bool *orgnodes, STP_Bool *orgedges, int *nsolnodes, int *nsoledges)
static SCIP_RETCODE	central_terminal (SCIP *scip, GRAPH *g, int *central_term, int centertype)
static SCIP_RETCODE	probdataCreate (SCIP *scip, SCIP_PROBDATA **probdata, GRAPH *graph)
static SCIP_RETCODE	probdataFree (SCIP *scip, SCIP_PROBDATA **probdata)
static SCIP_RETCODE	probdataPrintGraph (GRAPH *graph, const char *filename, SCIP_Bool *edgemark)
static SCIP_RETCODE	createHopConstraint (SCIP *scip, SCIP_PROBDATA *probdata)
static SCIP_RETCODE	createDegreeConstraints (SCIP *scip, SCIP_PROBDATA *probdata)
static SCIP_RETCODE	createPrizeConstraints (SCIP *scip, SCIP_PROBDATA *probdata)
static SCIP_RETCODE	createConstraints (SCIP *scip, SCIP_PROBDATA *probdata)
static SCIP_RETCODE	createVariables (SCIP *scip, SCIP_PROBDATA *probdata, SCIP_Real offset)
Callback methods of problem data
static	SCIP_DECL_PROBCOPY (probcopyStp)
static	SCIP_DECL_PROBDELORIG (probdelorigStp)
static	SCIP_DECL_PROBTRANS (probtransStp)
static	SCIP_DECL_PROBINITSOL (probinitsolStp)
static	SCIP_DECL_PROBEXITSOL (probexitsolStp)
static	SCIP_DECL_PROBDELTRANS (probdeltransStp)
Interface methods
SCIP_RETCODE	SCIPprobdataCreate (SCIP *scip, const char *filename)
void	SCIPprobdataSetGraph (SCIP_PROBDATA *probdata, GRAPH *graph)
GRAPH *	SCIPprobdataGetGraph (SCIP_PROBDATA *probdata)
GRAPH *	SCIPprobdataGetGraph2 (SCIP *scip)
void	SCIPprobdataSetOffset (SCIP_PROBDATA *probdata, SCIP_Real offset)
int	SCIPprobdataGetNVars (SCIP *scip)
SCIP_VAR **	SCIPprobdataGetVars (SCIP *scip)
int	SCIPprobdataGetNLayers (SCIP *scip)
int	SCIPprobdataGetNEdges (SCIP *scip)
int	SCIPprobdataGetNTerms (SCIP *scip)
int	SCIPprobdataGetRNTerms (SCIP *scip)
int	SCIPprobdataGetRoot (SCIP *scip)
int	SCIPprobdataGetNorgEdges (SCIP *scip)
SCIP_Real	SCIPprobdataGetOffset (SCIP *scip)
SCIP_VAR *	SCIPprobdataGetedgeVarByIndex (SCIP *scip, int idx)
SCIP_Real *	SCIPprobdataGetXval (SCIP *scip, SCIP_SOL *sol)
SCIP_CONS **	SCIPprobdataGetEdgeConstraints (SCIP *scip)
SCIP_CONS **	SCIPprobdataGetPathConstraints (SCIP *scip)
int *	SCIPprobdataGetRTerms (SCIP *scip)
SCIP_VAR **	SCIPprobdataGetEdgeVars (SCIP *scip)
SCIP_Bool	SCIPprobdataIsBigt (SCIP *scip)
SCIP_RETCODE	SCIPprobdataPrintGraph (SCIP *scip, const char *filename, SCIP_SOL *sol, SCIP_Bool printsol)
SCIP_RETCODE	SCIPprobdataWriteIntermediateSolution (SCIP *scip)
void	SCIPprobdataWriteStp (SCIP *scip, const GRAPH *graph, const char *filename)
SCIP_RETCODE	SCIPprobdataWriteSolution (SCIP *scip, FILE *file)
void	SCIPprobdataWriteLogLine (SCIP *scip, const char *formatstr,...)
SCIP_RETCODE	SCIPprobdataAddNewSol (SCIP *scip, SCIP_Real *nval, SCIP_SOL *sol, SCIP_HEUR *heur, SCIP_Bool *success)
SCIP_RETCODE	SCIPprobdataPrintGraph2 (const GRAPH *graph, const char *filename, SCIP_Bool *edgemark)
int	SCIPprobdataGetType (SCIP *scip)
SCIP_RETCODE	SCIPprobdataWriteLogfileEnd (SCIP *scip)
void	SCIPprobdataSetDualBound (SCIP *scip, SCIP_Real dual)
void	SCIPprobdataSetNSolvers (SCIP *scip, int nSolvers)
void	initReceivedSubproblem (SCIP *scip, const int lLinearConsNames, const char *linearConsNames, const int lSetppcConsNames, const char *setppcConsNames)

Macro Definition Documentation

STP_AGG_SYM

#define STP_AGG_SYM

Definition at line 53 of file probdata_stp.c.

CENTER_OK

#define CENTER_OK   0

do nothing

Definition at line 54 of file probdata_stp.c.

Referenced by central_terminal().

CENTER_DEG

#define CENTER_DEG   1

find maximum degree

Definition at line 55 of file probdata_stp.c.

Referenced by central_terminal(), and SCIPprobdataCreate().

CENTER_SUM

#define CENTER_SUM   2

find the minimum distance sum

Definition at line 56 of file probdata_stp.c.

Referenced by central_terminal().

CENTER_MIN

#define CENTER_MIN   3

find the minimum largest distance

Definition at line 57 of file probdata_stp.c.

Referenced by central_terminal().

CENTER_ALL

#define CENTER_ALL   4

find the minimum distance sum to all knots

Definition at line 58 of file probdata_stp.c.

Referenced by central_terminal().

MODE_CUT

#define MODE_CUT   0

branch and cut

Definition at line 60 of file probdata_stp.c.

Referenced by createConstraints(), createVariables(), initReceivedSubproblem(), probdataFree(), SCIP_DECL_PROBCOPY(), SCIP_DECL_PROBDELORIG(), SCIP_DECL_PROBTRANS(), SCIPprobdataAddNewSol(), and SCIPprobdataCreate().

MODE_FLOW

#define MODE_FLOW   1

use flow model

Definition at line 61 of file probdata_stp.c.

Referenced by createConstraints(), createVariables(), probdataFree(), SCIP_DECL_PROBCOPY(), SCIP_DECL_PROBTRANS(), SCIPprobdataAddNewSol(), and SCIPprobdataCreate().

MODE_PRICE

#define MODE_PRICE   2

branch and price

Definition at line 62 of file probdata_stp.c.

Referenced by createConstraints(), createVariables(), probdataFree(), SCIP_DECL_PROBCOPY(), SCIP_DECL_PROBTRANS(), SCIPprobdataAddNewSol(), and SCIPprobdataCreate().

CONS_ALWAYS

#define CONS_ALWAYS   1

always use (respective) constraints

Definition at line 64 of file probdata_stp.c.

Referenced by SCIPprobdataCreate().

CONS_SPECIFIC

#define CONS_SPECIFIC   2

use (respective) constraints depending on the problem instance

Definition at line 65 of file probdata_stp.c.

Referenced by SCIPprobdataCreate().

FLOWB

#define FLOWB   FALSE

Definition at line 67 of file probdata_stp.c.

USEOFFSETVAR

#define USEOFFSETVAR   TRUE

Definition at line 68 of file probdata_stp.c.

SYM_CONS_LIMIT

#define SYM_CONS_LIMIT   20000

maximum number of symmetry inequalities for MWCSP and PCSPG

Definition at line 70 of file probdata_stp.c.

Referenced by SCIPprobdataCreate().

CYC_CONS_LIMIT

#define CYC_CONS_LIMIT   15000

maximum number of symmetry inequalities for PCSPG

Definition at line 71 of file probdata_stp.c.

Referenced by SCIPprobdataCreate().

CUT_MAXNTERMINALS

#define CUT_MAXNTERMINALS   500

Definition at line 73 of file probdata_stp.c.

Referenced by SCIPprobdataCreate().

CUT_MAXNEDGES

#define CUT_MAXNEDGES   10000

Definition at line 74 of file probdata_stp.c.

Referenced by SCIPprobdataCreate().

CUT_MAXTOTNEDGES

#define CUT_MAXTOTNEDGES   50000

Definition at line 75 of file probdata_stp.c.

Referenced by SCIPprobdataCreate().

Function Documentation

updateorgsol()

static void updateorgsol ( GRAPH *  graph, IDX *  curr, STP_Bool *  orgnodes, STP_Bool *  orgedges, int *  nsolnodes, int *  nsoledges  )

static

Parameters

graph	graph data structure
curr	head of solution edge list
orgnodes	array to mark whether a node is part of the original solution
orgedges	array to mark whether an edge is part of the original solution
nsolnodes	pointer to store the number of nodes in the original solution
nsoledges	pointer to store the number of edges in the original solution

Definition at line 151 of file probdata_stp.c.

References FALSE, Int_List_Node::index, NULL, GRAPH::orghead, GRAPH::orgtail, Int_List_Node::parent, and TRUE.

Referenced by SCIPprobdataWriteSolution().

central_terminal()

static SCIP_RETCODE central_terminal ( SCIP *  scip, GRAPH *  g, int *  central_term, int  centertype  )

static

Parameters

scip	SCIP data structure
g	graph data structure
central_term	pointer to store the selected (terminal) vertex
centertype	type of root selection

Definition at line 202 of file probdata_stp.c.

References CENTER_ALL, CENTER_DEG, CENTER_MIN, CENTER_OK, CENTER_SUM, shortest_path::dist, GRAPH::edges, FARAWAY, FSP_MODE, GRAPH::grad, graph_path_exec(), Is_term, GRAPH::knots, GRAPH::layers, GRAPH::mark, NULL, SCIP_CALL, SCIP_OKAY, SCIP_VERBLEVEL_HIGH, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisEQ(), SCIPisLT(), SCIPverbMessage(), GRAPH::source, GRAPH::term, and TRUE.

Referenced by SCIPprobdataCreate().

probdataCreate()

static SCIP_RETCODE probdataCreate ( SCIP *  scip, SCIP_PROBDATA **  probdata, GRAPH *  graph  )

static

creates problem data

Parameters

scip	SCIP data structure
probdata	pointer to problem data
graph	graph data structure

Definition at line 334 of file probdata_stp.c.

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, STP_SPG, and GRAPH::stp_type.

Referenced by SCIP_DECL_PROBCOPY(), SCIP_DECL_PROBTRANS(), and SCIPprobdataCreate().

probdataFree()

static SCIP_RETCODE probdataFree ( SCIP *  scip, SCIP_PROBDATA **  probdata  )

static

frees the memory of the given problem data

Parameters

scip	SCIP data structure
probdata	pointer to problem data

Definition at line 368 of file probdata_stp.c.

References MODE_CUT, MODE_FLOW, MODE_PRICE, NULL, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, SCIPfreeMemory, SCIPfreeMemoryArrayNull, SCIPreleaseCons(), SCIPreleaseVar(), STP_DCSTP, STP_MWCSP, STP_PCSPG, and STP_RPCSPG.

Referenced by SCIP_DECL_PROBDELORIG(), and SCIP_DECL_PROBDELTRANS().

probdataPrintGraph()

static SCIP_RETCODE probdataPrintGraph ( GRAPH *  graph, const char *  filename, SCIP_Bool *  edgemark  )

static

print graph (in undirected form) in GML format

Parameters

graph	Graph to be printed
filename	Name of the output file
edgemark	Array of (undirected) edges to highlight

Definition at line 499 of file probdata_stp.c.

References GRAPH::cost, GRAPH::edges, FALSE, GRAPH::head, GRAPH::knots, NULL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPgmlWriteClosing(), SCIPgmlWriteEdge(), SCIPgmlWriteNode(), SCIPgmlWriteOpening(), SCIPsnprintf(), GRAPH::source, GRAPH::tail, and GRAPH::term.

Referenced by SCIPprobdataCreate(), and SCIPprobdataPrintGraph().

createHopConstraint()

static SCIP_RETCODE createHopConstraint ( SCIP *  scip, SCIP_PROBDATA *  probdata  )

static

create (edge-) HOP constraint (cut mode only)

Parameters

scip	SCIP data structure
probdata	problem data

Definition at line 570 of file probdata_stp.c.

References FALSE, GRAPH::hoplimit, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddCons(), SCIPcreateConsLinear(), SCIPdebugMessage, SCIPinfinity(), and TRUE.

Referenced by SCIPprobdataCreate().

createDegreeConstraints()

static SCIP_RETCODE createDegreeConstraints ( SCIP *  scip, SCIP_PROBDATA *  probdata  )

static

create (node-) degree constraints (cut mode only)

Parameters

scip	SCIP data structure
probdata	problem data

Definition at line 598 of file probdata_stp.c.

References FALSE, GRAPH::maxdeg, nnodes, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddCons(), SCIPallocMemoryArray, SCIPcreateConsLinear(), SCIPdebugMessage, SCIPinfinity(), SCIPsnprintf(), and TRUE.

Referenced by SCIPprobdataCreate().

createPrizeConstraints()

static SCIP_RETCODE createPrizeConstraints ( SCIP *  scip, SCIP_PROBDATA *  probdata  )

static

create Prize constraints (cut mode only)

Parameters

scip	SCIP data structure
probdata	problem data

Definition at line 633 of file probdata_stp.c.

References GRAPH::edges, FALSE, GRAPH::head, GRAPH::knots, NULL, r, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddCons(), SCIPallocMemoryArray, SCIPcreateConsLinear(), SCIPcreateConsSetpack(), SCIPdebugMessage, SCIPinfinity(), SCIPsnprintf(), GRAPH::source, STP_PCSPG, STP_RPCSPG, GRAPH::stp_type, GRAPH::terms, and TRUE.

Referenced by SCIPprobdataCreate().

createConstraints()

static SCIP_RETCODE createConstraints ( SCIP *  scip, SCIP_PROBDATA *  probdata  )

static

create constraints (in Flow or Price Mode)

Parameters

scip	SCIP data structure
probdata	problem data

Definition at line 759 of file probdata_stp.c.

References FALSE, MODE_CUT, MODE_FLOW, MODE_PRICE, nnodes, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddCons(), SCIPallocMemoryArray, SCIPcreateConsLinear(), SCIPdebugMessage, SCIPinfinity(), SCIPsnprintf(), GRAPH::source, GRAPH::term, and TRUE.

Referenced by SCIPprobdataCreate().

createVariables()

static SCIP_RETCODE createVariables ( SCIP *  scip, SCIP_PROBDATA *  probdata, SCIP_Real  offset  )

static

create initial columns

Parameters

scip	SCIP data structure
probdata	problem data
offset	offset computed during the presolving

Definition at line 905 of file probdata_stp.c.

References a, GRAPH::cost, EAT_LAST, shortest_path::edge, GRAPH::edges, GRAPH::extended, flipedge, FSP_MODE, graph_path_exec(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::mark, MODE_CUT, MODE_FLOW, MODE_PRICE, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_INTEGER, SCIPaddCoefLinear(), SCIPaddCoefSetppc(), SCIPaddOrigObjoffset(), SCIPaddVar(), SCIPallocBufferArray, SCIPallocMemoryArray, SCIPchgVarBranchPriority(), SCIPchgVarUbLazy(), SCIPcreateVarBasic(), SCIPdebugMessage, SCIPfreeBufferArray, SCIPinfinity(), SCIPisIntegral(), SCIPsetObjIntegral(), SCIPsnprintf(), GRAPH::source, STP_DCSTP, STP_DHCSTP, STP_MWCSP, STP_PCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, and GRAPH::terms.

Referenced by SCIPprobdataCreate().

SCIP_DECL_PROBCOPY()

static SCIP_DECL_PROBCOPY ( probcopyStp  )

static

copies user data of source SCIP for the target SCIP

Definition at line 1248 of file probdata_stp.c.

References graph_copy(), graph_mincut_init(), graph_path_init(), MODE_CUT, MODE_FLOW, MODE_PRICE, NULL, probdataCreate(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_SUCCESS, SCIPallocMemoryArray, SCIPcaptureCons(), SCIPcaptureVar(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPdebugMessage, SCIPgetConsCopy(), SCIPgetVarCopy(), SCIPvarIsActive(), STP_DCSTP, STP_MWCSP, STP_PCSPG, STP_RPCSPG, and TRUE.

SCIP_DECL_PROBDELORIG()

static SCIP_DECL_PROBDELORIG ( probdelorigStp  )

static

frees user data of original problem (called when the original problem is freed)

Definition at line 1628 of file probdata_stp.c.

References graph_free(), graph_mincut_exit(), graph_path_exit(), MODE_CUT, NULL, probdataFree(), SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, and TRUE.

SCIP_DECL_PROBTRANS()

static SCIP_DECL_PROBTRANS ( probtransStp  )

static

creates user data of transformed problem by transforming the original user problem data (called after problem was transformed)

Definition at line 1659 of file probdata_stp.c.

References MAX, MODE_CUT, MODE_FLOW, MODE_PRICE, NULL, probdataCreate(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocMemoryArray, SCIPdebugMessage, SCIPgetBoolParam(), SCIPgetReadingTime(), SCIPgetRealParam(), SCIPsetRealParam(), SCIPtransformCons(), SCIPtransformConss(), SCIPtransformVar(), SCIPtransformVars(), STP_DCSTP, STP_MWCSP, and STP_PCSPG.

SCIP_DECL_PROBINITSOL()

static SCIP_DECL_PROBINITSOL ( probinitsolStp  )

static

Definition at line 1819 of file probdata_stp.c.

References NULL, and SCIP_OKAY.

SCIP_DECL_PROBEXITSOL()

static SCIP_DECL_PROBEXITSOL ( probexitsolStp  )

static

Definition at line 1828 of file probdata_stp.c.

References NULL, SCIP_CALL, SCIP_FILECREATEERROR, SCIP_OKAY, SCIP_Real, SCIPerrorMessage, SCIPgetDualbound(), SCIPgetNSols(), SCIPgetPrimalbound(), SCIPgetTotalTime(), SCIPprobdataWriteLogLine(), SCIPprobdataWriteSolution(), STP_MWCSP, and STP_RMWCSP.

SCIP_DECL_PROBDELTRANS()

static SCIP_DECL_PROBDELTRANS ( probdeltransStp  )

static

frees user data of transformed problem (called when the transformed problem is freed)

Definition at line 1897 of file probdata_stp.c.

References probdataFree(), SCIP_CALL, SCIP_OKAY, and SCIPdebugMessage.

SCIPprobdataCreate()

SCIP_RETCODE SCIPprobdataCreate	(	SCIP *	scip,
		const char *	filename
	)

sets up the problem data

Parameters

scip	SCIP data structure
filename	file name

Definition at line 1915 of file probdata_stp.c.

References CENTER_DEG, central_terminal(), CONS_ALWAYS, CONS_SPECIFIC, createConstraints(), createDegreeConstraints(), createHopConstraint(), createPrizeConstraints(), createVariables(), CUT_MAXNEDGES, CUT_MAXNTERMINALS, CUT_MAXTOTNEDGES, CYC_CONS_LIMIT, GRAPH::edges, FALSE, presolve_info::fixed, graph_copy(), graph_load(), graph_mincut_init(), graph_pack(), graph_path_init(), Is_term, GRAPH::knots, GRAPH::layers, MODE_CUT, MODE_FLOW, MODE_PRICE, nnodes, NULL, GRAPH::orgsource, polyscip::global::print(), probdataCreate(), probdataPrintGraph(), reduce(), SCIP_Bool, SCIP_CALL, SCIP_FILECREATEERROR, SCIP_MAXSTRLEN, SCIP_OBJSENSE_MINIMIZE, SCIP_OKAY, SCIP_Real, SCIPaddCons(), SCIPallocMemoryArray, SCIPcreateConsStp(), SCIPcreateProbBasic(), SCIPdebugMessage, SCIPerrorMessage, SCIPgetBoolParam(), SCIPgetCharParam(), SCIPgetIntParam(), SCIPgetRealParam(), SCIPgetStringParam(), SCIPprintSysError(), SCIPprobdataWriteLogLine(), SCIPreleaseCons(), SCIPsetIntParam(), SCIPsetObjsense(), SCIPsetProbCopy(), SCIPsetProbData(), SCIPsetProbDelorig(), SCIPsetProbDeltrans(), SCIPsetProbExitsol(), SCIPsetProbInitsol(), SCIPsetProbTrans(), SCIPsetRealParam(), SCIPsnprintf(), SCIPsplitFilename(), SCIPStpDualAscent(), SCIPStpDualAscentPcMw(), SCIPwriteOrigProblem(), GRAPH::source, STP_DCSTP, STP_DHCSTP, STP_GSTP, STP_MWCSP, STP_NWSPG, STP_OARSMT, STP_PCSPG, STP_RMWCSP, STP_RPCSPG, STP_RSMT, STP_SAP, STP_SPG, GRAPH::stp_type, SYM_CONS_LIMIT, GRAPH::term, GRAPH::terms, TRUE, and VERSION_SCIPJACK.

SCIPprobdataSetGraph()

void SCIPprobdataSetGraph	(	SCIP_PROBDATA *	probdata,
		GRAPH *	graph
	)

sets the probdata graph

Parameters

probdata	problem data
graph	graph data structure

Definition at line 2345 of file probdata_stp.c.

References NULL.

SCIPprobdataGetGraph()

GRAPH* SCIPprobdataGetGraph

(

SCIP_PROBDATA *

probdata

)

returns the graph

Parameters

probdata

problem data

Definition at line 2357 of file probdata_stp.c.

References NULL.

Referenced by initReceivedSubproblem(), pricing(), SCIP_DECL_BRANCHEXECLP(), SCIP_DECL_BRANCHEXECPS(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSINITLP(), SCIP_DECL_CONSPROP(), SCIP_DECL_HEUREXEC(), SCIP_DECL_HEURINIT(), SCIP_DECL_PROPEXEC(), SCIP_DECL_READERREAD(), and SCIP_DECL_READERWRITE().

SCIPprobdataGetGraph2()

GRAPH* SCIPprobdataGetGraph2

(

SCIP *

scip

)

returns the graph

Parameters

scip	problem data

Definition at line 2367 of file probdata_stp.c.

References NULL, and SCIPgetProbData().

Referenced by SCIP_DECL_CONSCHECK(), SCIP_DECL_CONSINITSOL(), SCIPStpConshdlrSetGraph(), and selectBranchingVertexBySol().

SCIPprobdataSetOffset()

void SCIPprobdataSetOffset	(	SCIP_PROBDATA *	probdata,
		SCIP_Real	offset
	)

sets the offset

Parameters

probdata	problem data
offset	the offset value

Definition at line 2382 of file probdata_stp.c.

References NULL.

SCIPprobdataGetNVars()

int SCIPprobdataGetNVars

(

SCIP *

scip

)

returns the number of variables

Parameters

scip	SCIP data structure

Definition at line 2394 of file probdata_stp.c.

References NULL, and SCIPgetProbData().

Referenced by consdataCheck(), SCIP_DECL_CONSACTIVE(), SCIP_DECL_CONSDEACTIVE(), SCIP_DECL_CONSLOCK(), SCIP_DECL_CONSPROP(), SCIP_DECL_HEUREXEC(), SCIPStpHeurAscendPruneRun(), and selectBranchingVertexBySol().

SCIPprobdataGetVars()

SCIP_VAR** SCIPprobdataGetVars

(

SCIP *

scip

)

returns the array with all variables

Parameters

scip	SCIP data structure

Definition at line 2409 of file probdata_stp.c.

References NULL, and SCIPgetProbData().

Referenced by consdataCheck(), cut_add(), reduce_boundHopRc(), SCIP_DECL_CONSLOCK(), SCIP_DECL_CONSPROP(), SCIP_DECL_HEUREXEC(), SCIP_DECL_PROPEXEC(), SCIPStpDualAscent(), SCIPStpDualAscentPcMw(), SCIPStpHeurTMRunLP(), sep_2cut(), and sep_flow().

SCIPprobdataGetNLayers()

int SCIPprobdataGetNLayers

(

SCIP *

scip

)

returns the number of layers

Parameters

scip	SCIP data structure

Definition at line 2424 of file probdata_stp.c.

References NULL, and SCIPgetProbData().

SCIPprobdataGetNEdges()

int SCIPprobdataGetNEdges

(

SCIP *

scip

)

returns the number of edges

Parameters

scip	SCIP data structure

Definition at line 2439 of file probdata_stp.c.

References NULL, and SCIPgetProbData().

Referenced by SCIP_DECL_PRICERINIT(), and SCIP_DECL_PRICERINITSOL().

SCIPprobdataGetNTerms()

int SCIPprobdataGetNTerms

(

SCIP *

scip

)

returns the number of terminals

Parameters

scip	SCIP data structure

Definition at line 2454 of file probdata_stp.c.

References NULL, and SCIPgetProbData().

SCIPprobdataGetRNTerms()

int SCIPprobdataGetRNTerms

(

SCIP *

scip

)

returns the number of terminals without the root node

Parameters

scip	SCIP data structure

Definition at line 2469 of file probdata_stp.c.

References NULL, and SCIPgetProbData().

Referenced by SCIP_DECL_PRICERINIT(), and SCIP_DECL_PRICERINITSOL().

SCIPprobdataGetRoot()

int SCIPprobdataGetRoot

(

SCIP *

scip

)

returns root

Parameters

scip	SCIP data structure

Definition at line 2484 of file probdata_stp.c.

References NULL, SCIPgetProbData(), and GRAPH::source.

Referenced by SCIP_DECL_PRICERINIT().

SCIPprobdataGetNorgEdges()

int SCIPprobdataGetNorgEdges

(

SCIP *

scip

)

returns numer of original edges

Parameters

scip	SCIP data structure

Definition at line 2503 of file probdata_stp.c.

References NULL, and SCIPgetProbData().

Referenced by SCIPintListNodeAppendCopy().

SCIPprobdataGetOffset()

SCIP_Real SCIPprobdataGetOffset

(

SCIP *

scip

)

returns offset of the problem

Parameters

scip	SCIP data structure

Definition at line 2518 of file probdata_stp.c.

References NULL, and SCIPgetProbData().

Referenced by reduce_daSlackPruneMw(), SCIP_DECL_HEUREXEC(), SCIP_DECL_READERWRITE(), SCIPStpDualAscentPcMw(), SCIPStpHeurSlackPruneRun(), and SCIPStpHeurSlackPruneRunPcMw().

SCIPprobdataGetedgeVarByIndex()

SCIP_VAR* SCIPprobdataGetedgeVarByIndex	(	SCIP *	scip,
		int	idx
	)

returns the variable for a given index

Parameters

scip	SCIP data structure
idx	index of the edge

Definition at line 2534 of file probdata_stp.c.

References NULL, and SCIPgetProbData().

SCIPprobdataGetXval()

SCIP_Real* SCIPprobdataGetXval	(	SCIP *	scip,
		SCIP_SOL *	sol
	)

returns the LP solution values

Parameters

scip	SCIP data structure
sol	solution to get values from

Definition at line 2551 of file probdata_stp.c.

References NULL, SCIP_CALL_ABORT, SCIP_Real, SCIPgetProbData(), and SCIPgetSolVals().

Referenced by SCIP_DECL_CONSCHECK(), SCIP_DECL_CONSENFOLP(), SCIP_DECL_CONSENFOPS(), SCIP_DECL_HEUREXEC(), SCIPStpHeurTMRunLP(), sep_2cut(), and sep_flow().

SCIPprobdataGetEdgeConstraints()

SCIP_CONS** SCIPprobdataGetEdgeConstraints

(

SCIP *

scip

)

returns all edge constraints

Parameters

scip	SCIP data structure

Definition at line 2579 of file probdata_stp.c.

References NULL, and SCIPgetProbData().

Referenced by SCIP_DECL_PRICERINIT().

SCIPprobdataGetPathConstraints()

SCIP_CONS** SCIPprobdataGetPathConstraints

(

SCIP *

scip

)

returns all path constraints

Parameters

scip	SCIP data structure

Definition at line 2593 of file probdata_stp.c.

References NULL, and SCIPgetProbData().

Referenced by SCIP_DECL_PRICERINIT().

SCIPprobdataGetRTerms()

int* SCIPprobdataGetRTerms

(

SCIP *

scip

)

returns the array with all variables

Parameters

scip	SCIP data structure

Definition at line 2608 of file probdata_stp.c.

References NULL, and SCIPgetProbData().

Referenced by SCIP_DECL_PRICERINIT().

SCIPprobdataGetEdgeVars()

SCIP_VAR** SCIPprobdataGetEdgeVars

(

SCIP *

scip

)

returns the array with all edge variables

Parameters

scip	SCIP data structure

Definition at line 2623 of file probdata_stp.c.

References NULL, and SCIPgetProbData().

Referenced by branchOnVertex(), buildsolgraph(), selectBranchingVertexByLp(), and selectBranchingVertexByLp2Flow().

SCIPprobdataIsBigt()

SCIP_Bool SCIPprobdataIsBigt

(

SCIP *

scip

)

returns if 'T' model is being used

Parameters

scip	SCIP data structure

Definition at line 2638 of file probdata_stp.c.

References NULL, and SCIPgetProbData().

Referenced by SCIP_DECL_PRICERINIT().

SCIPprobdataPrintGraph()

SCIP_RETCODE SCIPprobdataPrintGraph	(	SCIP *	scip,
		const char *	filename,
		SCIP_SOL *	sol,
		SCIP_Bool	printsol
	)

print (undirected) graph in GML format

Parameters

scip	SCIP data structure
filename	name of the output file
sol	solution to be printed; or NULL for LP solution
printsol	should solution be printed?

Definition at line 2653 of file probdata_stp.c.

References FALSE, NULL, probdataPrintGraph(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetProbData(), SCIPgetSolVal(), SCIPisZero(), and TRUE.

Referenced by pricing().

SCIPprobdataWriteIntermediateSolution()

SCIP_RETCODE SCIPprobdataWriteIntermediateSolution

(

SCIP *

scip

)

writes the best solution to the intermediate solution file

Parameters

scip	SCIP data structure

Definition at line 2697 of file probdata_stp.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPgetProbData(), and SCIPprobdataWriteSolution().

Referenced by SCIP_DECL_EVENTEXEC().

SCIPprobdataWriteStp()

void SCIPprobdataWriteStp	(	SCIP *	scip,
		const GRAPH *	graph,
		const char *	filename
	)

writes SPG (no variant!) to a file

Parameters

scip	SCIP data structure
graph	graph data structure
filename	file name

Definition at line 2713 of file probdata_stp.c.

References GRAPH::cost, GRAPH::edges, GRAPH::head, Is_term, GRAPH::knots, NULL, GRAPH::tail, GRAPH::term, and GRAPH::terms.

SCIPprobdataWriteSolution()

SCIP_RETCODE SCIPprobdataWriteSolution	(	SCIP *	scip,
		FILE *	file
	)

writes the best solution to a file

Parameters

scip	SCIP data structure
file	file to write best solution to; or NULL, to write to stdout

Definition at line 2753 of file probdata_stp.c.

References GRAPH::ancestors, EAT_LAST, GRAPH::edges, FALSE, GRAPH::fixedges, flipedge, graph_edge_add(), graph_free(), graph_grid_coordinates(), graph_init(), graph_knot_add(), graph_sol_markPcancestors(), GRAPH::grid_coordinates, GRAPH::grid_dim, GRAPH::grid_ncoords, GRAPH::head, Int_List_Node::index, Is_term, GRAPH::knots, GRAPH::mark, GRAPH::norgmodelknots, NULL, GRAPH::oeat, GRAPH::orgedges, GRAPH::orghead, GRAPH::orgknots, GRAPH::orgsource, GRAPH::orgtail, GRAPH::outbeg, Int_List_Node::parent, GRAPH::pcancestors, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetProbData(), SCIPgetSolVal(), SCIPinfoMessage(), SCIPisZero(), SCIPprobdataWriteLogLine(), SCIPqueueCreate(), SCIPqueueFree(), SCIPqueueInsert(), SCIPqueueIsEmpty(), SCIPqueueRemove(), GRAPH::source, STP_DCSTP, STP_DHCSTP, STP_GSTP, STP_MWCSP, STP_NWSPG, STP_PCSPG, STP_RMWCSP, STP_RPCSPG, STP_RSMT, STP_SAP, STP_SPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and updateorgsol().

Referenced by SCIP_DECL_PROBEXITSOL(), SCIPprobdataWriteIntermediateSolution(), and SCIPprobdataWriteLogfileEnd().

SCIPprobdataWriteLogLine()

void SCIPprobdataWriteLogLine	(	SCIP *	scip,
		const char *	formatstr,
			...
	)

writes a line to the log file

Parameters

scip	SCIP data structure
formatstr	format string like in printf() function

Definition at line 3124 of file probdata_stp.c.

References SCIP_Messagehdlr::logfile, NULL, SCIPgetMessagehdlr(), SCIPgetProbData(), and SCIPmessageVFPrintInfo().

Referenced by SCIP_DECL_EVENTEXEC(), SCIP_DECL_PROBEXITSOL(), SCIPprobdataCreate(), SCIPprobdataWriteLogfileEnd(), and SCIPprobdataWriteSolution().

SCIPprobdataAddNewSol()

SCIP_RETCODE SCIPprobdataAddNewSol	(	SCIP *	scip,
		SCIP_Real *	nval,
		SCIP_SOL *	sol,
		SCIP_HEUR *	heur,
		SCIP_Bool *	success
	)

add new solution

Parameters

scip	SCIP data structure
nval	array [0..nvars], nval[v] = 1 if node v is in the solution, nval[v] = 0 if not
sol	the new solution
heur	heuristic data
success	denotes whether the new solution has been successfully added

Definition at line 3153 of file probdata_stp.c.

References BMSclearMemoryArray, GRAPH::cost, EAT_LAST, shortest_path::edge, FALSE, FSP_MODE, graph_path_exec(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::mark, MODE_CUT, MODE_FLOW, MODE_PRICE, NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPaddCoefLinear(), SCIPaddSolFree(), SCIPaddVar(), SCIPallocMemoryArray, SCIPcheckSol(), SCIPcheckSolOrig(), SCIPcreateOrigSol(), SCIPcreateSol(), SCIPcreateVarBasic(), SCIPdebugMessage, SCIPfreeMemoryArrayNull, SCIPfreeSol(), SCIPgetNOrigVars(), SCIPgetOrigVars(), SCIPgetProbData(), SCIPgetSolVal(), SCIPinfinity(), SCIPisEQ(), SCIPisGT(), SCIPisZero(), SCIPreleaseVar(), SCIPsetSolVal(), SCIPsetSolVals(), SCIPsnprintf(), SCIPsolGetHeur(), SCIPtrySolFree(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), SCIPvarIsActive(), GRAPH::source, STP_MWCSP, STP_PCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, and TRUE.

Referenced by SCIP_DECL_HEUREXEC(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurRecRun(), and selectBranchingVertexBySol().

SCIPprobdataPrintGraph2()

SCIP_RETCODE SCIPprobdataPrintGraph2	(	const GRAPH *	graph,
		const char *	filename,
		SCIP_Bool *	edgemark
	)

print graph (in undirected form) in GML format with given edges highlighted

Parameters

graph	Graph to be printed
filename	Name of the output file
edgemark	Array of (undirected) edges to highlight

Definition at line 3429 of file probdata_stp.c.

References GRAPH::cost, EAT_FREE, GRAPH::edges, FALSE, GRAPH::head, GRAPH::knots, GRAPH::mark, NULL, GRAPH::oeat, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPgmlWriteClosing(), SCIPgmlWriteEdge(), SCIPgmlWriteNode(), SCIPgmlWriteOpening(), SCIPsnprintf(), GRAPH::source, GRAPH::tail, GRAPH::term, and TRUE.

SCIPprobdataGetType()

int SCIPprobdataGetType

(

SCIP *

scip

)

returns problem type

Parameters

scip	SCIP data structure

Definition at line 3499 of file probdata_stp.c.

References NULL, and SCIPgetProbData().

Referenced by SCIP_DECL_EVENTEXEC(), and SCIPintListNodeAppendCopy().

SCIPprobdataWriteLogfileEnd()

SCIP_RETCODE SCIPprobdataWriteLogfileEnd

(

SCIP *

scip

)

writes end of log file

Parameters

scip	SCIP data structure

Definition at line 3514 of file probdata_stp.c.

References NULL, SCIP_CALL, SCIP_FILECREATEERROR, SCIP_OKAY, SCIP_Real, SCIPerrorMessage, SCIPgetDualbound(), SCIPgetNSols(), SCIPgetPrimalbound(), SCIPgetProbData(), SCIPgetTotalTime(), SCIPprobdataWriteLogLine(), SCIPprobdataWriteSolution(), STP_MWCSP, and STP_RMWCSP.

Referenced by SCIP_DECL_DIALOGEXEC().

SCIPprobdataSetDualBound()

void SCIPprobdataSetDualBound	(	SCIP *	scip,
		SCIP_Real	dual
	)

writes end of log file

Parameters

scip	SCIP data structure
dual	dual bound

Definition at line 3575 of file probdata_stp.c.

References NULL, SCIPgetProbData(), and TRUE.

SCIPprobdataSetNSolvers()

void SCIPprobdataSetNSolvers	(	SCIP *	scip,
		int	nSolvers
	)

writes end of log file

Parameters

scip	SCIP data structure
nSolvers	the number of solvers

Definition at line 3590 of file probdata_stp.c.

References NULL, and SCIPgetProbData().

initReceivedSubproblem()

void initReceivedSubproblem	(	SCIP *	scip,
		const int	lLinearConsNames,
		const char *	linearConsNames,
		const int	lSetppcConsNames,
		const char *	setppcConsNames
	)

branching information from UG

Parameters

scip	SCIP data structure
lLinearConsNames	number of linear constraints
linearConsNames	linear constraints string
lSetppcConsNames	number of setppc constraints
setppcConsNames	number of setppc constraints

Definition at line 3604 of file probdata_stp.c.

References BLOCKED, BRANCH_STP_VERTEX_KILLED, BRANCH_STP_VERTEX_TERM, GRAPH::cost, EAT_LAST, FALSE, flipedge, graph_copy(), graph_free(), graph_init_history(), graph_knot_chg(), graph_mincut_exit(), graph_mincut_init(), graph_path_exit(), graph_path_init(), GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, MODE_CUT, nnodes, NULL, SCIP_CALL_ABORT, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPgetProbData(), SCIPprobdataGetGraph(), SCIPStpBranchruleInitNodeState(), STPStpBranchruleParseConsname(), GRAPH::term, and TRUE.