# SCIP

Solving Constraint Integer Programs

heur_vbounds.c File Reference

## Detailed Description

LNS heuristic uses the variable lower and upper bounds to determine the search neighborhood.

More details about the heuristic can be found in
Structure-Based Primal Heuristics for Mixed Integer Programming
Gerald Gamrath, Timo Berthold, Stefan Heinz, and Michael Winkler
Optimization in the Real World, Volume 13 of the series Mathematics for Industry, pp 37-53
Preliminary version available as ZIB-Report 15-26.

Definition in file heur_vbounds.c.

#include <assert.h>
#include <string.h>
#include "scip/scip.h"
#include "scip/scipdefplugins.h"
#include "scip/heur_vbounds.h"

Go to the source code of this file.

## Macros

#define HEUR_NAME   "vbounds"

#define HEUR_DESC   "LNS heuristic uses the variable lower and upper bounds to determine the search neighborhood"

#define HEUR_DISPCHAR   'V'

#define HEUR_PRIORITY   -1106000

#define HEUR_FREQ   -1

#define HEUR_FREQOFS   0

#define HEUR_MAXDEPTH   -1

#define HEUR_TIMING   SCIP_HEURTIMING_BEFORENODE

#define HEUR_USESSUBSCIP   TRUE

#define DEFAULT_MAXNODES   5000LL /* maximum number of nodes to regard in the subproblem */

#define DEFAULT_MINFIXINGRATE   0.25 /* minimum percentage of integer variables that have to be fixed */

#define DEFAULT_MINIMPROVE   0.01 /* factor by which vbounds heuristic should at least improve the incumbent */

#define DEFAULT_MINNODES   500LL /* minimum number of nodes to regard in the subproblem */

#define DEFAULT_NODESOFS   500LL /* number of nodes added to the contingent of the total nodes */

#define DEFAULT_NODESQUOT   0.1 /* subproblem nodes in relation to nodes of the original problem */

#define DEFAULT_MAXPROPROUNDS   2 /* maximum number of propagation rounds during probing */

#define DEFAULT_COPYCUTS   TRUE

## Propagator defines

The propagator works on indices representing a bound of a variable. This index will be called bound index in the following. For a given active variable with problem index i (note that active variables have problem indices between 0 and nactivevariable - 1), the bound index of its lower bound is 2*i, the bound index of its upper bound is 2*i + 1. The other way around, a given bound index i corresponds to the variable with problem index i/2 (rounded down), and to the lower bound, if i is even, to the upper bound if i is odd. The following macros can be used to convert bound index into variable problem index and boundtype and vice versa.

#define getLbIndex(idx)   (2*(idx))

#define getUbIndex(idx)   (2*(idx)+1)

#define getVarIndex(idx)   ((idx)/2)

#define getBoundtype(idx)   (((idx) % 2 == 0) ? SCIP_BOUNDTYPE_LOWER : SCIP_BOUNDTYPE_UPPER)

#define isIndexLowerbound(idx)   ((idx) % 2 == 0)

static void heurdataReset (SCIP_HEURDATA *heurdata)

static SCIP_RETCODE dfs (SCIP *scip, int startnode, SCIP_Bool *visited, int *dfsstack, int *stacknextedge, int *dfsnodes, int *ndfsnodes)

static SCIP_RETCODE topologicalSort (SCIP *scip, int *vbvars, int *nvbvars)

static SCIP_RETCODE initializeCandsLists (SCIP *scip, SCIP_HEURDATA *heurdata)

static SCIP_RETCODE applyVboundsFixings (SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **vars, int nvbvars, SCIP_Bool tighten, SCIP_Bool obj, SCIP_Bool *infeasible, SCIP_VAR **lastvar, SCIP_Bool *fixedtolb)

static SCIP_RETCODE createNewSol (SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_SOL *newsol, SCIP_SOL *subsol, SCIP_Bool *success)

static SCIP_RETCODE applyVbounds (SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, SCIP_VAR **vbvars, int nvbvars, SCIP_Bool tighten, SCIP_Bool obj, SCIP_RESULT *result)

static SCIP_DECL_HEURCOPY (heurCopyVbounds)

static SCIP_DECL_HEURFREE (heurFreeVbounds)

static SCIP_DECL_HEUREXITSOL (heurExitsolVbounds)

static SCIP_DECL_HEUREXEC (heurExecVbounds)

SCIP_RETCODE SCIPincludeHeurVbounds (SCIP *scip)

## ◆ HEUR_NAME

 #define HEUR_NAME   "vbounds"

Definition at line 46 of file heur_vbounds.c.

Referenced by applyVbounds(), and SCIPincludeHeurVbounds().

## ◆ HEUR_DESC

 #define HEUR_DESC   "LNS heuristic uses the variable lower and upper bounds to determine the search neighborhood"

Definition at line 47 of file heur_vbounds.c.

