Detailed Description

Methods for loading Steiner problems in .stp format.

Reduction tests for Steiner problems.

Saving routines for Steiner problems.

Author: Thorsten Koch; Daniel Rehfeldt

This file includes methods for reading a Steiner problem in .stp format

A list of all interface methods can be found in grph.h.

Author: Gerald Gamrath; Thorsten Koch; Daniel Rehfeldt

This file includes several saving routines for Steiner problems

A list of all interface methods can be found in grph.h.

Author: Gerald Gamrath; Thorsten Koch; Stephen Maher; Daniel Rehfeldt

This file includes several easy reduction techniques ('degree_test'), bound-based reductions (e.g. 'bound_reduce') and several packages of reduction techniques for different Steiner problem variants.

A list of all interface methods can be found in grph.h.

Definition in file reduce.c.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "grph.h"
#include "heur_tm.h"
#include "misc_stp.h"
#include "scip/scip.h"
#include "probdata_stp.h"
#include "prop_stp.h"

Go to the source code of this file.

Macros
#define	REDUCE_C

#define	SDSP_BOUND 400

#define	BD3_BOUND 400

Functions
static void	setTrue (char **arr, int arrsize)

static SCIP_RETCODE	nvsl_reduction (SCIP scip, GRAPH g, PATH vnoi, SCIP_Real nodearrreal, SCIP_Real fixed, int edgearrint, int heap, int state, int vbase, int neighb, int distnode, char visited, int *nelims, int minelims)

void	level0 (SCIP scip, GRAPH g)

static SCIP_RETCODE	reduceStp (SCIP scip, GRAPH graph, SCIP_Real fixed, int minelims, SCIP_Bool dualascent)

static SCIP_RETCODE	reducePc (SCIP scip, GRAPH graph, SCIP_Real fixed, int minelims, char dualascent)

static SCIP_RETCODE	reduceMwcs (SCIP scip, GRAPH graph, SCIP_Real fixed, int minelims, char dualascent)

static SCIP_RETCODE	reduceHc (SCIP scip, GRAPH graph, SCIP_Real fixed, int minelims)

static SCIP_RETCODE	reduceSap (SCIP scip, GRAPH graph, SCIP_Real fixed, int minelims)

SCIP_RETCODE	reduce (SCIP scip, GRAPH graph, SCIP_Real offset, int level, int minelims)

Macro Definition Documentation

#define BD3_BOUND 400

visited edges bound for BD3 test

Definition at line 35 of file reduce.c.

Referenced by reducePc(), and reduceStp().

#define REDUCE_C

Definition at line 33 of file reduce.c.

#define SDSP_BOUND 400

visited edges bound for SDSP test

Definition at line 34 of file reduce.c.

Referenced by reducePc(), and reduceStp().

Function Documentation

void level0	(	SCIP *	scip,
		GRAPH *	g
	)

Definition at line 791 of file reduce.c.

References EAT_LAST, FALSE, GRAPH::grad, graph_edge_del(), graph_trail(), GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::mark, GRAPH::source, GRAPH::term, and TRUE.

Referenced by ledge_reduction(), reduce(), and reduceMwcs().

static SCIP_RETCODE nvsl_reduction	(	SCIP *	scip,
		GRAPH *	g,
		PATH *	vnoi,
		SCIP_Real *	nodearrreal,
		SCIP_Real *	fixed,
		int *	edgearrint,
		int *	heap,
		int *	state,
		int *	vbase,
		int *	neighb,
		int *	distnode,
		char *	visited,
		int *	nelims,
		int	minelims
	)

static

iterate NV and SL test while at least minelims many contractions are being performed

Definition at line 69 of file reduce.c.

References GRAPH::cost, degree_test(), degree_test_pc(), shortest_path::dist, EAT_FREE, EAT_LAST, shortest_path::edge, Edge_anti, GRAPH::edges, EQ, FALSE, FARAWAY, FSP_MODE, GE, GRAPH::grad, graph_edge_del(), graph_knot_contract(), graph_path_exec(), graph_valid(), GT, GRAPH::head, GRAPH::ieat, Is_term, GRAPH::knots, GRAPH::layers, LE, LT, GRAPH::mark, Max, MST_MODE, nv_reductionAdv(), GRAPH::oeat, GRAPH::outbeg, sl_reduction(), GRAPH::source, STP_PRIZE_COLLECTING, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, GRAPH::tail, GRAPH::term, and TRUE.

Referenced by reducePc(), and reduceStp().

SCIP_RETCODE reduce	(	SCIP *	scip,
		GRAPH **	graph,
		SCIP_Real *	offset,
		int	level,
		int	minelims
	)

reduces the graph

Parameters

scip	SCIP data structure
graph	graph structure
offset	pointer to store offset generated by reductions
level	reduction level 0: none, 1: basic, 2: advanced
minelims	minimal amount of reductions to reiterate reduction methods

