# 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. Most 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. Note that special distance tests as well as extending (alternative) reduction techniques can be found in separate files.

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

Definition in file reduce_alt.c.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "graph.h"
#include "reduce.h"
#include "misc_stp.h"
#include "probdata_stp.h"
#include "scip/scip.h"
#include "portab.h"

Go to the source code of this file.

## Data Structures

struct  nearest_special_distance_test_data

## 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

## Typedefs

typedef struct nearest_special_distance_test_data NSV

## Functions

static void ansDeleteVertex (SCIP *scip, GRAPH *g, int *RESTRICT marked, int *RESTRICT nelims, int vertex)

static void ansUnmark (const GRAPH *g, int basenode, const int *neighbarr, int nNeigbors, int *RESTRICT marked)

static void ansProcessCandidateWithBridge (SCIP *scip, GRAPH *g, int *RESTRICT marked, int *RESTRICT nelims, SCIP_Real maxprize, int candvertex, int bridgeedge)

static void ansProcessCandidate (SCIP *scip, GRAPH *g, int *RESTRICT marked, int *RESTRICT nelims, SCIP_Real maxprize, int candvertex)

static SCIP_RETCODE nsvInitData (SCIP *scip, const SD *sdistance, const GRAPH *g, int *solnode, SCIP_Real *fixed, NSV *nsv)

static void nsvInitRecording (STP_Vectype(int) edgesrecord, NSV *nsv)

static void nsvFreeData (SCIP *scip, NSV *nsv)

static SCIP_Bool nsvEdgeIsValid (const GRAPH *g, const NSV *nsv, int edge)

static void nsvEdgeGetTermDists (const GRAPH *g, const NSV *nsv, int edge, int candidate_id, SCIP_Real *dist_tail, SCIP_Real *dist_head)

static SCIP_RETCODE nsvEdgeContract (SCIP *scip, int edge, int end_remain, int end_killed, GRAPH *g, NSV *nsv, int *nelims)

static SCIP_RETCODE nsvExec (SCIP *scip, NSV *nsv, GRAPH *g, int *nelims)

SCIP_RETCODE reduce_nsvImplied (SCIP *scip, const SD *sdistance, GRAPH *g, int *solnode, SCIP_Real *fixed, int *nelims)

SCIP_RETCODE reduce_nsvImpliedRecord (SCIP *scip, const SD *sdistance, GRAPH *g, STP_Vectype(int) *edgerecord)

SCIP_RETCODE reduce_sl (SCIP *scip, const int *edgestate, GRAPH *g, PATH *vnoi, SCIP_Real *fixed, int *vbase, int *vrnodes, STP_Bool *visited, int *solnode, int *nelims)

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

SCIP_RETCODE reduce_nvAdv (SCIP *scip, const int *edgestate, GRAPH *g, PATH *vnoi, SCIP_Real *distance, SCIP_Real *fixed, int *edgearrint, int *vbase, int *distnode, int *solnode, int *nelims)

SCIP_RETCODE reduce_ans (SCIP *scip, GRAPH *g, int *nelims)

SCIP_RETCODE reduce_ansAdv (SCIP *scip, GRAPH *g, int *nelims, SCIP_Bool extneigbhood)

SCIP_RETCODE reduce_ansAdv2 (SCIP *scip, GRAPH *g, int *nelims)

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

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

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

SCIP_RETCODE reduce_nnp (SCIP *scip, GRAPH *g, int *nelims)

SCIP_RETCODE reduce_impliedProfitBased (SCIP *scip, int edgelimit, GRAPH *g, int *solnode, SCIP_Real *fixed, int *nelims)

SCIP_RETCODE reduce_impliedProfitBasedRpc (SCIP *scip, GRAPH *g, REDSOLLOCAL *redsollocal, SCIP_Real *fixed, int *nelims)

## ◆ VERTEX_CONNECT

 #define VERTEX_CONNECT   0

