Scippy

SCIP

Solving Constraint Integer Programs

reduce.c File Reference

Detailed Description

Reduction tests for Steiner problems.

Author
Gerald Gamrath
Thorsten Koch
Stephen Maher
Daniel Rehfeldt

This file includes 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 STP_RED_SDSPBOUND   200
 
#define STP_RED_SDSPBOUND2   600
 
#define STP_RED_BD3BOUND   500
 
#define STP_RED_EXTENSIVE   FALSE
 
#define STP_RED_MWTERMBOUND   400
 
#define STP_RED_MAXNROUNDS   15
 
#define STP_RED_EXFACTOR   2
 

Functions

static void reduceStatsPrint (SCIP_Bool print, const char *method, int nelims)
 
static SCIP_RETCODE nvreduce_sl (SCIP *scip, GRAPH *g, PATH *vnoi, SCIP_Real *nodearrreal, SCIP_Real *fixed, int *edgearrint, int *heap, int *state, int *vbase, int *neighb, int *distnode, int *solnode, STP_Bool *visited, int *nelims, int minelims)
 
SCIP_RETCODE level0 (SCIP *scip, GRAPH *g)
 
SCIP_RETCODE level0save (SCIP *scip, GRAPH *g)
 
SCIP_RETCODE reduceStp (SCIP *scip, GRAPH **graph, SCIP_Real *fixed, int minelims, SCIP_Bool dualascent, SCIP_Bool nodereplacing, SCIP_Bool userec)
 
static SCIP_RETCODE reducePc (SCIP *scip, GRAPH **graph, SCIP_Real *fixed, int minelims, STP_Bool dualascent, SCIP_Bool userec)
 
static SCIP_RETCODE reduceMw (SCIP *scip, GRAPH **graph, SCIP_Real *fixed, int minelims, STP_Bool advanced, SCIP_Bool userec)
 
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)
 
static SCIP_RETCODE reduceNw (SCIP *scip, GRAPH **graph, SCIP_Real *fixed, int minelims)
 
SCIP_RETCODE redLoopMw (SCIP *scip, GRAPH *g, PATH *vnoi, PATH *path, GNODE **gnodearr, SCIP_Real *nodearrreal, SCIP_Real *edgearrreal, SCIP_Real *edgearrreal2, int *state, int *vbase, int *nodearrint, int *edgearrint, int *nodearrint2, int *nodearrint3, int *solnode, STP_Bool *nodearrchar, SCIP_Real *fixed, STP_Bool advanced, STP_Bool bred, STP_Bool tryrmw, int redbound, SCIP_Bool userec)
 
SCIP_RETCODE redLoopPc (SCIP *scip, GRAPH *g, PATH *vnoi, PATH *path, GNODE **gnodearr, SCIP_Real *nodearrreal, SCIP_Real *exedgearrreal, SCIP_Real *exedgearrreal2, int *heap, int *state, int *vbase, int *nodearrint, int *edgearrint, int *nodearrint2, int *solnode, STP_Bool *nodearrchar, SCIP_Real *fixed, SCIP_Bool dualascent, SCIP_Bool bred, int reductbound, SCIP_Bool userec)
 
SCIP_RETCODE redLoopStp (SCIP *scip, GRAPH *g, PATH *vnoi, PATH *path, GNODE **gnodearr, SCIP_Real *nodearrreal, SCIP_Real *edgearrreal, SCIP_Real *edgearrreal2, int *heap, int *state, int *vbase, int *nodearrint, int *edgearrint, int *nodearrint2, int *solnode, STP_Bool *nodearrchar, SCIP_Real *fixed, SCIP_Real upperbound, SCIP_Bool dualascent, SCIP_Bool boundreduce, SCIP_Bool nodereplacing, int reductbound, SCIP_Bool userec, SCIP_Bool fullreduce)
 
SCIP_RETCODE reduce (SCIP *scip, GRAPH **graph, SCIP_Real *offset, int level, int minelims, SCIP_Bool userec)
 

Macro Definition Documentation

◆ REDUCE_C

#define REDUCE_C

Definition at line 31 of file reduce.c.

◆ STP_RED_SDSPBOUND

#define STP_RED_SDSPBOUND   200

visited edges bound for SDSP test

Definition at line 32 of file reduce.c.

Referenced by redLoopPc(), and redLoopStp().

◆ STP_RED_SDSPBOUND2

#define STP_RED_SDSPBOUND2   600

visited edges bound for SDSP test

Definition at line 33 of file reduce.c.

Referenced by redLoopPc(), and redLoopStp().

◆ STP_RED_BD3BOUND

#define STP_RED_BD3BOUND   500

visited edges bound for BD3 test

Definition at line 34 of file reduce.c.

Referenced by redLoopPc(), and redLoopStp().

