reduce_bnd.c File Reference

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

Go to the source code of this file.

Macros
#define	DEFAULT_HEURRUNS   100
#define	DEFAULT_DARUNS   5

Functions
static void	compTMstarts (GRAPH *graph, int *starts, unsigned int *seed, int runs)
SCIP_RETCODE	da_reduce (SCIP *scip, GRAPH *graph, PATH *vnoi, GNODE **gnodearr, SCIP_Real *cost, SCIP_Real *costrev, SCIP_Real *pathdist, int *edgearrint, int *vbase, int *pathedge, int *state, int *heursources, char *nodearrchar, int *nelims)
SCIP_RETCODE	daPc_reduce (SCIP *scip, GRAPH *graph, PATH *vnoi, GNODE **gnodearr, SCIP_Real *cost, SCIP_Real *costrev, SCIP_Real *pathdist, int *vbase, int *pathedge, int *edgearrint, int *state, char *nodearrchar, int *nelims)
SCIP_RETCODE	bound_reduce (SCIP *scip, GRAPH *graph, PATH *vnoi, SCIP_Real *cost, SCIP_Real *prize, SCIP_Real *radius, SCIP_Real *costrev, SCIP_Real *offset, SCIP_Real *upperbound, int *heap, int *state, int *vbase, int *nelims)
SCIP_RETCODE	hopbound_reduce (SCIP *scip, GRAPH *graph, PATH *vnoi, SCIP_Real *cost, SCIP_Real *radius, SCIP_Real *costrev, int *heap, int *state, int *vbase, int *nelims)
SCIP_RETCODE	hcrbound_reduce (SCIP *scip, GRAPH *graph, PATH *vnoi, SCIP_Real *cost, SCIP_Real *costrev, SCIP_Real *pathdist, int *heap, int *state, int *vbase, int *nelims, int *pathedge)
SCIP_RETCODE	hcrcbound_reduce (SCIP *scip, GRAPH *graph, PATH *vnoi, SCIP_Real *cost, SCIP_Real *costrev, SCIP_Real *pathdist, SCIP_Real objval, int *heap, int *state, int *vbase, int *nelims, int *pathedge, SCIP_Bool fix)

Macro Definition Documentation

#define DEFAULT_DARUNS   5

number of runs for dual ascent heuristic

Definition at line 43 of file reduce_bnd.c.

Referenced by da_reduce().

#define DEFAULT_HEURRUNS   100

number of runs of constructive heuristic

Definition at line 42 of file reduce_bnd.c.

Referenced by da_reduce(), and daPc_reduce().

Function Documentation

SCIP_RETCODE bound_reduce	(	SCIP *	scip,
		GRAPH *	graph,
		PATH *	vnoi,
		SCIP_Real *	cost,
		SCIP_Real *	prize,
		SCIP_Real *	radius,
		SCIP_Real *	costrev,
		SCIP_Real *	offset,
		SCIP_Real *	upperbound,
		int *	heap,
		int *	state,
		int *	vbase,
		int *	nelims
	)

bound-based reductions for the (R)PCSTP, the MWCSP and the STP

Definition at line 845 of file reduce_bnd.c.

References GRAPH::ancestors, BLOCKED, compTMstarts(), CONNECT, GRAPH::cost, DEFAULT_HOPFACTOR, deleteterm(), shortest_path::dist, EAT_LAST, shortest_path::edge, Edge_anti, GRAPH::edges, FALSE, FARAWAY, flipedge, get2next(), get3next(), get4next(), getnext4tterms(), GRAPH::grad, graph_edge_del(), graph_edge_reinsert(), graph_free(), graph_init(), graph_knot_chg(), graph_path_exec(), graph_path_exit(), graph_path_init(), GRAPH::head, Is_pterm, Is_term, GRAPH::knots, GRAPH::mark, MST_MODE, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_state, pcgraphorg(), pcgraphtrans(), GRAPH::prize, SCIPheurComputeSteinerTree(), SCIPintListNodeAppendCopy(), SCIPintListNodeFree(), GRAPH::source, STP_HOP_CONS, STP_MAX_NODE_WEIGHT, STP_PRIZE_COLLECTING, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, UNKNOWN, and voronoi_radius().

Referenced by reduceHc(), reduceMwcs(), reducePc(), and reduceStp().

static void compTMstarts ( GRAPH *  graph, int *  starts, unsigned int *  seed, int  runs  )

static

compute starting points for constructive heuristics

Parameters

graph	graph data structure
starts	starting points array
seed	random seed
runs	number of runs

Definition at line 140 of file reduce_bnd.c.

References EAT_LAST, GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, GRAPH::outbeg, GRAPH::source, GRAPH::term, and GRAPH::terms.

Referenced by bound_reduce(), and da_reduce().

SCIP_RETCODE da_reduce	(	SCIP *	scip,
		GRAPH *	graph,
		PATH *	vnoi,
		GNODE **	gnodearr,
		SCIP_Real *	cost,
		SCIP_Real *	costrev,
		SCIP_Real *	pathdist,
		int *	edgearrint,
		int *	vbase,
		int *	pathedge,
		int *	state,
		int *	heursources,
		char *	nodearrchar,
		int *	nelims
	)

dual ascent based reductions

Parameters

scip	SCIP data structure
graph	graph data structure
vnoi	Voronoi data structure
gnodearr	GNODE* terminals array for internal computations or NULL
cost	edge costs
costrev	reverse edge costs
pathdist	distance array for shortest path calculations
edgearrint	int edges array for internal computations or NULL
vbase	array for Voronoi bases
pathedge	array for predecessor edge on a path
state	int 4 * nnodes array for internal computations
heursources	array to store starting points of TM heuristic
nodearrchar	char node array for internal computations or NULL
nelims	pointer to store number of reduced edges

