Scippy

SCIP

Solving Constraint Integer Programs

reduce_alt.c File Reference

Detailed Description

Altenative based reduction tests for Steiner problems.

Author
Thorsten Koch
Stephen Maher
Daniel Rehfeldt

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)
 

Macro Definition Documentation

◆ VERTEX_CONNECT

#define VERTEX_CONNECT   0

Definition at line 43 of file reduce_alt.c.

Referenced by reduce_cnsAdv().

◆ VERTEX_TEMPNEIGHBOR

#define VERTEX_TEMPNEIGHBOR   1

Definition at line 44 of file reduce_alt.c.

Referenced by reduce_cnsAdv().

◆ VERTEX_NEIGHBOR

#define VERTEX_NEIGHBOR   2

Definition at line 45 of file reduce_alt.c.

Referenced by reduce_cnsAdv().

◆ VERTEX_OTHER

#define VERTEX_OTHER   3

Definition at line 46 of file reduce_alt.c.

Referenced by reduce_cnsAdv().

◆ STP_RED_CNSNN

#define STP_RED_CNSNN   25

Definition at line 47 of file reduce_alt.c.

Referenced by reduce_ansAdv(), reduce_ansAdv2(), and reduce_cnsAdv().

◆ STP_RED_ANSMAXCANDS

#define STP_RED_ANSMAXCANDS   500

Definition at line 48 of file reduce_alt.c.

Referenced by reduce_ansAdv().

◆ STP_RED_ANSEXMAXCANDS

#define STP_RED_ANSEXMAXCANDS   50

Definition at line 49 of file reduce_alt.c.

Referenced by reduce_ansAdv().

◆ 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().

Function Documentation

◆ 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

◆ 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

◆ getlecloseterms()

◆ ansProcessCandidate()

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

ans subtest

Parameters
scipSCIP data structure
ggraph data structure
markednodes array
countpointer to number of reductions
minvalue to not surpass
candvertexcandidate

Definition at line 1028 of file reduce_alt.c.

References EAT_LAST, FALSE, GRAPH::grad, graph_edge_del(), GRAPH::head, Is_pterm, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIPisGT(), SCIPisLE(), GRAPH::source, GRAPH::term, and TRUE.

Referenced by reduce_ans(), reduce_ansAdv(), and reduce_ansAdv2().

◆ 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
scipSCIP data structure
ggraph data structure
vnoiVoronoi data structure
edgepredsarray to store edge predecessors of auxiliary graph
mstsdistarray to store mst distances in auxiliary graph
heaparray representing a heap
statearray to indicate whether a node has been scanned during SP calculation
vbaseVoronoi base to each vertex
nodesidarray to map nodes in auxiliary graph to original ones
nodesorgarray to map terminals of original graph vertices of auxiliary graph
forbiddenarray to mark whether an edge may be eliminated
nelimspoint to store number of deleted edges
nodereplacingshould node replacement (by edges) be performed?
edgestatearray to store status of (directed) edge (for propagation, can otherwise be set to NULL)

Definition at line 1105 of file reduce_alt.c.

References GRAPH::cost, shortest_path::dist, EAT_FREE, EAT_LAST, shortest_path::edge, EDGE_BLOCKED, GRAPH::edges, FALSE, flipedge, getlecloseterms(), GRAPH::grad, graph_edge_add(), graph_edge_del(), graph_free(), graph_get4nextTerms(), graph_init(), graph_knot_add(), graph_knot_chg(), graph_path_exec(), graph_path_exit(), graph_path_init(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, MST_MODE, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, reduce_bdr(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisEQ(), SCIPisGE(), SCIPisGT(), SCIPisLT(), sddeltable(), GRAPH::source, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

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
scipSCIP data structure
ggraph data structure
vnoiVoronoi data structure
heapheap array
statearray to store state of a node during Voronoi computation
vbaseVoronoi base to each node
nodesidarray
nodesorgarray
nelimspointer to store number of eliminated edges

Definition at line 1499 of file reduce_alt.c.

References GRAPH::cost, shortest_path::dist, EAT_FREE, EAT_LAST, GRAPH::edges, FARAWAY, flipedge, getcloseterms(), getcloseterms2term(), GRAPH::grad, graph_edge_add(), graph_edge_del(), graph_free(), graph_get4nextTerms(), graph_get4nextTTerms(), graph_init(), graph_knot_add(), graph_valid(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisGT(), SCIPisLT(), GRAPH::source, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

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
scipSCIP data structure
ggraph structure
netgraphauxiliary graph structure
mstMST structure
vnoipath structure
mstsdistMST distance in aux-graph
termdist1dist array
termdist2second dist array
sd_initialinitial sd or -1.0
vbasebases for nearest terminals
nodesidnodes identification array
neighbterms1neighbour terminals array
neighbterms2second neighbour terminals array
ifirst vertex
i2second vertex
limitlimit for incident edges to consider

Definition at line 1777 of file reduce_alt.c.

References GRAPH::cost, EAT_LAST, shortest_path::edge, FARAWAY, getcloseterms(), GRAPH::head, Is_term, GRAPH::knots, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Real, SCIPisGT(), SCIPisLT(), GRAPH::tail, and GRAPH::term.

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 
)

◆ 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 
)

◆ 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.

References GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, GRAPH::edges, FARAWAY, flipedge, GRAPH::grad, graph_edge_del(), graph_sdPaths(), GRAPH::head, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisGE(), SCIPisGT(), TRUE, and UNKNOWN.

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 
)