◆ STP_RED_EXTENSIVE

#define STP_RED_EXTENSIVE   FALSE

Definition at line 35 of file reduce.c.

Referenced by redLoopMw(), redLoopPc(), and redLoopStp().

◆ STP_RED_MWTERMBOUND

#define STP_RED_MWTERMBOUND   400

Definition at line 36 of file reduce.c.

Referenced by redLoopMw().

◆ STP_RED_MAXNROUNDS

#define STP_RED_MAXNROUNDS   15

Definition at line 37 of file reduce.c.

Referenced by redLoopMw(), and redLoopPc().

◆ STP_RED_EXFACTOR

#define STP_RED_EXFACTOR   2

Definition at line 38 of file reduce.c.

Referenced by redLoopStp().

Function Documentation

◆ reduceStatsPrint()

static void reduceStatsPrint ( SCIP_Bool  print,
const char *  method,
int  nelims 
)
static

print reduction information

Definition at line 55 of file reduce.c.

Referenced by redLoopStp().

◆ nvreduce_sl()

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

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

Definition at line 72 of file reduce.c.

References FALSE, graph_valid(), NULL, reduce_nvAdv(), reduce_simple(), reduce_simple_pc(), reduce_sl(), SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, STP_PCSPG, STP_RPCSPG, and GRAPH::stp_type.

Referenced by redLoopPc(), and redLoopStp().

◆ level0()

◆ level0save()

SCIP_RETCODE level0save ( SCIP scip,
GRAPH g 
)

◆ reduceStp()

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

basic reduction package for the STP

Parameters
scipSCIP data structure
graphgraph data structure
fixedpointer to store the offset value
minelimsminimal number of edges to be eliminated in order to reiterate reductions
dualascentperform dual-ascent reductions?
nodereplacingshould node replacement (by edges) be performed?
userecuse recombination heuristic?

Definition at line 223 of file reduce.c.

