probdata_stp.h File Reference

Detailed Description

Problem data for stp problem.

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

#include "scip/scip.h"
#include "grph.h"

Go to the source code of this file.

Functions
SCIP_RETCODE	SCIPprobdataCreate (SCIP *scip, const char *filename)
void	SCIPprobdataSetGraph (SCIP_PROBDATA *probdata, GRAPH *graph)
GRAPH *	SCIPprobdataGetGraph (SCIP_PROBDATA *probdata)
void	SCIPprobdataSetOffset (SCIP_PROBDATA *probdata, SCIP_Real offset)
SCIP_VAR **	SCIPprobdataGetVars (SCIP *scip)
SCIP_VAR **	SCIPprobdataGetEdgeVars (SCIP *scip)
int *	SCIPprobdataGetRTerms (SCIP *scip)
int	SCIPprobdataGetNLayers (SCIP *scip)
int	SCIPprobdataGetNVars (SCIP *scip)
int	SCIPprobdataGetNTerms (SCIP *scip)
int	SCIPprobdataGetRNTerms (SCIP *scip)
int	SCIPprobdataGetRoot (SCIP *scip)
int	SCIPprobdataGetNEdges (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)
SCIP_RETCODE	SCIPprobdataPrintGraph (SCIP *scip, const char *filename, SCIP_SOL *sol, SCIP_Bool printsol)
SCIP_RETCODE	SCIPprobdataPrintGraph2 (const GRAPH *graph, const char *filename, SCIP_Bool *edgemark)
SCIP_Bool	SCIPprobdataIsBigt (SCIP *scip)
SCIP_RETCODE	SCIPprobdataWriteIntermediateSolution (SCIP *scip)
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)
void	SCIPprobdataSetDualBound (SCIP *scip, SCIP_Real dual)
void	SCIPprobdataSetNSolvers (SCIP *scip, int nSolvers)
int	SCIPprobdataGetType (SCIP *scip)
SCIP_RETCODE	SCIPprobdataWriteLogfileEnd (SCIP *scip)

Function Documentation

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 2934 of file probdata_stp.c.

References GRAPH::cost, EAT_LAST, shortest_path::edge, SCIP_ProbData::edgevars, FALSE, FSP_MODE, SCIP_ProbData::graph, graph_path_exec(), GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::mark, MODE_CUT, MODE_FLOW, MODE_PRICE, SCIP_ProbData::nedges, SCIP_ProbData::nvars, SCIP_ProbData::realnterms, GRAPH::source, STP_MAX_NODE_WEIGHT, STP_PRIZE_COLLECTING, GRAPH::stp_type, GRAPH::tail, GRAPH::term, and TRUE.

Referenced by SCIP_DECL_HEUREXEC().

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

sets up the problem data

Parameters

scip	SCIP data structure
filename	file name

Definition at line 1847 of file probdata_stp.c.

References CENTER_DEG, central_terminal(), CONS_ALWAYS, CONS_SPECIFIC, createConstraints(), createDegreeConstraints(), createHopConstraint(), createPrizeConstraints(), createVariables(), CYC_CONS_LIMIT, GRAPH::edges, FALSE, presolve_info::fixed, SCIP_ProbData::graph, graph_load(), graph_mincut_init(), graph_pack(), graph_path_init(), Is_term, GRAPH::knots, GRAPH::layers, SCIP_ProbData::mode, MODE_CUT, MODE_FLOW, MODE_PRICE, SCIP_ProbData::nedges, SCIP_ProbData::nnodes, SCIP_ProbData::offset, GRAPH::orgedges, GRAPH::orgknots, probdataCreate(), probdataPrintGraph(), SCIP_ProbData::realnterms, reduce(), SCIPcreateConsStp(), SCIPdualAscentAddCutsStp(), SCIPdualAscentPcStp(), SCIPdualAscentStp(), SCIPprobdataWriteLogLine(), GRAPH::source, STP_DEG_CONS, STP_DIRECTED, STP_GRID, STP_HOP_CONS, STP_MAX_NODE_WEIGHT, STP_NODE_WEIGHTS, STP_OBSTACLES_GRID, STP_PRIZE_COLLECTING, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, STP_UNDIRECTED, SYM_CONS_LIMIT, GRAPH::term, GRAPH::terms, and TRUE.

Referenced by SCIP_DECL_READERREAD().

SCIP_CONS** SCIPprobdataGetEdgeConstraints

(

SCIP *

scip

)

