# SCIP

Solving Constraint Integer Programs

reduce_alt.c File Reference

## Detailed Description

Altenative based reduction tests for Steiner problems.

This file implements alternative-based reduction techniques for several Steiner problems. All tests can be found in "Combining NP-Hard Reduction Techniques and Strong Heuristics in an Exact Algorithm for the Maximum-Weight Connected Subgraph Problem" by Daniel Rehfeldt and Thorsten Koch, or in "Reduction Techniques for the Prize-Collecting Steiner Tree Problem and the Maximum-Weight Connected Subgraph Problem" by Daniel Rehfeldt et al.

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

Definition in file reduce_alt.c.

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

Go to the source code of this file.

## Macros

#define VERTEX_CONNECT   0

#define VERTEX_TEMPNEIGHBOR   1

#define VERTEX_NEIGHBOR   2

#define VERTEX_OTHER   3

#define STP_RED_CNSNN   25

#define STP_RED_ANSMAXCANDS   500

#define STP_RED_ANSEXMAXCANDS   50

#define STP_RED_ANSMAXNEIGHBORS   25

#define STP_BDR_MAXDEGREE   4

#define STP_BDR_MAXDNEDGES   6

#define STP_BD_MAXDEGREE   4

#define STP_BD_MAXDNEDGES   6

## Functions

static SCIP_Bool sddeltable (SCIP *scip, GRAPH *g, PATH *path, int *vbase, int *forbidden, int tpos, int hpos, int tail, int head, int edge, int nnodes)

static int getcloseterms (SCIP *scip, const PATH *vnoi, SCIP_Real *termdist, SCIP_Real ecost, const int *vbase, int *neighbterms, int i, int nnodes)

static int getcloseterms2term (SCIP *scip, const GRAPH *g, const GRAPH *netgraph, SCIP_Real *termdist, SCIP_Real ecost, int *neighbterms, int *nodesid, int *nodesorg, int i)

static int getlecloseterms (SCIP *scip, PATH *vnoi, SCIP_Real *termdist, SCIP_Real ecost, int *vbase, int *neighbterms, int i, int nnodes)

static void ansProcessCandidate (SCIP *scip, GRAPH *g, int *marked, int *count, SCIP_Real min, int candvertex)

SCIP_RETCODE reduce_sd (SCIP *scip, GRAPH *g, PATH *vnoi, SCIP_Real *edgepreds, SCIP_Real *mstsdist, int *heap, int *state, int *vbase, int *nodesid, int *nodesorg, int *forbidden, int *nelims, SCIP_Bool nodereplacing, int *edgestate)

SCIP_RETCODE reduce_sdPc (SCIP *scip, GRAPH *g, PATH *vnoi, int *heap, int *state, int *vbase, int *nodesid, int *nodesorg, int *nelims)

static SCIP_Real getRSD (SCIP *scip, GRAPH *g, GRAPH *netgraph, PATH *mst, PATH *vnoi, SCIP_Real *mstsdist, SCIP_Real *termdist1, SCIP_Real *termdist2, SCIP_Real sd_initial, int *vbase, int *nodesid, int *neighbterms1, int *neighbterms2, int i, int i2, int limit)

SCIP_RETCODE reduce_getSd (SCIP *scip, GRAPH *g, PATH *pathtail, PATH *pathhead, SCIP_Real *sdist, SCIP_Real distlimit, int *heap, int *statetail, int *statehead, int *memlbltail, int *memlblhead, int i, int i2, int limit, SCIP_Bool pc, SCIP_Bool mw)

SCIP_RETCODE reduce_getSdPcMw (SCIP *scip, const GRAPH *g, PATH *pathtail, PATH *pathhead, SCIP_Real *sdist, SCIP_Real distlimit, int *heap, int *statetail, int *statehead, int *memlbltail, int *memlblhead, int *pathmaxnodetail, int *pathmaxnodehead, int i, int i2, int limit)

SCIP_RETCODE reduce_sdspSap (SCIP *scip, GRAPH *g, PATH *pathtail, PATH *pathhead, int *heap, int *statetail, int *statehead, int *memlbltail, int *memlblhead, int *nelims, int limit)

SCIP_RETCODE reduce_sdsp (SCIP *scip, GRAPH *g, PATH *pathtail, PATH *pathhead, int *heap, int *statetail, int *statehead, int *memlbltail, int *memlblhead, int *nelims, int limit, int *edgestate)