Definition at line 1886 of file reduce.c.

References FALSE, graph_init_history(), graph_path_exit(), graph_path_init(), graph_valid(), level0(), reduceHc(), reduceMwcs(), reducePc(), reduceSap(), reduceStp(), STP_DEG_CONS, STP_DIRECTED, STP_HOP_CONS, STP_MAX_NODE_WEIGHT, STP_NODE_WEIGHTS, STP_PRIZE_COLLECTING, STP_ROOTED_PRIZE_COLLECTING, and TRUE.

Referenced by SCIP_DECL_HEUREXEC(), and SCIPprobdataCreate().

static SCIP_RETCODE reduceHc	(	SCIP *	scip,
		GRAPH **	graph,
		SCIP_Real *	fixed,
		int	minelims
	)

static

basic reduction package for the HCDSTP

Parameters

scip	SCIP data structure
graph	graph data structure
fixed	pointer to store the offset value
minelims	minimal number of edges to be eliminated in order to reiterate reductions

Definition at line 1677 of file reduce.c.

References bound_reduce(), da_reduce(), degree_test_hc(), GRAPH::edges, FALSE, hcrbound_reduce(), hcrcbound_reduce(), hopbound_reduce(), GRAPH::knots, and TRUE.

Referenced by reduce().

static SCIP_RETCODE reduceMwcs	(	SCIP *	scip,
		GRAPH **	graph,
		SCIP_Real *	fixed,
		int	minelims,
		char	dualascent
	)

static

reduction package for the MWCSP

Parameters

scip	SCIP data structure
graph	graph data structure
fixed	pointer to store the offset value
minelims	minimal number of edges to be eliminated in order to reiterate reductions
dualascent	perform dual ascent reductions?

Definition at line 1352 of file reduce.c.

References ansadv2Reduction(), ansadvReduction(), ansReduction(), bound_reduce(), chain2Reduction(), cnsAdvReduction(), daPc_reduce(), degree_test_mw(), GRAPH::edges, FALSE, GRAPH::knots, level0(), nnpReduction(), npvReduction(), pcgraphorg(), pcgraphtrans(), GRAPH::prize, setTrue(), GRAPH::terms, and TRUE.

Referenced by reduce().

static SCIP_RETCODE reducePc	(	SCIP *	scip,
		GRAPH **	graph,
		SCIP_Real *	fixed,
		int	minelims,
		char	dualascent
	)

static

basic reduction package for the (R)PCSTP

Parameters

scip	SCIP data structure
graph	graph data structure
fixed	pointer to store the offset value
minelims	minimal number of edges to be eliminated in order to reiterate reductions
dualascent	perform dual ascent reductions?

Definition at line 1118 of file reduce.c.

References BD3_BOUND, bd3_reduction(), bound_reduce(), da_reduce(), daPc_reduce(), degree_test_pc(), GRAPH::edges, FALSE, GRAPH::knots, nvsl_reduction(), pcgraphorg(), pcgraphtrans(), GRAPH::prize, sdpc_reduction(), SDSP_BOUND, sdsp_reduction(), STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, GRAPH::terms, and TRUE.

Referenced by reduce().

static SCIP_RETCODE reduceSap	(	SCIP *	scip,
		GRAPH **	graph,
		SCIP_Real *	fixed,
		int	minelims
	)

static

basic reduction package for the SAP (

Parameters

scip	SCIP data structure
graph	graph data structure
fixed	pointer to store the offset value
minelims	minimal number of edges to be eliminated in order to reiterate reductions

Definition at line 1804 of file reduce.c.

References GRAPH::cost, degree_test_sap(), GRAPH::edges, FALSE, FARAWAY, GRAPH::knots, rptReduction(), sdsp_sap_reduction(), and TRUE.

Referenced by reduce().

static SCIP_RETCODE reduceStp	(	SCIP *	scip,
		GRAPH **	graph,
		SCIP_Real *	fixed,
		int	minelims,
		SCIP_Bool	dualascent
	)

static

basic reduction package for the STP

Parameters

scip	SCIP data structure
graph	graph data structure
fixed	pointer to store the offset value
minelims	minimal number of edges to be eliminated in order to reiterate reductions
dualascent	perform dualascent reductions?

Definition at line 818 of file reduce.c.

References BD3_BOUND, bd3_reduction(), bound_reduce(), da_reduce(), degree_test(), GRAPH::edges, FALSE, GRAPH::knots, ledge_reduction(), nvsl_reduction(), sd_red(), sd_reduction(), SDSP_BOUND, sdsp_reduction(), GRAPH::terms, and TRUE.

Referenced by reduce().

static void setTrue	(	char **	arr,
		int	arrsize
	)

static

set entries of (char) array to FALSE

Definition at line 50 of file reduce.c.

References TRUE.

Referenced by reduceMwcs().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

Function Documentation