returns all edge constraints

Parameters

scip	SCIP data structure

Definition at line 2452 of file probdata_stp.c.

Referenced by SCIP_DECL_PRICERINIT().

SCIP_VAR* SCIPprobdataGetedgeVarByIndex	(	SCIP *	scip,
		int	idx
	)

returns the edge variable for a given index

returns the variable for a given index

Parameters

scip	SCIP data structure
idx	index of the edge

Definition at line 2407 of file probdata_stp.c.

SCIP_VAR** SCIPprobdataGetEdgeVars

(

SCIP *

scip

)

returns the array with all edge variables

Parameters

scip	SCIP data structure

Definition at line 2496 of file probdata_stp.c.

Referenced by buildsolgraph(), SCIP_DECL_BRANCHEXECLP(), and selectBranchingVertex().

GRAPH* SCIPprobdataGetGraph

(

SCIP_PROBDATA *

probdata

)

returns the graph

Parameters

probdata

problem data

Definition at line 2258 of file probdata_stp.c.

Referenced by pricing(), SCIP_DECL_BRANCHEXECLP(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSINITLP(), SCIP_DECL_CONSINITSOL(), SCIP_DECL_CONSPROP(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_HEUREXEC(), SCIP_DECL_HEURINIT(), SCIP_DECL_PROPEXEC(), SCIP_DECL_READERREAD(), SCIP_DECL_READERWRITE(), and selectBranchingVertex().

int SCIPprobdataGetNEdges

(

SCIP *

scip

)

returns the number of edges

Parameters

scip	SCIP data structure

Definition at line 2326 of file probdata_stp.c.

Referenced by SCIP_DECL_PRICERINIT(), and SCIP_DECL_PRICERINITSOL().

int SCIPprobdataGetNLayers

(

SCIP *

scip

)

returns the number of layers

Parameters

scip	SCIP data structure

Definition at line 2311 of file probdata_stp.c.

int SCIPprobdataGetNTerms

(

SCIP *

scip

)

returns the number of terminals

Parameters

scip	SCIP data structure

Definition at line 2341 of file probdata_stp.c.

int SCIPprobdataGetNVars

(

SCIP *

scip

)

returns the number of vars

returns the number of variables

Parameters

scip	SCIP data structure

Definition at line 2281 of file probdata_stp.c.

Referenced by SCIP_DECL_CONSLOCK(), and SCIP_DECL_HEUREXEC().

SCIP_Real SCIPprobdataGetOffset

(

SCIP *

scip

)

returns the offset

returns offset of the problem

Parameters

scip	SCIP data structure

Definition at line 2391 of file probdata_stp.c.

Referenced by SCIP_DECL_EVENTEXEC(), SCIP_DECL_HEUREXEC(), SCIP_DECL_READERWRITE(), and SCIPdualAscentPcStp().

SCIP_CONS** SCIPprobdataGetPathConstraints

(

SCIP *

scip

)

returns all path constraints

Parameters

scip	SCIP data structure

Definition at line 2466 of file probdata_stp.c.

Referenced by SCIP_DECL_PRICERINIT().

int SCIPprobdataGetRNTerms

(

SCIP *

scip

)

returns the number of terminals without the root node

Parameters

scip	SCIP data structure

Definition at line 2356 of file probdata_stp.c.

Referenced by SCIP_DECL_PRICERINIT(), and SCIP_DECL_PRICERINITSOL().

int SCIPprobdataGetRoot

(

SCIP *

scip

)

returns root

Parameters

scip	SCIP data structure

Definition at line 2371 of file probdata_stp.c.

References SCIP_ProbData::graph, and GRAPH::source.

Referenced by SCIP_DECL_PRICERINIT().

int* SCIPprobdataGetRTerms

(

SCIP *

scip

)

returns the array with all terminals (without the root)

returns the array with all variables

Parameters

scip	SCIP data structure

Definition at line 2481 of file probdata_stp.c.

Referenced by SCIP_DECL_PRICERINIT().

int SCIPprobdataGetType

(

SCIP *

scip

)

returns problem type

Parameters

scip	SCIP data structure

Definition at line 3287 of file probdata_stp.c.

Referenced by SCIP_DECL_EVENTEXEC().

SCIP_VAR** SCIPprobdataGetVars

(

SCIP *

scip

)

returns the array with all variables

Parameters

scip	SCIP data structure

Definition at line 2296 of file probdata_stp.c.

Referenced by cut_add(), hcrcbound_reduce(), SCIP_DECL_CONSLOCK(), SCIP_DECL_HEUREXEC(), SCIP_DECL_PROPEXEC(), SCIPdualAscentPcStp(), SCIPdualAscentStp(), and sep_flow().

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 2424 of file probdata_stp.c.

References SCIP_ProbData::nedges.

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

SCIP_Bool SCIPprobdataIsBigt

(

SCIP *

scip

)

returns if 'T' model is being used

Parameters

scip	SCIP data structure

Definition at line 2511 of file probdata_stp.c.

Referenced by SCIP_DECL_PRICERINIT().

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

print (undirected) graph

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 2526 of file probdata_stp.c.

References SCIP_ProbData::edgevars, FALSE, probdataPrintGraph(), and TRUE.

Referenced by pricing().

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 3208 of file probdata_stp.c.

References GRAPH::cost, EAT_FREE, GRAPH::edges, FALSE, GRAPH::head, GRAPH::knots, GRAPH::mark, GRAPH::oeat, GRAPH::source, GRAPH::tail, GRAPH::term, and TRUE.

Referenced by SCIPheurImproveSteinerTree(), and sd_red().

void SCIPprobdataSetDualBound	(	SCIP *	scip,
		SCIP_Real	dual
	)

set dual bound by ug

writes end of log file

Parameters

scip	SCIP data structure
dual	dual bound

Definition at line 3363 of file probdata_stp.c.

References TRUE.

void SCIPprobdataSetGraph	(	SCIP_PROBDATA *	probdata,
		GRAPH *	graph
	)

sets the probdata graph

Parameters

probdata	problem data
graph	graph data structure

Definition at line 2246 of file probdata_stp.c.

References SCIP_ProbData::graph.

void SCIPprobdataSetNSolvers	(	SCIP *	scip,
		int	nSolvers
	)

set the number of solvers

writes end of log file

Parameters

scip	SCIP data structure
nSolvers	the number of solvers

Definition at line 3378 of file probdata_stp.c.

References SCIP_ProbData::nSolvers.

void SCIPprobdataSetOffset	(	SCIP_PROBDATA *	probdata,
		SCIP_Real	offset
	)

sets the offset

Parameters

probdata	problem data
offset	the offset value

Definition at line 2269 of file probdata_stp.c.

References SCIP_ProbData::offset.

SCIP_RETCODE SCIPprobdataWriteIntermediateSolution

(

SCIP *

scip

)

writes the best solution to the intermediate solution file

Parameters

scip	SCIP data structure

Definition at line 2570 of file probdata_stp.c.

References SCIPprobdataWriteSolution().

Referenced by SCIP_DECL_EVENTEXEC().

SCIP_RETCODE SCIPprobdataWriteLogfileEnd

(

SCIP *

scip

)

writes end of log file

Parameters

scip	SCIP data structure

Definition at line 3302 of file probdata_stp.c.

References SCIPprobdataWriteLogLine(), SCIPprobdataWriteSolution(), and STP_MAX_NODE_WEIGHT.

Referenced by SCIP_DECL_DIALOGEXEC().

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 2911 of file probdata_stp.c.

Referenced by SCIP_DECL_EVENTEXEC(), SCIP_DECL_PROBEXITSOL(), SCIPprobdataCreate(), SCIPprobdataWriteLogfileEnd(), and 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 2588 of file probdata_stp.c.

References GRAPH::ancestors, GRAPH::edges, SCIP_ProbData::edgevars, FALSE, GRAPH::fixedges, flipedge, SCIP_ProbData::graph, graph_grid_coordinates(), GRAPH::grid_coordinates, GRAPH::grid_dim, GRAPH::grid_ncoords, GSTP, GRAPH::head, Int_List_Node::index, Is_term, GRAPH::norgmodeledges, GRAPH::norgmodelknots, GRAPH::orgedges, GRAPH::orghead, GRAPH::orgknots, GRAPH::orgtail, Int_List_Node::parent, GRAPH::pcancestors, SCIPprobdataWriteLogLine(), GRAPH::source, STP_DEG_CONS, STP_DIRECTED, STP_GRID, STP_HOP_CONS, STP_MAX_NODE_WEIGHT, STP_NODE_WEIGHTS, STP_PRIZE_COLLECTING, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, STP_UNDIRECTED, GRAPH::tail, GRAPH::term, GRAPH::terms, and TRUE.

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