Definition at line 202 of file reduce_bnd.c.

References GRAPH::ancestors, BLOCKED, compTMstarts(), CONNECT, GRAPH::cost, DEFAULT_DARUNS, DEFAULT_HEURRUNS, DEFAULT_HOPFACTOR, shortest_path::dist, EAT_LAST, Edge_anti, GRAPH::edges, extendSteinerTreePcMw(), FALSE, FARAWAY, flipedge, getnext4terms(), GRAPH::grad, graph_edge_del(), graph_edge_reinsert(), graph_path_execX(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, pcgraphorg(), pcgraphtrans(), SCIPdualAscentStp(), SCIPheurComputeSteinerTree(), SCIPintListNodeAppendCopy(), SCIPintListNodeFree(), GRAPH::source, STP_HOP_CONS, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by reduceHc(), reducePc(), and reduceStp().

SCIP_RETCODE daPc_reduce	(	SCIP *	scip,
		GRAPH *	graph,
		PATH *	vnoi,
		GNODE **	gnodearr,
		SCIP_Real *	cost,
		SCIP_Real *	costrev,
		SCIP_Real *	pathdist,
		int *	vbase,
		int *	pathedge,
		int *	edgearrint,
		int *	state,
		char *	nodearrchar,
		int *	nelims
	)

dual ascent based reductions for PCSPG and MWCSP

Parameters

scip	SCIP data structure
graph	graph data structure
vnoi	Voronoi data structure array
gnodearr	GNODE* terminals array for internal computations or NULL
cost	edge costs
costrev	reverse edge costs
pathdist	distance array for shortest path calculations
vbase	Voronoi base array
pathedge	shorest path incoming edge array for shortest path calculations
edgearrint	int edges array for internal computations or NULL
state	int 4 * vertices array
nodearrchar	char node array for internal computations
nelims	pointer to store number of reduced edges

Definition at line 577 of file reduce_bnd.c.

References CONNECT, GRAPH::cost, DEFAULT_HEURRUNS, DEFAULT_HOPFACTOR, shortest_path::dist, EAT_LAST, GRAPH::edges, extendSteinerTreePcMw(), FALSE, FARAWAY, flipedge, GRAPH::grad, graph_edge_del(), graph_free(), graph_init_history(), graph_path_execX(), graph_path_exit(), graph_path_init(), graph_PcSapCopy(), GRAPH::head, Is_gterm, Is_term, GRAPH::knots, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, pcgraphorg(), pcgraphtrans(), SCIPdualAscentStp(), SCIPheurComputeSteinerTree(), SCIPintListNodeFree(), GRAPH::source, GRAPH::term, GRAPH::terms, TRUE, UNKNOWN, and voronoi_terms().

Referenced by reduceMwcs(), and reducePc().

SCIP_RETCODE hcrbound_reduce	(	SCIP *	scip,
		GRAPH *	graph,
		PATH *	vnoi,
		SCIP_Real *	cost,
		SCIP_Real *	costrev,
		SCIP_Real *	pathdist,
		int *	heap,
		int *	state,
		int *	vbase,
		int *	nelims,
		int *	pathedge
	)

hop bound-based reduction test for the HCDSTP

Definition at line 1750 of file reduce_bnd.c.

References GRAPH::cost, shortest_path::dist, EAT_LAST, GRAPH::edges, FARAWAY, flipedge, GRAPH::grad, graph_edge_del(), graph_path_execX(), graph_valid(), GRAPH::head, GRAPH::hoplimit, Is_term, GRAPH::knots, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, GRAPH::source, GRAPH::term, TRUE, and voronoi_terms().

Referenced by reduceHc().

SCIP_RETCODE hcrcbound_reduce	(	SCIP *	scip,
		GRAPH *	graph,
		PATH *	vnoi,
		SCIP_Real *	cost,
		SCIP_Real *	costrev,
		SCIP_Real *	pathdist,
		SCIP_Real	objval,
		int *	heap,
		int *	state,
		int *	vbase,
		int *	nelims,
		int *	pathedge,
		SCIP_Bool	fix
	)

Definition at line 1878 of file reduce_bnd.c.

References BLOCKED, CONNECT, GRAPH::cost, DEFAULT_HOPFACTOR, shortest_path::dist, EAT_LAST, GRAPH::edges, FARAWAY, fixedgevar(), flipedge, GRAPH::grad, graph_edge_del(), graph_path_execX(), graph_valid(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, SCIPheurComputeSteinerTree(), SCIPprobdataGetVars(), GRAPH::source, GRAPH::term, TRUE, UNKNOWN, and voronoi_terms().

Referenced by reduceHc(), and SCIP_DECL_EVENTEXEC().

SCIP_RETCODE hopbound_reduce	(	SCIP *	scip,
		GRAPH *	graph,
		PATH *	vnoi,
		SCIP_Real *	cost,
		SCIP_Real *	radius,
		SCIP_Real *	costrev,
		int *	heap,
		int *	state,
		int *	vbase,
		int *	nelims
	)

bound-based reduction test for the HCDSTP

Definition at line 1552 of file reduce_bnd.c.

References CONNECT, GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, GRAPH::edges, FARAWAY, flipedge, get2next(), GRAPH::grad, graph_edge_del(), graph_free(), graph_init(), graph_knot_chg(), graph_path_exec(), graph_path_exit(), graph_path_init(), graph_valid(), GRAPH::head, GRAPH::hoplimit, Is_term, GRAPH::knots, GRAPH::mark, MST_MODE, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_state, GRAPH::source, GRAPH::tail, GRAPH::term, TRUE, and voronoi_radius().

Referenced by reduceHc().