SCIP_RETCODE reduce_bdr (SCIP *scip, GRAPH *g, GRAPH *netgraph, PATH *netmst, PATH *vnoi, SCIP_Real *mstsdist, SCIP_Real *termdist1, SCIP_Real *termdist2, int *vbase, int *nodesid, int *neighbterms1, int *neighbterms2, int *nelims)

SCIP_RETCODE reduce_bd34 (SCIP *scip, GRAPH *g, PATH *pathtail, PATH *pathhead, int *heap, int *statetail, int *statehead, int *memlbltail, int *memlblhead, int *nelims, int limit)

SCIP_RETCODE reduce_nts (SCIP *scip, GRAPH *g, PATH *pathtail, PATH *pathhead, int *heap, int *statetail, int *statehead, int *memlbltail, int *memlblhead, int *nelims, int limit)

SCIP_RETCODE reduce_sl (SCIP *scip, GRAPH *g, PATH *vnoi, double *fixed, int *heap, int *state, int *vbase, int *vrnodes, STP_Bool *visited, int *solnode, int *nelims)

SCIP_RETCODE reduce_nv (SCIP *scip, GRAPH *g, PATH *vnoi, double *fixed, int *edgearrint, int *heap, int *state, int *vbase, int *solnode, int *nelims)

SCIP_RETCODE reduce_nvAdv (SCIP *scip, GRAPH *g, PATH *vnoi, SCIP_Real *distance, double *fixed, int *edgearrint, int *heap, int *state, int *vbase, int *neighb, int *distnode, int *solnode, int *nelims)

SCIP_RETCODE reduce_ledge (SCIP *scip, GRAPH *g, PATH *vnoi, int *heap, int *state, int *vbase, int *nelims, int *edgestate)

void reduce_ans (SCIP *scip, GRAPH *g, int *marked, int *count)

void reduce_ansAdv (SCIP *scip, GRAPH *g, int *marked, int *count, SCIP_Bool extneigbhood)

void reduce_ansAdv2 (SCIP *scip, GRAPH *g, int *marked, int *count)

SCIP_RETCODE reduce_cnsAdv (SCIP *scip, GRAPH *g, int *marked, int *count)

SCIP_RETCODE reduce_npv (SCIP *scip, GRAPH *g, PATH *pathtail, PATH *pathhead, int *heap, int *statetail, int *statehead, int *memlbltail, int *memlblhead, int *nelims, int limit)

SCIP_RETCODE reduce_chain2 (SCIP *scip, GRAPH *g, PATH *pathtail, PATH *pathhead, int *heap, int *statetail, int *statehead, int *memlbltail, int *memlblhead, int *nelims, int limit)

void reduce_nnp (SCIP *scip, GRAPH *g, int *marked, int *count)

## ◆ VERTEX_CONNECT

 #define VERTEX_CONNECT   0

Definition at line 43 of file reduce_alt.c.

## ◆ VERTEX_TEMPNEIGHBOR

 #define VERTEX_TEMPNEIGHBOR   1

Definition at line 44 of file reduce_alt.c.

## ◆ VERTEX_NEIGHBOR

 #define VERTEX_NEIGHBOR   2

Definition at line 45 of file reduce_alt.c.

## ◆ VERTEX_OTHER

 #define VERTEX_OTHER   3

Definition at line 46 of file reduce_alt.c.

## ◆ STP_RED_CNSNN

 #define STP_RED_CNSNN   25

Definition at line 47 of file reduce_alt.c.

## ◆ STP_RED_ANSMAXCANDS

 #define STP_RED_ANSMAXCANDS   500

Definition at line 48 of file reduce_alt.c.

## ◆ STP_RED_ANSEXMAXCANDS

 #define STP_RED_ANSEXMAXCANDS   50

Definition at line 49 of file reduce_alt.c.

## ◆ STP_RED_ANSMAXNEIGHBORS

 #define STP_RED_ANSMAXNEIGHBORS   25

Definition at line 50 of file reduce_alt.c.

Referenced by reduce_ans().

## ◆ STP_BDR_MAXDEGREE

 #define STP_BDR_MAXDEGREE   4

Definition at line 2743 of file reduce_alt.c.

Referenced by reduce_bdr().

## ◆ STP_BDR_MAXDNEDGES

 #define STP_BDR_MAXDNEDGES   6

Definition at line 2744 of file reduce_alt.c.

Referenced by reduce_bdr().

## ◆ STP_BD_MAXDEGREE

 #define STP_BD_MAXDEGREE   4

Definition at line 2952 of file reduce_alt.c.

Referenced by reduce_bd34(), and reduce_nts().

## ◆ STP_BD_MAXDNEDGES

 #define STP_BD_MAXDNEDGES   6

