Scippy

SCIP

Solving Constraint Integer Programs

prop_stp.c File Reference

Detailed Description

propagator for Steiner tree problems, using the LP reduced costs

Author
Daniel Rehfeldt

This propagator makes use of the reduced cost of an optimally solved LP relaxation to propagate the variables

Definition in file prop_stp.c.

#include <assert.h>
#include <string.h>
#include "prop_stp.h"

Go to the source code of this file.

Macros

Propagator properties
#define PROP_NAME   "stp"
 
#define PROP_DESC   "stp propagator"
 
#define PROP_TIMING   SCIP_PROPTIMING_DURINGLPLOOP | SCIP_PROPTIMING_AFTERLPLOOP
 
#define PROP_PRIORITY   +1000000
 
#define PROP_FREQ   1
 
#define PROP_DELAY   FALSE
 
Default parameter values
#define DEFAULT_MAXNWAITINGROUNDS   3
 

Functions

Local methods
SCIP_RETCODE fixedgevar (SCIP *scip, SCIP_VAR *edgevar, int *nfixed)
 
Callback methods of propagator
static SCIP_DECL_PROPCOPY (propCopyStp)
 
static SCIP_DECL_PROPFREE (propFreeStp)
 
static SCIP_DECL_PROPEXEC (propExecStp)
 
Interface methods
SCIP_RETCODE SCIPincludePropStp (SCIP *scip)
 

Macro Definition Documentation

#define DEFAULT_MAXNWAITINGROUNDS   3

maximal number of rounds to wait until propagating again

Definition at line 51 of file prop_stp.c.

Referenced by SCIP_DECL_PROPEXEC().

#define PROP_DELAY   FALSE

should propagation method be delayed, if other propagators found reductions?

Definition at line 42 of file prop_stp.c.

Referenced by SCIPincludePropStp().

#define PROP_DESC   "stp propagator"

Definition at line 38 of file prop_stp.c.

Referenced by SCIPincludePropStp().

#define PROP_FREQ   1

propagator frequency

Definition at line 41 of file prop_stp.c.

Referenced by SCIPincludePropStp().

#define PROP_NAME   "stp"

Definition at line 37 of file prop_stp.c.

Referenced by SCIP_DECL_PROPCOPY(), and SCIPincludePropStp().

#define PROP_PRIORITY   +1000000

propagator priority

Definition at line 40 of file prop_stp.c.

Referenced by SCIPincludePropStp().

#define PROP_TIMING   SCIP_PROPTIMING_DURINGLPLOOP | SCIP_PROPTIMING_AFTERLPLOOP

Definition at line 39 of file prop_stp.c.

Referenced by SCIPincludePropStp().

Function Documentation

SCIP_RETCODE fixedgevar ( SCIP *  scip,
SCIP_VAR *  edgevar,
int *  nfixed 
)

fix a variable (corresponding to an edge) to zero

Parameters
scipSCIP data structure
edgevarthe variable to be fixed
nfixedcounter that is incriminated if variable could be fixed

Definition at line 76 of file prop_stp.c.

Referenced by hcrcbound_reduce(), and SCIP_DECL_PROPEXEC().

static SCIP_DECL_PROPCOPY ( propCopyStp  )
static

copy method for propagator plugins (called when SCIP copies plugins)

Definition at line 100 of file prop_stp.c.

References PROP_NAME, and SCIPincludePropStp().

static SCIP_DECL_PROPEXEC ( propExecStp  )
static

reduced cost propagation method for an LP solution

Definition at line 133 of file prop_stp.c.

References DEFAULT_MAXNWAITINGROUNDS, shortest_path::dist, EAT_LAST, GRAPH::edges, FARAWAY, fixedgevar(), flipedge, GRAPH::grad, graph_path_execX(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, SCIPprobdataGetGraph(), SCIPprobdataGetVars(), GRAPH::source, STP_MAX_NODE_WEIGHT, STP_PRIZE_COLLECTING, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, GRAPH::term, and voronoi_terms().

static SCIP_DECL_PROPFREE ( propFreeStp  )
static

destructor of propagator to free user data (called when SCIP is exiting)

Definition at line 115 of file prop_stp.c.

SCIP_RETCODE SCIPincludePropStp ( SCIP *  scip)

creates the stp propagator and includes it in SCIP

Parameters
scipSCIP data structure

Definition at line 342 of file prop_stp.c.

References PROP_DELAY, PROP_DESC, PROP_FREQ, PROP_NAME, PROP_PRIORITY, and PROP_TIMING.

Referenced by runShell(), and SCIP_DECL_PROPCOPY().