Definition at line 48 of file reduce_alt.c.

## ◆ VERTEX_TEMPNEIGHBOR

 #define VERTEX_TEMPNEIGHBOR   1

Definition at line 49 of file reduce_alt.c.

## ◆ VERTEX_NEIGHBOR

 #define VERTEX_NEIGHBOR   2

Definition at line 50 of file reduce_alt.c.

## ◆ VERTEX_OTHER

 #define VERTEX_OTHER   3

Definition at line 51 of file reduce_alt.c.

## ◆ STP_RED_CNSNN

 #define STP_RED_CNSNN   25

Definition at line 52 of file reduce_alt.c.

## ◆ STP_RED_ANSMAXCANDS

 #define STP_RED_ANSMAXCANDS   500

Definition at line 53 of file reduce_alt.c.

## ◆ STP_RED_ANSEXMAXCANDS

 #define STP_RED_ANSEXMAXCANDS   50

Definition at line 54 of file reduce_alt.c.

## ◆ STP_RED_ANSMAXNEIGHBORS

 #define STP_RED_ANSMAXNEIGHBORS   25

Definition at line 55 of file reduce_alt.c.

Referenced by reduce_ans().

## ◆ NSV

 typedef struct nearest_special_distance_test_data NSV

NSV test data

## ◆ ansDeleteVertex()

 static void ansDeleteVertex ( SCIP * scip, GRAPH * g, int *RESTRICT marked, int *RESTRICT nelims, int vertex )
inlinestatic

ans subtest

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

Definition at line 85 of file reduce_alt.c.

Referenced by ansProcessCandidate(), and ansProcessCandidateWithBridge().

## ◆ ansUnmark()

 static void ansUnmark ( const GRAPH * g, int basenode, const int * neighbarr, int nNeigbors, int *RESTRICT marked )
inlinestatic

un-marks

Parameters
 g graph data structure basenode base node neighbarr array of neighbors nNeigbors nNeigbors marked nodes array

Definition at line 111 of file reduce_alt.c.

## ◆ ansProcessCandidateWithBridge()

 static void ansProcessCandidateWithBridge ( SCIP * scip, GRAPH * g, int *RESTRICT marked, int *RESTRICT nelims, SCIP_Real maxprize, int candvertex, int bridgeedge )
inlinestatic

ANS submethod for the case that the candidate vertex has exactly one non-dominated neighbor and both vertices combined are dominated

Parameters
 scip SCIP data structure g graph data structure marked nodes array nelims pointer to number of reductions maxprize value to not surpass candvertex candidate bridgeedge edge to neighbor

Definition at line 158 of file reduce_alt.c.

Referenced by ansProcessCandidate().

## ◆ ansProcessCandidate()

 static void ansProcessCandidate ( SCIP * scip, GRAPH * g, int *RESTRICT marked, int *RESTRICT nelims, SCIP_Real maxprize, int candvertex )
static

ANS subtest

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

Definition at line 219 of file reduce_alt.c.

## ◆ nsvInitData()

 static SCIP_RETCODE nsvInitData ( SCIP * scip, const SD * sdistance, const GRAPH * g, int * solnode, SCIP_Real * fixed, NSV * nsv )
static

initializes NSV test data

Parameters
 scip SCIP data structure sdistance special distances storage g graph structure solnode node array to mark whether an node is part of a given solution (CONNECT) fixed offset pointer nsv NSV

Definition at line 264 of file reduce_alt.c.

Referenced by reduce_nsvImplied(), and reduce_nsvImpliedRecord().

## ◆ nsvInitRecording()

 static void nsvInitRecording ( STP_Vectype(int) edgesrecord, NSV * nsv )
static

initializes NSV recordings

Parameters
 edgesrecord edges record nsv NSV

Definition at line 337 of file reduce_alt.c.

References TRUE.

Referenced by reduce_nsvImpliedRecord().