Definition at line 2953 of file reduce_alt.c.

Referenced by reduce_bd34(), and reduce_nts().

## ◆ sddeltable()

 static SCIP_Bool sddeltable ( SCIP * scip, GRAPH * g, PATH * path, int * vbase, int * forbidden, int tpos, int hpos, int tail, int head, int edge, int nnodes )
static

Definition at line 55 of file reduce_alt.c.

Referenced by reduce_sd().

## ◆ getcloseterms()

 static int getcloseterms ( SCIP * scip, const PATH * vnoi, SCIP_Real * termdist, SCIP_Real ecost, const int * vbase, int * neighbterms, int i, int nnodes )
static

Definition at line 167 of file reduce_alt.c.

References shortest_path::dist, nnodes, NULL, and SCIPisLT().

Referenced by getRSD(), and reduce_sdPc().

## ◆ getcloseterms2term()

 static int getcloseterms2term ( SCIP * scip, const GRAPH * g, const GRAPH * netgraph, SCIP_Real * termdist, SCIP_Real ecost, int * neighbterms, int * nodesid, int * nodesorg, int i )
static

Definition at line 206 of file reduce_alt.c.

Referenced by reduce_sdPc().

## ◆ getlecloseterms()

 static int getlecloseterms ( SCIP * scip, PATH * vnoi, SCIP_Real * termdist, SCIP_Real ecost, int * vbase, int * neighbterms, int i, int nnodes )
static

Definition at line 257 of file reduce_alt.c.

Referenced by reduce_sd().

## ◆ ansProcessCandidate()

 static void ansProcessCandidate ( SCIP * scip, GRAPH * g, int * marked, int * count, SCIP_Real min, int candvertex )
static

ans subtest

Parameters
 scip SCIP data structure g graph data structure marked nodes array count pointer to number of reductions min value to not surpass candvertex candidate

Definition at line 1028 of file reduce_alt.c.

## ◆ reduce_sd()

 SCIP_RETCODE reduce_sd ( SCIP * scip, GRAPH * g, PATH * vnoi, SCIP_Real * edgepreds, SCIP_Real * mstsdist, int * heap, int * state, int * vbase, int * nodesid, int * nodesorg, int * forbidden, int * nelims, SCIP_Bool nodereplacing, int * edgestate )

Special distance test

Parameters
 scip SCIP data structure g graph data structure vnoi Voronoi data structure edgepreds array to store edge predecessors of auxiliary graph mstsdist array to store mst distances in auxiliary graph heap array representing a heap state array to indicate whether a node has been scanned during SP calculation vbase Voronoi base to each vertex nodesid array to map nodes in auxiliary graph to original ones nodesorg array to map terminals of original graph vertices of auxiliary graph forbidden array to mark whether an edge may be eliminated nelims point to store number of deleted edges nodereplacing should node replacement (by edges) be performed? edgestate array to store status of (directed) edge (for propagation, can otherwise be set to NULL)

Definition at line 1105 of file reduce_alt.c.

Referenced by redLoopStp().

## ◆ reduce_sdPc()

 SCIP_RETCODE reduce_sdPc ( SCIP * scip, GRAPH * g, PATH * vnoi, int * heap, int * state, int * vbase, int * nodesid, int * nodesorg, int * nelims )

SD test for PC

Parameters
 scip SCIP data structure g graph data structure vnoi Voronoi data structure heap heap array state array to store state of a node during Voronoi computation vbase Voronoi base to each node nodesid array nodesorg array nelims pointer to store number of eliminated edges

Definition at line 1499 of file reduce_alt.c.

Referenced by redLoopPc().

## ◆ getRSD()

 static SCIP_Real getRSD ( SCIP * scip, GRAPH * g, GRAPH * netgraph, PATH * mst, PATH * vnoi, SCIP_Real * mstsdist, SCIP_Real * termdist1, SCIP_Real * termdist2, SCIP_Real sd_initial, int * vbase, int * nodesid, int * neighbterms1, int * neighbterms2, int i, int i2, int limit )
static

get RSD to a single edge

Parameters
 scip SCIP data structure g graph structure netgraph auxiliary graph structure mst MST structure vnoi path structure mstsdist MST distance in aux-graph termdist1 dist array termdist2 second dist array sd_initial initial sd or -1.0 vbase bases for nearest terminals nodesid nodes identification array neighbterms1 neighbour terminals array neighbterms2 second neighbour terminals array i first vertex i2 second vertex limit limit for incident edges to consider

Definition at line 1777 of file reduce_alt.c.

Referenced by reduce_bdr().

