Scippy

SCIP

Solving Constraint Integer Programs

heur_slackprune.c File Reference

Detailed Description

dual-ascent and reduction based primal heuristic for Steiner problems

Author
Daniel Rehfeldt

This file implements a dual-ascent and reduction based heuristic for Steiner problems. It is based on an approach described in T. Polzin's "Algorithms for the Steiner problem in networks".

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

Definition in file heur_slackprune.c.

#include <assert.h>
#include <string.h>
#include <stdio.h>
#include "scip/scip.h"
#include "scip/scipdefplugins.h"
#include "scip/cons_linear.h"
#include "heur_slackprune.h"
#include "heur_ascendprune.h"
#include "heur_local.h"
#include "heur_prune.h"
#include "grph.h"
#include "heur_tm.h"
#include "cons_stp.h"
#include "scip/pub_misc.h"
#include "probdata_stp.h"
#include "prop_stp.h"

Go to the source code of this file.

Macros

#define HEUR_NAME   "slackprune"
 
#define HEUR_DESC   "Reduction based heuristic for Steiner problems"
 
#define HEUR_DISPCHAR   'S'
 
#define HEUR_PRIORITY   1
 
#define HEUR_FREQ   1
 
#define HEUR_FREQOFS   0
 
#define HEUR_MAXDEPTH   -1
 
#define HEUR_TIMING   (SCIP_HEURTIMING_DURINGLPLOOP | SCIP_HEURTIMING_AFTERLPLOOP | SCIP_HEURTIMING_AFTERNODE)
 
#define HEUR_USESSUBSCIP   FALSE
 
#define DEFAULT_SLACKPRUNE_MAXFREQ   FALSE
 
#define SLACKPRUNE_MINREDELIMS   2
 
#define SLACKPRUNE_MAXREDROUNDS   10
 
#define SLACKPRUNE_MINSTALLPROPORTION   0.25
 
#define SLACKPRUNE_MAXSTALLPROPORTION   0.5
 
#define BREAKONERROR   FALSE
 
#define MAXNTERMINALS   500
 
#define MAXNEDGES   10000
 
#define SLACK_MAXTOTNEDGES   5000
 

Functions

static int getRedBound (int nrounds, int nedges)
 
static void setMinMaxElims (SCIP *scip, int *minnelims, int *lminnelims, int annodes, int anedges, int anterms, int nround, int maxnrounds)
 
static void updateSolNodeArray (GRAPH *graph, int *soledge, int *solnode, int nnodes, int nnedges)
 
static SCIP_DECL_HEURCOPY (heurCopySlackPrune)
 
static SCIP_DECL_HEURFREE (heurFreeSlackPrune)
 
static SCIP_DECL_HEURINIT (heurInitSlackPrune)
 
static SCIP_DECL_HEURINITSOL (heurInitsolSlackPrune)
 
static SCIP_DECL_HEUREXITSOL (heurExitsolSlackPrune)
 
static SCIP_DECL_HEUREXEC (heurExecSlackPrune)
 
SCIP_RETCODE SCIPStpHeurSlackPruneRun (SCIP *scip, SCIP_VAR **vars, GRAPH *g, int *soledge, SCIP_Bool *success, SCIP_Bool reducegraph, SCIP_Bool fullreduce)
 
SCIP_RETCODE SCIPStpHeurSlackPruneRunPcMw (SCIP *scip, SCIP_VAR **vars, GRAPH *g, int *soledge, SCIP_Bool *success)
 
SCIP_RETCODE SCIPStpIncludeHeurSlackPrune (SCIP *scip)
 

Macro Definition Documentation

◆ HEUR_NAME

#define HEUR_NAME   "slackprune"

◆ HEUR_DESC

#define HEUR_DESC   "Reduction based heuristic for Steiner problems"

Definition at line 46 of file heur_slackprune.c.

Referenced by SCIPStpIncludeHeurSlackPrune().

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR   'S'

Definition at line 47 of file heur_slackprune.c.

Referenced by SCIPStpIncludeHeurSlackPrune().

◆ HEUR_PRIORITY

#define HEUR_PRIORITY   1

Definition at line 48 of file heur_slackprune.c.

Referenced by SCIPStpIncludeHeurSlackPrune().

◆ HEUR_FREQ

#define HEUR_FREQ   1

Definition at line 49 of file heur_slackprune.c.

Referenced by SCIPStpIncludeHeurSlackPrune().

◆ HEUR_FREQOFS

#define HEUR_FREQOFS   0

Definition at line 50 of file heur_slackprune.c.

Referenced by SCIPStpIncludeHeurSlackPrune().

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH   -1

Definition at line 51 of file heur_slackprune.c.

Referenced by SCIPStpIncludeHeurSlackPrune().

◆ HEUR_TIMING

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP   FALSE

does the heuristic use a secondary SCIP instance?

Definition at line 53 of file heur_slackprune.c.

Referenced by SCIPStpIncludeHeurSlackPrune().

◆ DEFAULT_SLACKPRUNE_MAXFREQ

#define DEFAULT_SLACKPRUNE_MAXFREQ   FALSE

