Scippy

SCIP

Solving Constraint Integer Programs

reduce_simple.c File Reference

Detailed Description

several basic reductions for Steiner tree problems

Author
Daniel Rehfeldt

This file implements basic reduction techniques for several Steiner problems. All tests are described in "A Generic Approach to Solving the Steiner Tree Problem and Variants" by Daniel Rehfeldt.

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

Definition in file reduce_simple.c.

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

Go to the source code of this file.

Functions

static SCIP_Bool adjterms (const GRAPH *g)
 
static unsigned nchains (const GRAPH *g)
 
static SCIP_Bool is_maxprize (SCIP *scip, const GRAPH *g, int i, SCIP_Real *maxprize)
 
static SCIP_RETCODE trydg1edgepc (SCIP *scip, GRAPH *g, SCIP_Real *offset, int *solnode, int *count, int i, int iout, SCIP_Bool *rerun, SCIP_Real *maxprize)
 
static SCIP_RETCODE traverseChain (SCIP *scip, GRAPH *g, int *length, int *final, int i, int i1, int i2, int e1)
 
static void adjust0term (SCIP *scip, GRAPH *g, int i)
 
SCIP_RETCODE reduce_contractZeroEdges (SCIP *scip, GRAPH *g, SCIP_Bool savehistory)
 
SCIP_RETCODE reduce_simple (SCIP *scip, GRAPH *g, SCIP_Real *fixed, int *solnode, int *nelims, int *edgestate)
 
SCIP_RETCODE reduce_simple_sap (SCIP *scip, GRAPH *g, SCIP_Real *fixed, int *count)
 
SCIP_RETCODE reduce_rpt (SCIP *scip, GRAPH *g, SCIP_Real *fixed, int *count)
 
SCIP_RETCODE reduce_simple_mw (SCIP *scip, GRAPH *g, int *solnode, SCIP_Real *fixed, int *count)
 
SCIP_RETCODE reduce_simple_hc (SCIP *scip, GRAPH *g, SCIP_Real *fixed, int *count)
 
SCIP_RETCODE reduce_simple_pc (SCIP *scip, GRAPH *g, SCIP_Real *fixed, int *count, int *solnode, SCIP_Bool contractroot)
 

Function Documentation

◆ adjterms()

static SCIP_Bool adjterms ( const GRAPH g)
static

check whether problem has adjacent terminals

Parameters
ggraph data structure

Definition at line 39 of file reduce_simple.c.

References EAT_FREE, GRAPH::edges, FALSE, GRAPH::head, Is_term, GRAPH::mark, GRAPH::oeat, GRAPH::tail, GRAPH::term, and TRUE.

Referenced by reduce_simple_mw().

◆ nchains()

static unsigned nchains ( const GRAPH g)
static

count numbers of chains

Parameters
ggraph data structure

Definition at line 60 of file reduce_simple.c.

References EAT_FREE, GRAPH::edges, GRAPH::grad, GRAPH::head, Is_term, GRAPH::oeat, GRAPH::tail, and GRAPH::term.

Referenced by reduce_simple_mw().

◆ is_maxprize()

static SCIP_Bool is_maxprize ( SCIP scip,
const GRAPH g,
int  i,
SCIP_Real maxprize 
)
static

is there no vertex of higher prize?

Parameters
scipSCIP data structure
ggraph data structure
ithe terminal to be checked
maxprizestores incumbent prize (can be updated)

Definition at line 80 of file reduce_simple.c.

References FALSE, GRAPH::grad, Is_term, GRAPH::knots, GRAPH::mark, GRAPH::prize, SCIP_Real, SCIPdebugMessage, GRAPH::source, STP_RPCSPG, GRAPH::stp_type, GRAPH::term, and TRUE.

Referenced by reduce_simple_mw(), reduce_simple_pc(), and trydg1edgepc().

◆ trydg1edgepc()