## ◆ reduce_getSd()

 SCIP_RETCODE reduce_getSd ( SCIP * scip, GRAPH * g, PATH * pathtail, PATH * pathhead, SCIP_Real * sdist, SCIP_Real distlimit, int * heap, int * statetail, int * statehead, int * memlbltail, int * memlblhead, int i, int i2, int limit, SCIP_Bool pc, SCIP_Bool mw )

get SD to a single edge

Definition at line 1970 of file reduce_alt.c.

Referenced by reduce_bd34(), reduce_chain2(), reduce_npv(), and reduce_nts().

## ◆ reduce_getSdPcMw()

 SCIP_RETCODE reduce_getSdPcMw ( SCIP * scip, const GRAPH * g, PATH * pathtail, PATH * pathhead, SCIP_Real * sdist, SCIP_Real distlimit, int * heap, int * statetail, int * statehead, int * memlbltail, int * memlblhead, int * pathmaxnodetail, int * pathmaxnodehead, int i, int i2, int limit )

get SD to a single edge

Definition at line 2110 of file reduce_alt.c.

Referenced by reduce_bd34(), and reduce_nts().

## ◆ reduce_sdspSap()

 SCIP_RETCODE reduce_sdspSap ( SCIP * scip, GRAPH * g, PATH * pathtail, PATH * pathhead, int * heap, int * statetail, int * statehead, int * memlbltail, int * memlblhead, int * nelims, int limit )

SDC test for the SAP using a limited version of Dijkstra's algorithm from both endpoints of an arc

Definition at line 2308 of file reduce_alt.c.

Referenced by reduceSap().

## ◆ reduce_sdsp()

 SCIP_RETCODE reduce_sdsp ( SCIP * scip, GRAPH * g, PATH * pathtail, PATH * pathhead, int * heap, int * statetail, int * statehead, int * memlbltail, int * memlblhead, int * nelims, int limit, int * edgestate )

SD test using only limited dijkstra from both endpoints of an edge

Definition at line 2459 of file reduce_alt.c.

Referenced by redLoopPc(), and redLoopStp().

## ◆ reduce_bdr()

 SCIP_RETCODE reduce_bdr ( SCIP * scip, GRAPH * g, GRAPH * netgraph, PATH * netmst, PATH * vnoi, SCIP_Real * mstsdist, SCIP_Real * termdist1, SCIP_Real * termdist2, int * vbase, int * nodesid, int * neighbterms1, int * neighbterms2, int * nelims )

bd_k test for given Steiner bottleneck distances todo bd5

Parameters
 scip SCIP data structure g graph structure netgraph auxiliary graph structure netmst MST structure vnoi path structure mstsdist MST distance in aux-graph termdist1 dist array termdist2 second dist array vbase bases for nearest terminals nodesid nodes identification array neighbterms1 neighbour terminals array neighbterms2 second neighbour terminals array nelims number of eliminations

Definition at line 2747 of file reduce_alt.c.

Referenced by reduce_sd().

## ◆ reduce_bd34()

 SCIP_RETCODE reduce_bd34 ( SCIP * scip, GRAPH * g, PATH * pathtail, PATH * pathhead, int * heap, int * statetail, int * statehead, int * memlbltail, int * memlblhead, int * nelims, int limit )
Parameters
 scip SCIP data structure g graph structure pathtail array for internal use pathhead array for internal use heap array for internal use statetail array for internal use statehead array for internal use memlbltail array for internal use memlblhead array for internal use nelims point to return number of eliminations limit limit for edges to consider for each vertex

Definition at line 2964 of file reduce_alt.c.

Referenced by redLoopPc(), and redLoopStp().

## ◆ reduce_nts()

 SCIP_RETCODE reduce_nts ( SCIP * scip, GRAPH * g, PATH * pathtail, PATH * pathhead, int * heap, int * statetail, int * statehead, int * memlbltail, int * memlblhead, int * nelims, int limit )

Non-Terminal-Set test

Parameters
 scip SCIP data structure g graph structure pathtail array for internal use pathhead array for internal use heap array for internal use statetail array for internal use statehead array for internal use memlbltail array for internal use memlblhead array for internal use nelims point to return number of eliminations limit limit for edges to consider for each vertex

Definition at line 3217 of file reduce_alt.c.

## ◆ reduce_sl()

 SCIP_RETCODE reduce_sl ( SCIP * scip, GRAPH * g, PATH * vnoi, double * fixed, int * heap, int * state, int * vbase, int * vrnodes, STP_Bool * visited, int * solnode, int * nelims )