executions of the heuristic at maximum frequency?

Definition at line 55 of file heur_slackprune.c.

Referenced by SCIPStpIncludeHeurSlackPrune().

◆ SLACKPRUNE_MINREDELIMS

#define SLACKPRUNE_MINREDELIMS   2

minimum number of eliminations for reduction package when called by slack-and-prune heuristic

Definition at line 56 of file heur_slackprune.c.

Referenced by getRedBound(), and setMinMaxElims().

◆ SLACKPRUNE_MAXREDROUNDS

#define SLACKPRUNE_MAXREDROUNDS   10

maximum number of reduction rounds in slack-prune heuristic

Definition at line 57 of file heur_slackprune.c.

Referenced by SCIPStpHeurSlackPruneRun(), and SCIPStpHeurSlackPruneRunPcMw().

◆ SLACKPRUNE_MINSTALLPROPORTION

#define SLACKPRUNE_MINSTALLPROPORTION   0.25

minimum proportion of arcs to be fixed before restarting slack-prune heuristic

Definition at line 58 of file heur_slackprune.c.

Referenced by SCIP_DECL_HEUREXEC().

◆ SLACKPRUNE_MAXSTALLPROPORTION

#define SLACKPRUNE_MAXSTALLPROPORTION   0.5

maximum proportion of arcs to be fixed before restarting slack-prune heuristic

Definition at line 59 of file heur_slackprune.c.

Referenced by SCIP_DECL_HEUREXEC().

◆ BREAKONERROR

#define BREAKONERROR   FALSE

Definition at line 60 of file heur_slackprune.c.

◆ MAXNTERMINALS

#define MAXNTERMINALS   500

Definition at line 61 of file heur_slackprune.c.

Referenced by SCIP_DECL_HEUREXEC().

◆ MAXNEDGES

#define MAXNEDGES   10000

Definition at line 62 of file heur_slackprune.c.

Referenced by SCIP_DECL_HEUREXEC().

◆ SLACK_MAXTOTNEDGES

#define SLACK_MAXTOTNEDGES   5000

Definition at line 63 of file heur_slackprune.c.

Referenced by SCIP_DECL_HEUREXEC().

Function Documentation

◆ getRedBound()

static int getRedBound ( int  nrounds,
int  nedges 
)
static

Definition at line 88 of file heur_slackprune.c.

References MAX, and SLACKPRUNE_MINREDELIMS.

Referenced by SCIPStpHeurSlackPruneRun(), and SCIPStpHeurSlackPruneRunPcMw().

◆ setMinMaxElims()

static void setMinMaxElims ( SCIP scip,
int *  minnelims,
int *  lminnelims,
int  annodes,
int  anedges,
int  anterms,
int  nround,
int  maxnrounds 
)
static

◆ updateSolNodeArray()

static void updateSolNodeArray ( GRAPH graph,
int *  soledge,
int *  solnode,
int  nnodes,
int  nnedges 
)
static

◆ SCIP_DECL_HEURCOPY()

static SCIP_DECL_HEURCOPY ( heurCopySlackPrune  )
static

copy method for primal heuristic plugins (called when SCIP copies plugins)

Definition at line 267 of file heur_slackprune.c.

References HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPStpIncludeHeurSlackPrune().

◆ SCIP_DECL_HEURFREE()

static SCIP_DECL_HEURFREE ( heurFreeSlackPrune  )
static

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

Definition at line 281 of file heur_slackprune.c.

References NULL, SCIP_OKAY, SCIPfreeMemory, SCIPheurGetData(), and SCIPheurSetData().

◆ SCIP_DECL_HEURINIT()

static SCIP_DECL_HEURINIT ( heurInitSlackPrune  )
static

initialization method of primal heuristic (called after problem was transformed)

Definition at line 303 of file heur_slackprune.c.

References SCIP_OKAY.

◆ SCIP_DECL_HEURINITSOL()

static SCIP_DECL_HEURINITSOL ( heurInitsolSlackPrune  )
static

solving process initialization method of primal heuristic (called when branch and bound process is about to begin)

Definition at line 313 of file heur_slackprune.c.

References NULL, SCIP_OKAY, and SCIPheurGetData().

◆ SCIP_DECL_HEUREXITSOL()

static SCIP_DECL_HEUREXITSOL ( heurExitsolSlackPrune  )
static

solving process deinitialization method of primal heuristic (called before branch and bound process data is freed)

Definition at line 336 of file heur_slackprune.c.

References SCIP_OKAY.

◆ SCIP_DECL_HEUREXEC()

◆ SCIPStpHeurSlackPruneRun()

SCIP_RETCODE SCIPStpHeurSlackPruneRun ( SCIP scip,
SCIP_VAR **  vars,
GRAPH g,
int *  soledge,
SCIP_Bool success,
SCIP_Bool  reducegraph,
SCIP_Bool  fullreduce 
)

◆ SCIPStpHeurSlackPruneRunPcMw()

◆ SCIPStpIncludeHeurSlackPrune()

SCIP_RETCODE SCIPStpIncludeHeurSlackPrune ( SCIP scip)