Referenced by SCIPincludeHeurVbounds().

## ◆ HEUR_DISPCHAR

 #define HEUR_DISPCHAR   'V'

Definition at line 48 of file heur_vbounds.c.

Referenced by SCIPincludeHeurVbounds().

## ◆ HEUR_PRIORITY

 #define HEUR_PRIORITY   -1106000

Definition at line 49 of file heur_vbounds.c.

Referenced by SCIPincludeHeurVbounds().

## ◆ HEUR_FREQ

 #define HEUR_FREQ   -1

Definition at line 50 of file heur_vbounds.c.

Referenced by SCIPincludeHeurVbounds().

## ◆ HEUR_FREQOFS

 #define HEUR_FREQOFS   0

Definition at line 51 of file heur_vbounds.c.

Referenced by SCIPincludeHeurVbounds().

## ◆ HEUR_MAXDEPTH

 #define HEUR_MAXDEPTH   -1

Definition at line 52 of file heur_vbounds.c.

Referenced by SCIPincludeHeurVbounds().

## ◆ HEUR_TIMING

 #define HEUR_TIMING   SCIP_HEURTIMING_BEFORENODE

Definition at line 53 of file heur_vbounds.c.

Referenced by SCIPincludeHeurVbounds().

## ◆ HEUR_USESSUBSCIP

 #define HEUR_USESSUBSCIP   TRUE

does the heuristic use a secondary SCIP instance?

Definition at line 54 of file heur_vbounds.c.

Referenced by SCIPincludeHeurVbounds().

## ◆ DEFAULT_MAXNODES

 #define DEFAULT_MAXNODES   5000LL /* maximum number of nodes to regard in the subproblem */

Definition at line 56 of file heur_vbounds.c.

Referenced by SCIPincludeHeurVbounds().

## ◆ DEFAULT_MINFIXINGRATE

 #define DEFAULT_MINFIXINGRATE   0.25 /* minimum percentage of integer variables that have to be fixed */

Definition at line 57 of file heur_vbounds.c.

Referenced by SCIPincludeHeurVbounds().

## ◆ DEFAULT_MINIMPROVE

 #define DEFAULT_MINIMPROVE   0.01 /* factor by which vbounds heuristic should at least improve the incumbent */

Definition at line 58 of file heur_vbounds.c.

Referenced by SCIPincludeHeurVbounds().

## ◆ DEFAULT_MINNODES

 #define DEFAULT_MINNODES   500LL /* minimum number of nodes to regard in the subproblem */

Definition at line 59 of file heur_vbounds.c.

Referenced by SCIPincludeHeurVbounds().

## ◆ DEFAULT_NODESOFS

 #define DEFAULT_NODESOFS   500LL /* number of nodes added to the contingent of the total nodes */

Definition at line 60 of file heur_vbounds.c.

Referenced by SCIPincludeHeurVbounds().

## ◆ DEFAULT_NODESQUOT

 #define DEFAULT_NODESQUOT   0.1 /* subproblem nodes in relation to nodes of the original problem */

Definition at line 61 of file heur_vbounds.c.

Referenced by SCIPincludeHeurVbounds().

## ◆ DEFAULT_MAXPROPROUNDS

 #define DEFAULT_MAXPROPROUNDS   2 /* maximum number of propagation rounds during probing */

Definition at line 62 of file heur_vbounds.c.

Referenced by SCIPincludeHeurVbounds().

## ◆ DEFAULT_COPYCUTS

 #define DEFAULT_COPYCUTS   TRUE

should all active cuts from the cutpool of the original scip be copied to constraints of the subscip

Definition at line 63 of file heur_vbounds.c.

Referenced by SCIPincludeHeurVbounds().

## ◆ getLbIndex

 #define getLbIndex ( idx ) (2*(idx))

Definition at line 106 of file heur_vbounds.c.

Referenced by dfs().

## ◆ getUbIndex

 #define getUbIndex ( idx ) (2*(idx)+1)

Definition at line 107 of file heur_vbounds.c.

Referenced by dfs().

## ◆ getVarIndex

 #define getVarIndex ( idx ) ((idx)/2)

Definition at line 108 of file heur_vbounds.c.

Referenced by dfs(), and initializeCandsLists().

## ◆ getBoundtype

 #define getBoundtype ( idx ) (((idx) % 2 == 0) ? SCIP_BOUNDTYPE_LOWER : SCIP_BOUNDTYPE_UPPER)

Definition at line 109 of file heur_vbounds.c.

Referenced by initializeCandsLists().

## ◆ isIndexLowerbound

 #define isIndexLowerbound ( idx ) ((idx) % 2 == 0)

Definition at line 110 of file heur_vbounds.c.

Referenced by dfs().

## ◆ heurdataReset()

 static void heurdataReset ( SCIP_HEURDATA * heurdata )
static

reset heuristic data structure