static SCIP_RETCODE trydg1edgepc ( SCIP scip,
GRAPH g,
SCIP_Real offset,
int *  solnode,
int *  count,
int  i,
int  iout,
SCIP_Bool rerun,
SCIP_Real maxprize 
)
static

try to eliminate a terminal of degree one

Parameters
scipSCIP data structure
ggraph data structure
offsetpointer to store the offset
solnodesolution nodes or NULL
countpointer storing number of eliminated edges
ithe terminal to be checked
ioutoutgoing arc
rerunfurther eliminations possible?
maxprizestores incumbent prize (can be updated)

Definition at line 129 of file reduce_simple.c.

References GRAPH::ancestors, GRAPH::cost, EAT_LAST, GRAPH::fixedges, flipedge, GRAPH::grad, graph_edge_del(), graph_pc_contractEdge(), graph_pc_deleteTerm(), graph_pc_knot2nonTerm(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, is_maxprize(), Is_pterm, Is_term, GRAPH::mark, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::pcancestors, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, SCIPintListNodeAppendCopy(), SCIPintListNodeFree(), SCIPisGE(), SCIPisGT(), SCIPisLE(), GRAPH::source, STP_MWCSP, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, TRUE, and UNKNOWN.

Referenced by reduce_simple_mw(), and reduce_simple_pc().

◆ traverseChain()

static SCIP_RETCODE traverseChain ( SCIP scip,
GRAPH g,
int *  length,
int *  final,
int  i,
int  i1,
int  i2,
int  e1 
)
static

traverse one side of a chain (MWCSP)

Parameters
scipSCIP data structure
ggraph data structure
lengthpointer to store length of chain
finalpointer to store final vertex
istart vertex
i1first vertex
i2last vertex
e1first edge

Definition at line 306 of file reduce_simple.c.

References GRAPH::ancestors, GRAPH::cost, EAT_LAST, flipedge, GRAPH::grad, graph_edge_del(), graph_edge_redirect(), GRAPH::head, Is_term, GRAPH::mark, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPintListNodeAppendCopy(), SCIPintListNodeFree(), SCIPisGE(), SCIPisLE(), GRAPH::term, and TRUE.

Referenced by reduce_simple_mw().

◆ adjust0term()

static void adjust0term ( SCIP scip,
GRAPH g,
int  i 
)
static

adjust for a (rooted) PC or MW problem

Parameters
scipSCIP data structure
ggraph data structure
iindex of the terminal

Definition at line 402 of file reduce_simple.c.

References EAT_LAST, GRAPH::grad, graph_edge_del(), graph_pc_knot2nonTerm(), GRAPH::head, Is_pterm, Is_term, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIPisGT(), SCIPisZero(), GRAPH::source, STP_RPCSPG, GRAPH::stp_type, GRAPH::term, GRAPH::term2edge, TRUE, and UNKNOWN.

Referenced by reduce_simple_mw(), and reduce_simple_pc().

◆ reduce_contractZeroEdges()

SCIP_RETCODE reduce_contractZeroEdges ( SCIP scip,
GRAPH g,
SCIP_Bool  savehistory 
)

contract edges of weight zero

Parameters
scipSCIP data structure
ggraph data structure
savehistorysave the history?

Definition at line 453 of file reduce_simple.c.

References GRAPH::ancestors, GRAPH::cost, EAT_FREE, GRAPH::edges, GRAPH::fixedges, flipedge, graph_knot_contract(), GRAPH::head, NULL, GRAPH::oeat, SCIP_CALL, SCIP_OKAY, SCIPintListNodeAppendCopy(), SCIPisZero(), and GRAPH::tail.

Referenced by redbasedVarfixing(), and redLoopStp().

◆ reduce_simple()

SCIP_RETCODE reduce_simple ( SCIP scip,
GRAPH g,
SCIP_Real fixed,
int *  solnode,
int *  nelims,
int *  edgestate 
)

basic reduction tests for the STP

Parameters
scipSCIP data structure
ggraph data structure
fixedpointer to offset value
solnodenode array to mark whether an node is part of a given solution (CONNECT), or NULL
nelimspointer to number of reductions
edgestatearray to store status of (directed) edge (for propagation, can otherwise be set to NULL)

Definition at line 489 of file reduce_simple.c.

References GRAPH::ancestors, GRAPH::cost, EAT_LAST, Edge_anti, EDGE_BLOCKED, EQ, FALSE, FARAWAY, GRAPH::fixedges, flipedge, GRAPH::grad, graph_edge_del(), graph_knot_contract(), graph_knot_contractLowdeg2High(), graph_valid(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPintListNodeAppendCopy(), SCIPisLE(), SCIPisLT(), GRAPH::term, TRUE, and UNKNOWN.

Referenced by nvreduce_sl(), and redLoopStp().

◆ reduce_simple_sap()

SCIP_RETCODE reduce_simple_sap ( SCIP scip,
GRAPH g,
SCIP_Real fixed,
int *  count 
)

◆ reduce_rpt()

SCIP_RETCODE reduce_rpt ( SCIP scip,
GRAPH g,
SCIP_Real fixed,
int *  count 
)

root proximity terminal test (SAP)

Parameters
scipSCIP data structure
ggraph data structure
fixedpointer to offset value
countpointer to number of reductions

Definition at line 884 of file reduce_simple.c.

References GRAPH::ancestors, GRAPH::cost, EAT_LAST, GRAPH::fixedges, GRAPH::grad, graph_knot_contract(), graph_path_execX(), GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, nnodes, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPintListNodeAppendCopy(), SCIPisGT(), GRAPH::source, GRAPH::tail, and GRAPH::term.

Referenced by reduceSap().

◆ reduce_simple_mw()

SCIP_RETCODE reduce_simple_mw ( SCIP scip,
GRAPH g,
int *  solnode,
SCIP_Real fixed,
int *  count 
)

basic reduction tests for the MWCS problem

Parameters
scipSCIP data structure
ggraph data structure
solnodearray to indicate whether a node is part of the current solution (==CONNECT)
fixedpointer to offset value
countpointer to number of reductions

Definition at line 953 of file reduce_simple.c.

References adjterms(), adjust0term(), GRAPH::cost, EAT_LAST, Edge_anti, FALSE, flipedge_Uint, GRAPH::grad, graph_edge_del(), graph_knot_contract(), graph_pc_contractEdge(), graph_pc_contractEdgeAncestors(), graph_pc_deleteTerm(), graph_valid(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, is_maxprize(), Is_pterm, Is_term, GRAPH::knots, level0save(), GRAPH::mark, nchains(), nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisGE(), SCIPisLE(), SCIPisZero(), GRAPH::source, STP_MWCSP, GRAPH::stp_type, GRAPH::tail, GRAPH::term, traverseChain(), TRUE, and trydg1edgepc().

Referenced by redLoopMw().

◆ reduce_simple_hc()

SCIP_RETCODE reduce_simple_hc ( SCIP scip,
GRAPH g,
SCIP_Real fixed,
int *  count 
)

basic reduction tests for the HCDSTP

Parameters
scipSCIP data structure
ggraph data structure
fixedpointer to offfset value
countpointer to number of reductions

Definition at line 1252 of file reduce_simple.c.

References GRAPH::cost, EAT_LAST, FALSE, FARAWAY, flipedge, graph_edge_del(), GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_OKAY, SCIPdebugMessage, SCIPisGE(), SCIPisLT(), GRAPH::source, STP_DHCSTP, GRAPH::stp_type, GRAPH::term, and TRUE.

Referenced by reduceHc().

◆ reduce_simple_pc()

SCIP_RETCODE reduce_simple_pc ( SCIP scip,
GRAPH g,
SCIP_Real fixed,
int *  count,
int *  solnode,
SCIP_Bool  contractroot 
)