References GRAPH::edges, FALSE, GRAPH::knots, MAX, nnodes, nterms, NULL, redLoopStp(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemory, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBlockMemory, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPisLE(), GRAPH::terms, and TRUE.

Referenced by redbasedVarfixing(), and reduce().

◆ reducePc()

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

basic reduction package for the (R)PCSTP

Parameters
scipSCIP data structure
graphgraph data structure
fixedpointer to store the offset value
minelimsminimal number of edges to be eliminated in order to reiterate reductions
dualascentperform dual ascent reductions?
userecuse recombination heuristic?

Definition at line 338 of file reduce.c.

References GRAPH::edges, FALSE, GRAPH::knots, MAX, nnodes, nterms, NULL, redLoopPc(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemory, SCIPallocBufferArray, SCIPfreeBlockMemory, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPgetRealParam(), SCIPisLE(), STP_RPCSPG, GRAPH::stp_type, GRAPH::terms, and TRUE.

Referenced by reduce().

◆ reduceMw()

static SCIP_RETCODE reduceMw ( SCIP scip,
GRAPH **  graph,
SCIP_Real fixed,
int  minelims,
STP_Bool  advanced,
SCIP_Bool  userec 
)
static

reduction package for the MWCSP

Parameters
scipSCIP data structure
graphgraph data structure
fixedpointer to store the offset value
minelimsminimal number of edges to be eliminated in order to reiterate reductions
advancedperform advanced reductions?
userecuse recombination heuristic?

Definition at line 459 of file reduce.c.

References GRAPH::edges, FALSE, GRAPH::knots, MAX, nnodes, nterms, NULL, redLoopMw(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemory, SCIPallocBufferArray, SCIPfreeBlockMemory, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPisLE(), GRAPH::terms, and TRUE.

Referenced by reduce().

◆ reduceHc()

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

basic reduction package for the HCDSTP

Parameters
scipSCIP data structure
graphgraph data structure
fixedpointer to store the offset value
minelimsminimal number of edges to be eliminated in order to reiterate reductions

Definition at line 571 of file reduce.c.

References GRAPH::edges, FALSE, GRAPH::knots, MAX, nnodes, NULL, reduce_bound(), reduce_boundHop(), reduce_boundHopR(), reduce_boundHopRc(), reduce_simple_hc(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetRealParam(), SCIPgetTotalTime(), SCIPisStopped(), and TRUE.

Referenced by reduce().

◆ reduceSap()

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

basic reduction package for the SAP

Parameters
scipSCIP data structure
graphgraph data structure
fixedpointer to store the offset value
minelimsminimal number of edges to be eliminated in order to reiterate reductions

Definition at line 691 of file reduce.c.

References GRAPH::cost, GRAPH::edges, FALSE, FARAWAY, GRAPH::knots, MAX, nnodes, nterms, reduce_da(), reduce_rpt(), reduce_sdspSap(), reduce_simple_sap(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemory, SCIPallocBufferArray, SCIPcreateRandom(), SCIPfreeBlockMemory, SCIPfreeBufferArray, SCIPfreeRandom(), SCIPgetRealParam(), SCIPgetTotalTime(), SCIPisEQ(), SCIPisStopped(), GRAPH::terms, and TRUE.

Referenced by reduce().

◆ reduceNw()

static SCIP_RETCODE reduceNw ( SCIP scip,
GRAPH **  graph,
SCIP_Real fixed,
int  minelims 
)
static
Parameters
scipSCIP data structure
graphgraph data structure
fixedpointer to store the offset value
minelimsminimal number of edges to be eliminated in order to reiterate reductions

Definition at line 826 of file reduce.c.

References GRAPH::edges, FALSE, FARAWAY, GRAPH::knots, MAX, nnodes, nterms, reduce_da(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemory, SCIPallocBufferArray, SCIPcreateRandom(), SCIPfreeBlockMemory, SCIPfreeBufferArray, SCIPfreeRandom(), SCIPgetRealParam(), SCIPgetTotalTime(), SCIPisStopped(), GRAPH::terms, and TRUE.

Referenced by reduce().

◆ redLoopMw()

SCIP_RETCODE redLoopMw ( SCIP scip,
GRAPH g,
PATH vnoi,
PATH path,
GNODE **  gnodearr,
SCIP_Real nodearrreal,
SCIP_Real edgearrreal,
SCIP_Real edgearrreal2,
int *  state,
int *  vbase,
int *  nodearrint,
int *  edgearrint,
int *  nodearrint2,
int *  nodearrint3,
int *  solnode,
STP_Bool nodearrchar,
SCIP_Real fixed,
STP_Bool  advanced,
STP_Bool  bred,
STP_Bool  tryrmw,
int  redbound,
SCIP_Bool  userec 
)

MWCS loop

Parameters
scipSCIP data structure
ggraph data structure
vnoiVoronoi data structure
pathpath data structure
gnodearrnodes-sized array
nodearrrealnodes-sized array
edgearrrealedges-sized array
edgearrreal2edges-sized array
stateshortest path array
vbasevoronoi base array
nodearrintnodes-sized array
edgearrintedges-sized array
nodearrint2nodes-sized array
nodearrint3nodes-sized array
solnodearray to indicate whether a node is part of the current solution (==CONNECT)
nodearrcharnodes-sized array
fixedpointer to store the offset value
advanceddo advanced reduction?
breddo bound-based reduction?
tryrmwtry to convert problem to RMWCSP? Only possible if advanced = TRUE and userec = TRUE
redboundminimal number of edges to be eliminated in order to reiterate reductions
userecuse recombination heuristic?

Definition at line 923 of file reduce.c.

References FALSE, graph_pc_2org(), graph_pc_2trans(), graph_pc_getPosPrizeSum(), graph_pc_mw2rmw(), graph_pc_term2edgeConsistent(), level0(), NULL, reduce_ans(), reduce_ansAdv(), reduce_ansAdv2(), reduce_boundMw(), reduce_chain2(), reduce_daPcMw(), reduce_nnp(), reduce_npv(), reduce_simple_mw(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcreateRandom(), SCIPdebugMessage, SCIPfreeRandom(), SCIPgetRealParam(), SCIPgetTotalTime(), SCIPisStopped(), STP_RED_EXTENSIVE, STP_RED_MAXNROUNDS, STP_RED_MWTERMBOUND, GRAPH::terms, and TRUE.

Referenced by reduceMw(), SCIPStpHeurPruneRun(), and SCIPStpHeurSlackPruneRunPcMw().

◆ redLoopPc()

SCIP_RETCODE redLoopPc ( SCIP scip,
GRAPH g,
PATH vnoi,
PATH path,
GNODE **  gnodearr,
SCIP_Real nodearrreal,
SCIP_Real exedgearrreal,
SCIP_Real exedgearrreal2,
int *  heap,
int *  state,
int *  vbase,
int *  nodearrint,
int *  edgearrint,
int *  nodearrint2,
int *  solnode,
STP_Bool nodearrchar,
SCIP_Real fixed,
SCIP_Bool  dualascent,
SCIP_Bool  bred,
int  reductbound,
SCIP_Bool  userec 
)

(R)PC loop

Parameters
scipSCIP data structure
ggraph data structure
vnoiVoronoi data structure
pathpath data structure
gnodearrnodes-sized array
nodearrrealnodes-sized array
exedgearrrealedges-sized array
exedgearrreal2edges-sized array
heapshortest path array
statevoronoi base array
vbasenodes-sized array
nodearrintedges-sized array
edgearrintnodes-sized array
nodearrint2nodes-sized array
solnodesolution nodes array (or NULL)
nodearrcharnodes-sized array
fixedpointer to store the offset value
dualascentdo dual-ascent reduction?
breddo bound-based reduction?
reductboundminimal number of edges to be eliminated in order to reiterate reductions
userecuse recombination heuristic?

Definition at line 1160 of file reduce.c.

References FALSE, FARAWAY, GRAPH::grad, graph_pc_2org(), graph_pc_2trans(), graph_pc_getPosPrizeSum(), graph_pc_presolExit(), graph_pc_presolInit(), graph_pc_term2edgeConsistent(), NULL, nvreduce_sl(), GRAPH::prize, reduce_bd34(), reduce_bound(), reduce_da(), reduce_daPcMw(), reduce_sdPc(), reduce_sdsp(), reduce_simple_pc(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcreateRandom(), SCIPdebugMessage, SCIPfreeRandom(), SCIPgetRealParam(), SCIPgetTotalTime(), SCIPisStopped(), GRAPH::source, STP_RED_BD3BOUND, STP_RED_EXTENSIVE, STP_RED_MAXNROUNDS, STP_RED_SDSPBOUND, STP_RED_SDSPBOUND2, STP_RPCSPG, GRAPH::stp_type, GRAPH::terms, and TRUE.

Referenced by reducePc(), and SCIPStpHeurPruneRun().

◆ redLoopStp()

SCIP_RETCODE redLoopStp ( SCIP scip,
GRAPH g,
PATH vnoi,
PATH path,
GNODE **  gnodearr,
SCIP_Real nodearrreal,
SCIP_Real edgearrreal,
SCIP_Real edgearrreal2,
int *  heap,
int *  state,
int *  vbase,
int *  nodearrint,
int *  edgearrint,
int *  nodearrint2,
int *  solnode,
STP_Bool nodearrchar,
SCIP_Real fixed,
SCIP_Real  upperbound,
SCIP_Bool  dualascent,
SCIP_Bool  boundreduce,
SCIP_Bool  nodereplacing,
int  reductbound,
SCIP_Bool  userec,
SCIP_Bool  fullreduce 
)

STP loop

Parameters
scipSCIP data structure
ggraph data structure
vnoiVoronoi data structure
pathpath data structure
gnodearrnodes-sized array
nodearrrealnodes-sized array
edgearrrealedges-sized array
edgearrreal2edges-sized array
heapheap array
stateshortest path array
vbaseVoronoi base array
nodearrintedges-sized array
edgearrintnodes-sized array
nodearrint2nodes-sized array
solnodesolution nodes array (or NULL)
nodearrcharnodes-sized array
fixedpointer to store the offset value
upperboundupper bound
dualascentdo dual-ascent reduction?
boundreducedo bound-based reduction?
nodereplacingshould node replacement (by edges) be performed?
reductboundminimal number of edges to be eliminated in order to reiterate reductions
userecuse recombination heuristic?
fullreduceuse full reductions? (including extended techniques)

Definition at line 1411 of file reduce.c.

References FALSE, graph_valid(), level0(), NULL, nvreduce_sl(), reduce_bd34(), reduce_bound(), reduce_contractZeroEdges(), reduce_da(), reduce_deleteConflictEdges(), reduce_ledge(), reduce_sd(), reduce_sdsp(), reduce_simple(), reduceStatsPrint(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcreateRandom(), SCIPdebugMessage, SCIPfreeRandom(), SCIPgetRealParam(), SCIPgetTotalTime(), SCIPisStopped(), STP_RED_BD3BOUND, STP_RED_EXFACTOR, STP_RED_EXTENSIVE, STP_RED_SDSPBOUND, STP_RED_SDSPBOUND2, and TRUE.

Referenced by reduceStp(), SCIPStpHeurPruneRun(), and SCIPStpHeurSlackPruneRun().

◆ reduce()

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

reduces the graph

Parameters
scipSCIP data structure
graphgraph structure
offsetpointer to store offset generated by reductions
levelreduction level 0: none, 1: basic, 2: advanced
minelimsminimal amount of reductions to reiterate reduction methods
userecuse recombination heuristic?

Definition at line 1675 of file reduce.c.

References FALSE, graph_init_history(), graph_path_exit(), graph_path_init(), graph_valid(), level0(), NULL, reduceHc(), reduceMw(), reduceNw(), reducePc(), reduceSap(), reduceStp(), SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, STP_DCSTP, STP_DHCSTP, STP_MWCSP, STP_NWSPG, STP_PCSPG, STP_RMWCSP, STP_RPCSPG, STP_SAP, and TRUE.

Referenced by SCIPprobdataCreate(), SCIPStpHeurRecExclude(), and SCIPStpHeurRecRun().