Parameters
 heurdata structure containing heurdata

Definition at line 123 of file heur_vbounds.c.

References dfs(), FALSE, and NULL.

Referenced by SCIPincludeHeurVbounds().

## ◆ dfs()

 static SCIP_RETCODE dfs ( SCIP * scip, int startnode, SCIP_Bool * visited, int * dfsstack, int * stacknextedge, int * dfsnodes, int * ndfsnodes )
static

performs depth-first-search in the implicitly given directed graph from the given start index

Parameters
 scip SCIP data structure startnode node to start the depth-first-search visited array to store for each node, whether it was already visited dfsstack array of size number of nodes to store the stack; only needed for performance reasons stacknextedge array of size number of nodes to store the number of adjacent nodes already visited for each node on the stack; only needed for performance reasons dfsnodes array of nodes that can be reached starting at startnode, in reverse dfs order ndfsnodes pointer to store number of nodes that can be reached starting at startnode

Definition at line 137 of file heur_vbounds.c.

Referenced by heurdataReset(), and topologicalSort().

## ◆ topologicalSort()

 static SCIP_RETCODE topologicalSort ( SCIP * scip, int * vbvars, int * nvbvars )
static

sort the bounds of variables topologically

Parameters
 scip SCIP data structure vbvars array to store variable bounds in topological order nvbvars array to store number of variable bounds in the graph

Definition at line 255 of file heur_vbounds.c.

Referenced by dfs(), and initializeCandsLists().

## ◆ initializeCandsLists()

 static SCIP_RETCODE initializeCandsLists ( SCIP * scip, SCIP_HEURDATA * heurdata )
static

initialize candidate lists

Parameters
 scip original SCIP data structure heurdata structure containing heurdata

Definition at line 298 of file heur_vbounds.c.

Referenced by topologicalSort().

## ◆ applyVboundsFixings()

 static SCIP_RETCODE applyVboundsFixings ( SCIP * scip, SCIP_HEURDATA * heurdata, SCIP_VAR ** vars, int nvbvars, SCIP_Bool tighten, SCIP_Bool obj, SCIP_Bool * infeasible, SCIP_VAR ** lastvar, SCIP_Bool * fixedtolb )
static

apply variable bound fixing during probing

Parameters
 scip original SCIP data structure heurdata structure containing heurdata vars variables to fix during probing nvbvars number of variables in the variable bound graph tighten should variables be fixed to cause other fixings? obj should the objective be taken into account? infeasible pointer to store whether problem is infeasible lastvar last fixed variable fixedtolb was last fixed variable fixed to its lower bound?

Definition at line 355 of file heur_vbounds.c.

Referenced by applyVbounds(), and initializeCandsLists().

## ◆ createNewSol()

 static SCIP_RETCODE createNewSol ( SCIP * scip, SCIP * subscip, SCIP_VAR ** subvars, SCIP_SOL * newsol, SCIP_SOL * subsol, SCIP_Bool * success )
static

creates a new solution for the original problem by copying the solution of the subproblem

Parameters
 scip original SCIP data structure subscip SCIP structure of the subproblem subvars the variables of the subproblem newsol working solution subsol solution of the subproblem success used to store whether new solution was found or not

Definition at line 462 of file heur_vbounds.c.

Referenced by applyVbounds(), and applyVboundsFixings().

## ◆ applyVbounds()

 static SCIP_RETCODE applyVbounds ( SCIP * scip, SCIP_HEUR * heur, SCIP_HEURDATA * heurdata, SCIP_VAR ** vbvars, int nvbvars, SCIP_Bool tighten, SCIP_Bool obj, SCIP_RESULT * result )
static

main procedure of the vbounds heuristic

Parameters
 scip original SCIP data structure heur heuristic heurdata heuristic data structure vbvars variables to fix during probing nvbvars number of variables to fix tighten should variables be fixed to cause other fixings? obj should the objective be taken into account? result pointer to store the result

Definition at line 505 of file heur_vbounds.c.

Referenced by createNewSol().

## ◆ SCIP_DECL_HEURCOPY()

 static SCIP_DECL_HEURCOPY ( heurCopyVbounds )
static

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

Definition at line 937 of file heur_vbounds.c.

Referenced by applyVbounds().

## ◆ SCIP_DECL_HEURFREE()

 static SCIP_DECL_HEURFREE ( heurFreeVbounds )
static

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

Definition at line 951 of file heur_vbounds.c.

## ◆ SCIP_DECL_HEUREXITSOL()

 static SCIP_DECL_HEUREXITSOL ( heurExitsolVbounds )
static

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

Definition at line 967 of file heur_vbounds.c.

## ◆ SCIP_DECL_HEUREXEC()

 static SCIP_DECL_HEUREXEC ( heurExecVbounds )
static

execution method of primal heuristic

Definition at line 993 of file heur_vbounds.c.