## ◆ nsvFreeData()

 static void nsvFreeData ( SCIP * scip, NSV * nsv )
static

frees NSV test data

Parameters
 scip SCIP data structure nsv NSV

Definition at line 352 of file reduce_alt.c.

Referenced by reduce_nsvImplied(), and reduce_nsvImpliedRecord().

## ◆ nsvEdgeIsValid()

 static SCIP_Bool nsvEdgeIsValid ( const GRAPH * g, const NSV * nsv, int edge )
inlinestatic

edge in NSV test can possibly still be contracted?

Parameters
 g graph structure nsv NSV data edge the edge

Definition at line 370 of file reduce_alt.c.

Referenced by nsvExec().

## ◆ nsvEdgeGetTermDists()

 static void nsvEdgeGetTermDists ( const GRAPH * g, const NSV * nsv, int edge, int candidate_id, SCIP_Real * dist_tail, SCIP_Real * dist_head )
inlinestatic

get special implied distances to terminals from both endpoints of given edge

Parameters
 g graph structure nsv NSV data edge the edge candidate_id id of candidate dist_tail distance from tail dist_head distance from head

Definition at line 400 of file reduce_alt.c.

Referenced by nsvExec().

## ◆ nsvEdgeContract()

 static SCIP_RETCODE nsvEdgeContract ( SCIP * scip, int edge, int end_remain, int end_killed, GRAPH * g, NSV * nsv, int * nelims )
inlinestatic

contract edge in NSV test

Parameters
 scip SCIP data structure edge the edge end_remain survivor end node of edge end_killed other end node g graph structure nsv NSV data nelims number of eliminations

Definition at line 497 of file reduce_alt.c.

Referenced by nsvExec().

## ◆ nsvExec()

 static SCIP_RETCODE nsvExec ( SCIP * scip, NSV * nsv, GRAPH * g, int * nelims )
static

executes actual NSV test

Parameters
 scip SCIP data structure nsv NSV g graph structure nelims number of eliminations

Definition at line 535 of file reduce_alt.c.

Referenced by reduce_nsvImplied(), and reduce_nsvImpliedRecord().

## ◆ reduce_nsvImplied()

 SCIP_RETCODE reduce_nsvImplied ( SCIP * scip, const SD * sdistance, GRAPH * g, int * solnode, SCIP_Real * fixed, int * nelims )

implied version of NSV test

Parameters
 scip SCIP data structure sdistance special distances storage g graph structure solnode node array to mark whether an node is part of a given solution (CONNECT) fixed offset pointer nelims number of eliminations

Definition at line 621 of file reduce_alt.c.

References nsvExec(), nsvFreeData(), nsvInitData(), SCIP_CALL, and SCIP_OKAY.

## ◆ reduce_nsvImpliedRecord()

 SCIP_RETCODE reduce_nsvImpliedRecord ( SCIP * scip, const SD * sdistance, GRAPH * g, STP_Vectype(int) * edgerecord )

implied version of NSV test. Does not perform the reductions, but rather records them

Parameters
 scip SCIP data structure sdistance special distances storage g graph structure edgerecord keeps number edges

Definition at line 643 of file reduce_alt.c.

References nsvExec(), nsvFreeData(), nsvInitData(), nsvInitRecording(), NULL, SCIP_CALL, and SCIP_OKAY.

Referenced by reduce_impliedProfitBasedRpc().

## ◆ reduce_sl()

 SCIP_RETCODE reduce_sl ( SCIP * scip, const int * edgestate, GRAPH * g, PATH * vnoi, SCIP_Real * fixed, int * vbase, int * vrnodes, STP_Bool * visited, int * solnode, int * nelims )

Parameters
 scip SCIP data structure edgestate for propagation or NULL g graph data structure vnoi Voronoi data structure fixed offset pointer 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 665 of file reduce_alt.c.

Referenced by execNvSl().