Parameters
 scip SCIP data structure g graph data structure vnoi Voronoi data structure fixed offset pointer heap heap array state shortest path array vbase Voronoi/shortest path bases array vrnodes Voronoi/shortest path array visited Voronoi/shortest path array solnode node array to mark whether an node is part of a given solution (CONNECT), or NULL nelims pointer to store number of eliminations

Definition at line 3483 of file reduce_alt.c.

Referenced by nvreduce_sl().

## ◆ reduce_nv()

 SCIP_RETCODE reduce_nv ( SCIP * scip, GRAPH * g, PATH * vnoi, double * fixed, int * edgearrint, int * heap, int * state, int * vbase, int * solnode, int * nelims )
Parameters
 scip SCIP data structure g graph data structure vnoi Voronoi data structure fixed offset pointer edgearrint edge int array for internal computations heap heap array state array for internal computations vbase array for internal computations solnode node array to mark whether an node is part of a given solution (CONNECT), or NULL nelims pointer to store number of eliminations

Definition at line 3710 of file reduce_alt.c.

 SCIP_RETCODE reduce_nvAdv ( SCIP * scip, GRAPH * g, PATH * vnoi, SCIP_Real * distance, double * fixed, int * edgearrint, int * heap, int * state, int * vbase, int * neighb, int * distnode, int * solnode, int * nelims )
Parameters
 scip SCIP data structure g graph data structure vnoi Voronoi data structure distance nodes-sized distance array fixed offset pointer edgearrint edges-sized array heap heap array state shortest path array vbase Voronoi base array neighb nodes-sized neighborhood array distnode nodes-sized distance array solnode node array to mark whether an node is part of a given solution (CONNECT), or NULL nelims pointer to store number of eliminations

Definition at line 3903 of file reduce_alt.c.

Referenced by nvreduce_sl().

## ◆ reduce_ledge()

 SCIP_RETCODE reduce_ledge ( SCIP * scip, GRAPH * g, PATH * vnoi, int * heap, int * state, int * vbase, int * nelims, int * edgestate )

Definition at line 4143 of file reduce_alt.c.

Referenced by redLoopStp().

## ◆ reduce_ans()

 void reduce_ans ( SCIP * scip, GRAPH * g, int * marked, int * count )

adjacent neighbourhood reduction for the MWCSP

Parameters
 scip SCIP data structure g graph data structure marked nodes array count pointer to number of reductions

Definition at line 4447 of file reduce_alt.c.

Referenced by redLoopMw().

 void reduce_ansAdv ( SCIP * scip, GRAPH * g, int * marked, int * count, SCIP_Bool extneigbhood )

Parameters
 scip SCIP data structure g graph data structure marked nodes array count pointer to number of performed reductions extneigbhood use extended neighbour hood

Definition at line 4515 of file reduce_alt.c.

Referenced by redLoopMw().

 void reduce_ansAdv2 ( SCIP * scip, GRAPH * g, int * marked, int * count )

Parameters
 scip SCIP data structure g graph data structure marked nodes array count pointer to number of reductions

Definition at line 4621 of file reduce_alt.c.

Referenced by redLoopMw().

 SCIP_RETCODE reduce_cnsAdv ( SCIP * scip, GRAPH * g, int * marked, int * count )

advanced connected neighborhood subset reduction test for the MWCSP

Parameters
 scip SCIP data structure g graph data structure marked nodes array for internal use count pointer to number of reductions

Definition at line 4748 of file reduce_alt.c.

## ◆ reduce_npv()

 SCIP_RETCODE reduce_npv ( SCIP * scip, GRAPH * g, PATH * pathtail, PATH * pathhead, int * heap, int * statetail, int * statehead, int * memlbltail, int * memlblhead, int * nelims, int limit )

non-positive vertex reduction for the MWCSP

Definition at line 5024 of file reduce_alt.c.

Referenced by redLoopMw().

## ◆ reduce_chain2()

 SCIP_RETCODE reduce_chain2 ( SCIP * scip, GRAPH * g, PATH * pathtail, PATH * pathhead, int * heap, int * statetail, int * statehead, int * memlbltail, int * memlblhead, int * nelims, int limit )

chain reduction (NPV_2) for the MWCSP

Definition at line 5367 of file reduce_alt.c.

Referenced by redLoopMw().

## ◆ reduce_nnp()

 void reduce_nnp ( SCIP * scip, GRAPH * g, int * marked, int * count )

non-negative path reduction for the MWCSP

Parameters
 scip SCIP data structure g graph data structure marked nodes array count pointer to number of reductions

Definition at line 5450 of file reduce_alt.c.

Referenced by redLoopMw().