Detailed Description

propagator for Steiner tree problems, using the LP reduced costs

Author: Daniel Rehfeldt

This propagator makes use of the reduced cost of an optimally solved LP relaxation to propagate the variables, see "SCIP-Jack - A solver for STP and variants with parallelization extensions" by Gamrath, Koch, Maher, Rehfeldt and Shinano

Definition in file prop_stp.h.

#include <stdio.h>
#include <stdlib.h>
#include "scip/scip.h"
#include "graph.h"
#include "probdata_stp.h"

Go to the source code of this file.

Functions
SCIP_RETCODE	SCIPincludePropStp (SCIP *scip)

SCIP_RETCODE	SCIPStpFixEdgeVarTo0 (SCIP scip, SCIP_VAR edgevar, SCIP_Bool *success)

SCIP_RETCODE	SCIPStpFixEdgeVarTo1 (SCIP scip, SCIP_VAR edgevar, SCIP_Bool *success)

int	SCIPStpNfixedEdges (SCIP *scip)

SCIP_RETCODE	SCIPStpPropCheckForInfeas (SCIP scip, SCIP_Bool probisinfeas)

SCIP_RETCODE	SCIPStpPropGetGraph (SCIP scip, GRAPH graph, SCIP_Longint graphnodenumber, SCIP_Bool probisinfeas, SCIP_Real offset)

const SCIP_Bool *	SCIPStpPropGet2BoundedArr (SCIP *scip)

Function Documentation

◆ SCIPincludePropStp()

SCIP_RETCODE SCIPincludePropStp ( SCIP * scip )

creates the stp propagator and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 2610 of file prop_stp.c.

References DEFAULT_MAXNWAITINGROUNDS, FALSE, NULL, PROP_DELAY, PROP_DESC, PROP_FREQ, PROP_NAME, PROP_PRIORITY, PROP_TIMING, SCIP_CALL, SCIP_OKAY, SCIPaddBoolParam(), SCIPaddIntParam(), SCIPallocMemory, SCIPcreateRandom(), SCIPincludePropBasic(), SCIPsetPropCopy(), SCIPsetPropExitsol(), SCIPsetPropFree(), SCIPsetPropInitsol(), and TRUE.

Referenced by runShell(), SCIP_DECL_PROPCOPY(), and subscipSetupCallbacks().

◆ SCIPStpFixEdgeVarTo0()

SCIP_RETCODE SCIPStpFixEdgeVarTo0	(	SCIP *	scip,
		SCIP_VAR *	edgevar,
		SCIP_Bool *	success
	)

fix a variable (corresponding to an edge) to 0

Parameters

scip	SCIP data structure
edgevar	the variable to be fixed
success	could variable be fixed?

Definition at line 2419 of file prop_stp.c.

References FALSE, SCIP_CALL, SCIP_OKAY, SCIPchgVarUb(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.

Referenced by reduce_boundHopRc(), and subsolFixOrgEdges().

◆ SCIPStpFixEdgeVarTo1()

SCIP_RETCODE SCIPStpFixEdgeVarTo1	(	SCIP *	scip,
		SCIP_VAR *	edgevar,
		SCIP_Bool *	success
	)

fix a variable (corresponding to an edge) to 1

Parameters

scip	SCIP data structure
edgevar	the variable to be fixed
success	could variable be fixed?

Definition at line 2443 of file prop_stp.c.

References FALSE, SCIP_CALL, SCIP_OKAY, SCIPchgVarLb(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.

Referenced by subsolFixOrgEdges().

◆ SCIPStpNfixedEdges()

int SCIPStpNfixedEdges ( SCIP * scip )

return total number of arcs fixed by 'fixedgevar' method of this propagator

Parameters

scip	SCIP data structure

Definition at line 2467 of file prop_stp.c.

References NULL, SCIPfindProp(), and SCIPpropGetData().

Referenced by abortSlackPruneEarly(), and SCIP_DECL_HEUREXEC().

◆ SCIPStpPropCheckForInfeas()

SCIP_RETCODE SCIPStpPropCheckForInfeas	(	SCIP *	scip,
		SCIP_Bool *	probisinfeas
	)

checks whether problem has become infeasible at current node

checks whether problem has become infeasible at current node NOTE: we basically check whether all terminals (at given B&B node) are reachable from root, taking bound changes into account

Parameters