## ◆ reduce_nv()

 SCIP_RETCODE reduce_nv ( SCIP * scip, GRAPH * g, PATH * vnoi, SCIP_Real * fixed, int * edgearrint, 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 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 932 of file reduce_alt.c.

 SCIP_RETCODE reduce_nvAdv ( SCIP * scip, const int * edgestate, GRAPH * g, PATH * vnoi, SCIP_Real * distance, SCIP_Real * fixed, int * edgearrint, int * vbase, int * distnode, int * solnode, int * nelims )
Parameters
 scip SCIP data structure edgestate for propagation or NULL g graph data structure vnoi Voronoi data structure distance nodes-sized distance array fixed offset pointer edgearrint edges-sized array vbase Voronoi base 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 1121 of file reduce_alt.c.

Referenced by execNvSl().

## ◆ reduce_ans()

 SCIP_RETCODE reduce_ans ( SCIP * scip, GRAPH * g, int * nelims )

adjacent neighbourhood reduction for the MWCSP

Parameters
 scip SCIP data structure g graph data structure nelims pointer to number of reductions

Definition at line 1470 of file reduce_alt.c.

 SCIP_RETCODE reduce_ansAdv ( SCIP * scip, GRAPH * g, int * nelims, SCIP_Bool extneigbhood )

Parameters
 scip SCIP data structure g graph data structure nelims pointer to number of performed reductions extneigbhood use extended neighbour hood

Definition at line 1544 of file reduce_alt.c.

Referenced by redLoopInnerMw().

 SCIP_RETCODE reduce_ansAdv2 ( SCIP * scip, GRAPH * g, int * nelims )

Parameters
 scip SCIP data structure g graph data structure nelims pointer to number of reductions

Definition at line 1656 of file reduce_alt.c.

Referenced by redLoopInnerMw().

 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 1793 of file reduce_alt.c.

## ◆ reduce_npv()

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

non-positive vertex reduction for the MWCSP

Definition at line 2067 of file reduce_alt.c.

Referenced by redLoopInnerMw(), and testRmwNpv3DeletesNode().

## ◆ reduce_chain2()

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

chain reduction (NPV_2) for the MWCSP

Definition at line 2445 of file reduce_alt.c.

Referenced by redLoopInnerMw(), and testRmwChain2DeletesNode().

## ◆ reduce_nnp()

 SCIP_RETCODE reduce_nnp ( SCIP * scip, GRAPH * g, int * nelims )

non-negative path reduction for the MWCSP

Parameters
 scip SCIP data structure g graph data structure nelims pointer to number of reductions

Definition at line 2534 of file reduce_alt.c.

Referenced by redLoopInnerMw().

## ◆ reduce_impliedProfitBased()

 SCIP_RETCODE reduce_impliedProfitBased ( SCIP * scip, int edgelimit, GRAPH * g, int * solnode, SCIP_Real * fixed, int * nelims )

Combined implied-profit based tests: First elimination tests are used, afterwards edge contraction test are applied. NOTE: The expensive part is to build the bottleneck distances, thus we always apply all other tests.

Parameters
 scip SCIP data structure edgelimit limit for star test g graph structure solnode node array to mark whether an node is part of a given solution (CONNECT) fixed offset pointer nelims number of eliminations

Definition at line 2609 of file reduce_alt.c.

Referenced by redLoopInnerStp().

## ◆ reduce_impliedProfitBasedRpc()

 SCIP_RETCODE reduce_impliedProfitBasedRpc ( SCIP * scip, GRAPH * g, REDSOLLOCAL * redsollocal, SCIP_Real * fixed, int * nelims )

similar to above, but for rooted-prize collecting Steiner tree problem

Parameters
 scip SCIP data structure g graph structure redsollocal primal bound info fixed offset pointer nelims number of eliminations

Definition at line 2664 of file reduce_alt.c.

Referenced by reduce_redLoopPc().