◆ 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
scipSCIP data structure
ggraph structure
netgraphauxiliary graph structure
netmstMST structure
vnoipath structure
mstsdistMST distance in aux-graph
termdist1dist array
termdist2second dist array
vbasebases for nearest terminals
nodesidnodes identification array
neighbterms1neighbour terminals array
neighbterms2second neighbour terminals array
nelimsnumber of eliminations

Definition at line 2747 of file reduce_alt.c.

References GRAPH::cost, shortest_path::dist, EAT_LAST, GRAPH::edges, FALSE, flipedge, getRSD(), GRAPH::grad, graph_edge_add(), graph_free(), graph_init(), graph_knot_add(), graph_knot_delPseudo(), graph_path_exec(), graph_path_exit(), graph_path_init(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, MST_MODE, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, STP_BDR_MAXDEGREE, STP_BDR_MAXDNEDGES, STP_PCSPG, STP_RPCSPG, GRAPH::stp_type, GRAPH::term, TRUE, and UNKNOWN.

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
scipSCIP data structure
ggraph structure
pathtailarray for internal use
pathheadarray for internal use
heaparray for internal use
statetailarray for internal use
stateheadarray for internal use
memlbltailarray for internal use
memlblheadarray for internal use
nelimspoint to return number of eliminations
limitlimit for edges to consider for each vertex

Definition at line 2964 of file reduce_alt.c.

References GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, FALSE, FARAWAY, flipedge, GRAPH::grad, graph_edge_add(), graph_free(), graph_init(), graph_knot_add(), graph_knot_delPseudo(), graph_path_exec(), graph_path_exit(), graph_path_init(), graph_valid(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, MST_MODE, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, reduce_getSd(), reduce_getSdPcMw(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArrayNull, SCIPisGE(), SCIPisLE(), SCIPisLT(), STP_BD_MAXDEGREE, STP_BD_MAXDNEDGES, STP_PCSPG, STP_RPCSPG, GRAPH::stp_type, GRAPH::term, TRUE, and UNKNOWN.

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
scipSCIP data structure
ggraph structure
pathtailarray for internal use
pathheadarray for internal use
heaparray for internal use
statetailarray for internal use
stateheadarray for internal use
memlbltailarray for internal use
memlblheadarray for internal use
nelimspoint to return number of eliminations
limitlimit for edges to consider for each vertex

Definition at line 3217 of file reduce_alt.c.

References GRAPH::cost, shortest_path::dist, EAT_FREE, EAT_LAST, shortest_path::edge, GRAPH::edges, FALSE, FARAWAY, flipedge, GRAPH::grad, graph_edge_add(), graph_free(), graph_init(), graph_knot_add(), graph_path_exec(), graph_path_exit(), graph_path_init(), graph_valid(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, MST_MODE, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, reduce_getSd(), reduce_getSdPcMw(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArrayNull, SCIPisGE(), SCIPisGT(), SCIPisLT(), STP_BD_MAXDEGREE, STP_BD_MAXDNEDGES, STP_PCSPG, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, TRUE, and UNKNOWN.

◆ 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
scipSCIP data structure
ggraph data structure
vnoiVoronoi data structure
fixedoffset pointer
heapheap array
stateshortest path array
vbaseVoronoi/shortest path bases array
vrnodesVoronoi/shortest path array
visitedVoronoi/shortest path array
solnodenode array to mark whether an node is part of a given solution (CONNECT), or NULL
nelimspointer to store number of eliminations

Definition at line 3483 of file reduce_alt.c.

References GRAPH::ancestors, GRAPH::cost, shortest_path::dist, EAT_LAST, FALSE, FARAWAY, GRAPH::fixedges, GRAPH::grad, graph_knot_chg(), graph_knot_contract(), graph_pc_contractEdge(), graph_voronoiTerms(), GRAPH::head, Is_pterm, Is_term, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPintListNodeAppendCopy(), SCIPisGE(), SCIPisLE(), SCIPisLT(), SCIPqueueCreate(), SCIPqueueFree(), SCIPqueueInsert(), SCIPqueueIsEmpty(), SCIPqueueRemove(), GRAPH::source, STP_PCSPG, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

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
scipSCIP data structure
ggraph data structure
vnoiVoronoi data structure
fixedoffset pointer
edgearrintedge int array for internal computations
heapheap array
statearray for internal computations
vbasearray for internal computations
solnodenode array to mark whether an node is part of a given solution (CONNECT), or NULL
nelimspointer to store number of eliminations

Definition at line 3710 of file reduce_alt.c.

References GRAPH::ancestors, GRAPH::cost, shortest_path::dist, EAT_LAST, FARAWAY, GRAPH::fixedges, GRAPH::grad, graph_knot_contract(), graph_pc_contractEdge(), graph_voronoiWithDist(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPintListNodeAppendCopy(), SCIPisGE(), SCIPisLE(), GRAPH::source, STP_PCSPG, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, and UNKNOWN.

◆ reduce_nvAdv()

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
scipSCIP data structure
ggraph data structure
vnoiVoronoi data structure
distancenodes-sized distance array
fixedoffset pointer
edgearrintedges-sized array
heapheap array
stateshortest path array
vbaseVoronoi base array
neighbnodes-sized neighborhood array
distnodenodes-sized distance array
solnodenode array to mark whether an node is part of a given solution (CONNECT), or NULL
nelimspointer to store number of eliminations

Definition at line 3903 of file reduce_alt.c.

References GRAPH::ancestors, GRAPH::cost, shortest_path::dist, EAT_LAST, FALSE, FARAWAY, GRAPH::fixedges, flipedge, GRAPH::grad, graph_knot_contract(), graph_pc_contractEdge(), graph_voronoiWithDist(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPintListNodeAppendCopy(), SCIPisGE(), SCIPisLE(), SCIPisLT(), GRAPH::source, STP_PCSPG, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by nvreduce_sl().

◆ reduce_ledge()

◆ reduce_ans()

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

adjacent neighbourhood reduction for the MWCSP

Parameters
scipSCIP data structure
ggraph data structure
markednodes array
countpointer to number of reductions

Definition at line 4447 of file reduce_alt.c.

References ansProcessCandidate(), EAT_LAST, FALSE, GRAPH::grad, graph_valid(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Real, SCIPisLT(), STP_MWCSP, STP_RED_ANSMAXNEIGHBORS, GRAPH::stp_type, GRAPH::term, and TRUE.

Referenced by redLoopMw().

◆ reduce_ansAdv()

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

advanced adjacent neighbourhood reduction for the MWCSP

Parameters
scipSCIP data structure
ggraph data structure
markednodes array
countpointer to number of performed reductions
extneigbhooduse extended neighbour hood

Definition at line 4515 of file reduce_alt.c.

References ansProcessCandidate(), EAT_LAST, FALSE, GRAPH::grad, graph_valid(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, MAX, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Real, SCIPdebugMessage, SCIPisGT(), SCIPisLE(), STP_MWCSP, STP_RED_ANSEXMAXCANDS, STP_RED_ANSMAXCANDS, STP_RED_CNSNN, GRAPH::stp_type, GRAPH::term, and TRUE.

Referenced by redLoopMw().

◆ reduce_ansAdv2()

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

alternative advanced adjacent neighbourhood reduction for the MWCSP

Parameters
scipSCIP data structure
ggraph data structure
markednodes array
countpointer to number of reductions

Definition at line 4621 of file reduce_alt.c.

References ansProcessCandidate(), EAT_LAST, FALSE, GRAPH::grad, graph_valid(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Real, SCIPisGE(), SCIPisGT(), SCIPisLE(), STP_MWCSP, STP_RED_CNSNN, GRAPH::stp_type, GRAPH::term, TRUE, and UNKNOWN.

Referenced by redLoopMw().

◆ reduce_cnsAdv()

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

advanced connected neighborhood subset reduction test for the MWCSP

Parameters
scipSCIP data structure
ggraph data structure
markednodes array for internal use
countpointer to number of reductions

Definition at line 4748 of file reduce_alt.c.

References EAT_LAST, FALSE, GRAPH::grad, graph_edge_del(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_OKAY, SCIP_Real, SCIPisGE(), SCIPisGT(), SCIPisLE(), STP_MWCSP, STP_RED_CNSNN, GRAPH::stp_type, GRAPH::term, TRUE, UNKNOWN, VERTEX_CONNECT, VERTEX_NEIGHBOR, VERTEX_OTHER, and VERTEX_TEMPNEIGHBOR.

◆ 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 
)

◆ 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 
)

◆ reduce_nnp()

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

non-negative path reduction for the MWCSP

Parameters
scipSCIP data structure
ggraph data structure
markednodes array
countpointer to number of reductions

Definition at line 5450 of file reduce_alt.c.

References EAT_LAST, FALSE, graph_edge_del(), graph_valid(), GRAPH::head, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, STP_MWCSP, GRAPH::stp_type, and TRUE.

Referenced by redLoopMw().