Scippy

GCG

Branch-and-Price & Column Generation for Everyone

heur_setcover.c File Reference

Detailed Description

set covering primal heuristic according to Caprara, Fischetti, and Toth (1999)

Author
Tobias Oelschlaegel
Christian Puchert

Definition in file heur_setcover.c.

#include <assert.h>
#include <string.h>
#include "gcg.h"
#include "pricer_gcg.h"
#include "scip/clock.h"
#include "scip/cons_linear.h"
#include "heur_setcover.h"

Go to the source code of this file.

Data Structures

struct  PQUEUE
 
struct  SCP_INSTANCE
 
struct  SCP_CORE
 
struct  SCP_Lagrange_Sol
 
struct  SCIP_HeurData
 

Macros

#define HEUR_NAME   "setcover"
 
#define HEUR_DESC   "set covering primal heuristic according to Caprara, Fischetti, and Toth (1999)"
 
#define HEUR_DISPCHAR   'S'
 
#define HEUR_PRIORITY   0
 
#define HEUR_FREQ   0
 
#define HEUR_FREQOFS   0
 
#define HEUR_MAXDEPTH   -1
 
#define HEUR_TIMING   SCIP_HEURTIMING_AFTERNODE
 
#define HEUR_USESSUBSCIP   FALSE
 
#define DEF_CORE_TENT_SIZE   10
 
#define DEF_LAMBDA_ADJUSTMENTS   TRUE
 
#define DEF_LAMBDA_P   50
 
#define DEF_LAMBDA   0.1
 
#define DEF_STOP_CRIT_ITER   300
 
#define DEF_STOP_CRIT_DIFF   1.0
 
#define DEF_STOP_CRIT_RATIO   0.99
 
#define DEF_PI_MIN   0.3
 
#define DEF_PI_ALPHA   1.1
 
#define DEF_BETA   1.025
 
#define DEF_MAX_ITER   2
 
#define DEF_MAX_ITER_NO_IMP   1
 
#define DEF_THREEPHASE_MAX_ITER   10
 
#define DEF_GREEDY_MAX_ITER   100
 
#define DEF_MIN_PROB_SIZE   1000
 
#define DEFAULT_RANDSEED   19
 

Functions

static SCIP_RETCODE pqueue_init (SCIP *scip, PQUEUE *queue)
 
static void pqueue_clear (SCIP *scip, PQUEUE *queue)
 
static void pqueue_destroy (SCIP *scip, PQUEUE *queue)
 
static SCIP_RETCODE pqueue_insert (SCIP *scip, PQUEUE *queue, SCIP_Real key, int elem, int *position)
 
static void pqueue_decrease_key (SCIP *scip, PQUEUE *queue, int pos, SCIP_Real key)
 
static void pqueue_increase_key (SCIP *scip, PQUEUE *queue, int pos, SCIP_Real key)
 
static void pqueue_get_min (SCIP *scip, PQUEUE *queue, int *elem)
 
static SCIP_RETCODE allocateMemoryForSolution (SCIP *scip, SCP_CORE *core, SCP_Lagrange_Sol *mult)
 
static SCIP_Bool isCoreVariable (SCP_CORE *core, SCIP_VAR *var)
 
static SCIP_Bool isFixedVariable (SCP_INSTANCE *inst, SCIP_VAR *var)
 
static SCIP_Bool isVarInSolution (SCIP_Bool *solution, SCIP_VAR *var)
 
static void addVarToCore (SCP_CORE *core, SCIP_VAR *var)
 
static void fixVariable (SCP_INSTANCE *inst, SCIP_VAR *var)
 
static void addVarToSolution (SCIP_Bool *solution, SCIP_VAR *var)
 
static void removeVarsFromCore (SCIP *scip, SCP_CORE *core)
 
static void removeVarFromSolution (SCIP_Bool *solution, SCIP_VAR *var)
 
static void clearSolution (SCIP *scip, SCIP_Bool *solution)
 
static SCIP_Bool isRowCovered (SCP_INSTANCE *inst, int rowpos)
 
static void markRowAsCovered (SCP_INSTANCE *inst, int rowpos)
 
static SCIP_RETCODE getVarIndex (SCIP *scip, SCP_CORE *core, SCIP_VAR *variable, int *pos)
 
static SCIP_RETCODE getConsVars (SCIP *scip, SCP_CORE *core, int pos, SCIP_VAR **vars, int *nvars, SCIP_Bool *success)
 
static void freeMemoryForSolution (SCIP *scip, SCP_Lagrange_Sol *mult)
 
static void copySetCoverSolution (SCIP *scip, SCP_CORE *core, SCP_INSTANCE *inst, SCIP_Bool *dest, SCIP_Real *destcosts, SCIP_Bool *source)
 
static void copySolution (SCIP *scip, SCP_CORE *core, SCP_Lagrange_Sol *dest, SCP_Lagrange_Sol *source)
 
static SCIP_RETCODE initInstance (SCIP *scip, SCP_INSTANCE *inst)
 
static void copyInstance (SCIP *scip, SCP_CORE *core, SCP_INSTANCE *dest, SCP_INSTANCE *source)
 
static void freeInstance (SCIP *scip, SCP_INSTANCE *inst)
 
static SCIP_RETCODE initTentativeCore (SCIP *scip, SCP_CORE *core, SCIP_HEURDATA *heurdata)
 
static void extendSolution (SCIP *scip, SCP_CORE *core, SCP_INSTANCE *inst, SCIP_Bool *solution)
 
static SCIP_RETCODE computeCoreRows (SCIP *scip, SCP_CORE *core, SCIP_HEURDATA *heurdata)
 
static SCIP_RETCODE computeCoreColumns (SCIP *scip, SCP_CORE *core)
 
static void freeCore (SCIP *scip, SCP_CORE *core)
 
static SCIP_RETCODE redefineCore (SCIP *scip, SCIP_HEURDATA *heurdata)
 
static SCIP_RETCODE markRowsCoveredByFixedVariables (SCIP *scip, SCP_CORE *core, SCP_INSTANCE *inst, SCIP_HEURDATA *heurdata)
 
static SCIP_RETCODE checkSetCover (SCIP *scip, SCP_CORE *core, SCP_INSTANCE *inst, SCIP_Bool *solution, SCIP_Bool *issetcover, SCIP_HEURDATA *heurdata)
 
static SCIP_RETCODE computeDelta (SCIP *scip, SCP_CORE *core, SCP_INSTANCE *inst, SCIP_Real *lagrangiancosts, SCIP_Bool *solution, SCIP_Real pi, SCIP_HEURDATA *heurdata)
 
static SCIP_RETCODE removeRedundantColumns (SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_Bool *solution, SCIP_Real *solcosts)
 
static SCIP_RETCODE greedySetCover (SCIP *scip, SCP_CORE *core, SCP_INSTANCE *inst, SCP_Lagrange_Sol *mult, SCIP_HEURDATA *heurdata)
 
static SCIP_RETCODE computeLocalLagrangianCosts (SCIP *scip, SCP_CORE *core, SCP_INSTANCE *inst, SCP_Lagrange_Sol *mult, SCIP_HEURDATA *heurdata)
 
static SCIP_RETCODE computeGlobalLagrangianCosts (SCIP *scip, SCP_CORE *core, SCP_Lagrange_Sol *mult, SCIP_HEURDATA *heurdata)
 
static SCIP_RETCODE computeOptimalSolution (SCIP *scip, SCP_CORE *core, SCP_INSTANCE *inst, SCP_Lagrange_Sol *mult, SCIP_HEURDATA *heurdata)
 
static SCIP_RETCODE subgradientOptimization (SCIP *scip, SCP_CORE *core, SCP_INSTANCE *inst, SCP_Lagrange_Sol *best_mult_lb, SCIP_Real bestub, SCIP_HEURDATA *heurdata)
 
static SCIP_RETCODE computeInitialLagrangeMultiplier (SCIP *scip, SCP_CORE *core, SCP_INSTANCE *inst, SCP_Lagrange_Sol *mult, SCIP_HEURDATA *heurdata)
 
static SCIP_RETCODE exploreNeighborhood (SCIP *scip, SCP_Lagrange_Sol *startmult, SCIP_HEURDATA *heurdata)
 
static SCIP_RETCODE reportSolution (SCIP *scip, SCP_INSTANCE *inst, SCIP_Bool *solution, SCIP_HEUR *heur)
 
static SCIP_RETCODE threePhase (SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
 
static SCIP_RETCODE setCoveringHeuristic (SCIP *scip, SCIP_HEUR *heur)
 
static SCIP_DECL_HEURFREE (heurFreeSetcover)
 
static SCIP_DECL_HEURINIT (heurInitSetcover)
 
static SCIP_DECL_HEUREXIT (heurExitSetcover)
 
static SCIP_DECL_HEUREXEC (heurExecSetcover)
 
SCIP_RETCODE SCIPincludeHeurSetcover (SCIP *scip)
 

Macro Definition Documentation

◆ HEUR_NAME

#define HEUR_NAME   "setcover"

Definition at line 45 of file heur_setcover.c.

◆ HEUR_DESC

#define HEUR_DESC   "set covering primal heuristic according to Caprara, Fischetti, and Toth (1999)"

Definition at line 46 of file heur_setcover.c.

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR   'S'

Definition at line 47 of file heur_setcover.c.

◆ HEUR_PRIORITY

#define HEUR_PRIORITY   0

Definition at line 48 of file heur_setcover.c.

◆ HEUR_FREQ

#define HEUR_FREQ   0

Definition at line 49 of file heur_setcover.c.

◆ HEUR_FREQOFS

#define HEUR_FREQOFS   0

Definition at line 50 of file heur_setcover.c.

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH   -1

Definition at line 51 of file heur_setcover.c.

◆ HEUR_TIMING

#define HEUR_TIMING   SCIP_HEURTIMING_AFTERNODE

Definition at line 52 of file heur_setcover.c.

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP   FALSE

does the heuristic use a secondary SCIP instance?

Definition at line 53 of file heur_setcover.c.

◆ DEF_CORE_TENT_SIZE

#define DEF_CORE_TENT_SIZE   10

number of columns covering each row that are added to the tentative core at the beginning

Definition at line 55 of file heur_setcover.c.

◆ DEF_LAMBDA_ADJUSTMENTS

#define DEF_LAMBDA_ADJUSTMENTS   TRUE

adjust step size during the subgradient phase

Definition at line 56 of file heur_setcover.c.

◆ DEF_LAMBDA_P

#define DEF_LAMBDA_P   50

number of iterations after which lambda is adjusted

Definition at line 57 of file heur_setcover.c.

◆ DEF_LAMBDA

#define DEF_LAMBDA   0.1

initial step size for the subgradient phase

Definition at line 58 of file heur_setcover.c.

◆ DEF_STOP_CRIT_ITER

#define DEF_STOP_CRIT_ITER   300

number of iterations of the subgradient phase after which the stopping criterion is tested again

Definition at line 59 of file heur_setcover.c.

◆ DEF_STOP_CRIT_DIFF

#define DEF_STOP_CRIT_DIFF   1.0

stop if absolute difference between best lower and upper bound is less than SCP_STOP_CRIT_DIFF, and

Definition at line 60 of file heur_setcover.c.

◆ DEF_STOP_CRIT_RATIO

#define DEF_STOP_CRIT_RATIO   0.99

the relative ratio between best lower and upper bound is less than DEF_STOP_CRIT_RATIO

Definition at line 61 of file heur_setcover.c.

◆ DEF_PI_MIN

#define DEF_PI_MIN   0.3

percentage of rows to be removed after fixing columns

Definition at line 62 of file heur_setcover.c.

◆ DEF_PI_ALPHA

#define DEF_PI_ALPHA   1.1

increase of pi when no improvement was made, i.e. more columns will be fixed

Definition at line 63 of file heur_setcover.c.

◆ DEF_BETA

#define DEF_BETA   1.025

allowed gap between lowerbound and upper bound during the subgradient phase

Definition at line 64 of file heur_setcover.c.

◆ DEF_MAX_ITER

#define DEF_MAX_ITER   2

maximum number of iterations of three-phase

Definition at line 65 of file heur_setcover.c.

◆ DEF_MAX_ITER_NO_IMP

#define DEF_MAX_ITER_NO_IMP   1

stop of no improvements during the last X iterations of three-phase

Definition at line 66 of file heur_setcover.c.

◆ DEF_THREEPHASE_MAX_ITER

#define DEF_THREEPHASE_MAX_ITER   10

maximum number of iterations inside three-phase

Definition at line 67 of file heur_setcover.c.

◆ DEF_GREEDY_MAX_ITER

#define DEF_GREEDY_MAX_ITER   100

number of multipliers that are used for computing greedy solutions during each iteration

Definition at line 68 of file heur_setcover.c.

◆ DEF_MIN_PROB_SIZE

#define DEF_MIN_PROB_SIZE   1000

minimum number of variables the problem has to contain for the heuristic to start

Definition at line 69 of file heur_setcover.c.

◆ DEFAULT_RANDSEED

#define DEFAULT_RANDSEED   19

initial random seed

Definition at line 70 of file heur_setcover.c.

Function Documentation

◆ pqueue_init()

static SCIP_RETCODE pqueue_init ( SCIP *  scip,
PQUEUE queue 
)
static

initializes a priority queue

Parameters
scipmaster SCIP data structure
queuepriority queue instance

Definition at line 196 of file heur_setcover.c.

References PQUEUE::data, PQUEUE::keys, PQUEUE::positions, PQUEUE::reserved, and PQUEUE::size.

Referenced by setCoveringHeuristic().

◆ pqueue_clear()

static void pqueue_clear ( SCIP *  scip,
PQUEUE queue 
)
static

removes all elements from a priority queue, but does not release any memory

Parameters
scipmaster SCIP data structure
queuepriority queue instance

Definition at line 213 of file heur_setcover.c.

References PQUEUE::size.

Referenced by greedySetCover().

◆ pqueue_destroy()

static void pqueue_destroy ( SCIP *  scip,
PQUEUE queue 
)
static

releases all memory that is used by the priority queue

Parameters
scipmaster SCIP data structure
queuepriority queue instance

Definition at line 223 of file heur_setcover.c.

References PQUEUE::data, PQUEUE::keys, and PQUEUE::positions.

Referenced by setCoveringHeuristic().

◆ pqueue_insert()

static SCIP_RETCODE pqueue_insert ( SCIP *  scip,
PQUEUE queue,
SCIP_Real  key,
int  elem,
int *  position 
)
static

inserts an element with key 'key' and value 'elem' into the queue. If 'position' is not NULL, the referenced memory location will always contain the internal position of the element

Parameters
scipmaster SCIP data structure
queuepriority queue instance
keykey of the new item
elemvalue of the new item
positionaddress where the items position within the queue is stored

Definition at line 237 of file heur_setcover.c.

References PQUEUE::data, PQUEUE::keys, PQUEUE::positions, PQUEUE::reserved, and PQUEUE::size.

Referenced by greedySetCover().

◆ pqueue_decrease_key()

static void pqueue_decrease_key ( SCIP *  scip,
PQUEUE queue,
int  pos,
SCIP_Real  key 
)
static

decreases the key to 'key' of the element that is currently at position 'pos'

Parameters
scipmaster SCIP data structure
queuepriority queue instance
posposition of the item within the queue that is to be changed
keynew key of the item, needs to be greater than the old key

Definition at line 290 of file heur_setcover.c.

References PQUEUE::data, PQUEUE::keys, PQUEUE::positions, and PQUEUE::size.

Referenced by greedySetCover().

◆ pqueue_increase_key()

static void pqueue_increase_key ( SCIP *  scip,
PQUEUE queue,
int  pos,
SCIP_Real  key 
)
static

increases the key to 'key' of the element that is currently at position 'pos'

Parameters
scipmaster SCIP data structure
queuepriority queue instance
posposition of the item within the queue that is to be changed
keynew key of the item, needs to be smaller than the old one

Definition at line 333 of file heur_setcover.c.

References PQUEUE::data, PQUEUE::keys, PQUEUE::positions, and PQUEUE::size.

Referenced by greedySetCover(), and pqueue_get_min().

◆ pqueue_get_min()

static void pqueue_get_min ( SCIP *  scip,
PQUEUE queue,
int *  elem 
)
static

returns the value of a minimum element in 'elem'. Sets 'elem' to -1 if the queue is empty

Parameters
scipmaster SCIP data structure
queuepriority queue instance
elemaddress where the value of a minimum key item will be stored

Definition at line 439 of file heur_setcover.c.

References PQUEUE::data, PQUEUE::keys, PQUEUE::positions, pqueue_increase_key(), and PQUEUE::size.

Referenced by greedySetCover().

◆ allocateMemoryForSolution()

static SCIP_RETCODE allocateMemoryForSolution ( SCIP *  scip,
SCP_CORE core,
SCP_Lagrange_Sol mult 
)
static

allocates memory for a lagrange multiplier and a set covering solution

Parameters
scipmaster SCIP data structure
corecore data structure
multuninitialized solution data structure

Definition at line 470 of file heur_setcover.c.

References SCP_Lagrange_Sol::lagrangiancostsglobal, SCP_Lagrange_Sol::lagrangiancostslocal, SCP_Lagrange_Sol::lblagrangeglobal, SCP_Lagrange_Sol::lblagrangelocal, SCP_CORE::nconss, SCP_CORE::nvariables, SCP_Lagrange_Sol::subgradient, SCP_Lagrange_Sol::u, SCP_Lagrange_Sol::ubgreedylocal, and SCP_Lagrange_Sol::xgreedylocal.

Referenced by exploreNeighborhood(), setCoveringHeuristic(), and subgradientOptimization().

◆ isCoreVariable()

static SCIP_Bool isCoreVariable ( SCP_CORE core,
SCIP_VAR *  var 
)
static

checks if 'var' is a core variable

Parameters
coreinitialized core data structure
varSCIP variable

Definition at line 505 of file heur_setcover.c.

References SCP_CORE::varincore.

Referenced by computeCoreColumns(), computeCoreRows(), computeInitialLagrangeMultiplier(), computeOptimalSolution(), exploreNeighborhood(), greedySetCover(), initTentativeCore(), and redefineCore().

◆ isFixedVariable()

static SCIP_Bool isFixedVariable ( SCP_INSTANCE inst,
SCIP_VAR *  var 
)
static

checks if 'var' is fixed within instance 'inst'

Parameters
instinstance of the set covering problem
varSCIP variable

Definition at line 523 of file heur_setcover.c.

References SCP_INSTANCE::varsfixed.

Referenced by computeInitialLagrangeMultiplier(), computeOptimalSolution(), copyInstance(), copySetCoverSolution(), extendSolution(), greedySetCover(), markRowsCoveredByFixedVariables(), and reportSolution().

◆ isVarInSolution()

static SCIP_Bool isVarInSolution ( SCIP_Bool *  solution,
SCIP_VAR *  var 
)
static

checks if 'variable' is part of 'solution'

Parameters
solutionSCIP hashtable that contains SCIP variables
varSCIP variable

Definition at line 541 of file heur_setcover.c.

Referenced by checkSetCover(), computeDelta(), copySetCoverSolution(), copySolution(), extendSolution(), removeRedundantColumns(), and reportSolution().

◆ addVarToCore()

static void addVarToCore ( SCP_CORE core,
SCIP_VAR *  var 
)
static

adds a variable to the core

Parameters
coreinitialized core data structure
varSCIP variable

Definition at line 559 of file heur_setcover.c.

References SCP_CORE::ncorevariables, and SCP_CORE::varincore.

Referenced by initTentativeCore(), and redefineCore().

◆ fixVariable()

static void fixVariable ( SCP_INSTANCE inst,
SCIP_VAR *  var 
)
static

fixes 'var' within instance 'inst'

Parameters
instSCP instance where 'variable' is to be fixed
varSCIP variable

Definition at line 579 of file heur_setcover.c.

References SCP_INSTANCE::nvarsfixed, and SCP_INSTANCE::varsfixed.

Referenced by computeDelta(), copyInstance(), and threePhase().

◆ addVarToSolution()

static void addVarToSolution ( SCIP_Bool *  solution,
SCIP_VAR *  var 
)
static

adds variable 'var' to 'solution'

Parameters
solutionsolution represented as a boolean array
varSCIP variable

Definition at line 599 of file heur_setcover.c.

Referenced by copySetCoverSolution(), copySolution(), extendSolution(), and greedySetCover().

◆ removeVarsFromCore()

static void removeVarsFromCore ( SCIP *  scip,
SCP_CORE core 
)
static

removes all variables from the core

Parameters
scipSCIP data structure
coreinitialized core data structure

Definition at line 618 of file heur_setcover.c.

References SCP_CORE::ncorevariables, and SCP_CORE::varincore.

Referenced by redefineCore().

◆ removeVarFromSolution()

static void removeVarFromSolution ( SCIP_Bool *  solution,
SCIP_VAR *  var 
)
static

removes a 'var' from 'solution'

Parameters
solutionsolution represented as a boolean array
varSCIP variable

Definition at line 634 of file heur_setcover.c.

Referenced by removeRedundantColumns().

◆ clearSolution()

static void clearSolution ( SCIP *  scip,
SCIP_Bool *  solution 
)
static

clears a solution

Parameters
scipSCIP data structure
solutionsolution represented as a boolean array

Definition at line 653 of file heur_setcover.c.

Referenced by copySetCoverSolution(), copySolution(), and greedySetCover().

◆ isRowCovered()

static SCIP_Bool isRowCovered ( SCP_INSTANCE inst,
int  rowpos 
)
static

checks if the row at position 'rowpos' is covered by fixed variables of 'inst'

Parameters
instSCP instance
rowposposition of the row within 'core'

Definition at line 669 of file heur_setcover.c.

References SCP_INSTANCE::rowscovered.

Referenced by computeDelta(), computeInitialLagrangeMultiplier(), computeLocalLagrangianCosts(), computeOptimalSolution(), exploreNeighborhood(), greedySetCover(), markRowsCoveredByFixedVariables(), and subgradientOptimization().

◆ markRowAsCovered()

static void markRowAsCovered ( SCP_INSTANCE inst,
int  rowpos 
)
static

marks the row at position 'rowpos' as covered within instance 'inst'

Parameters
instSCP instance
rowposposition of the row within 'core'

Definition at line 681 of file heur_setcover.c.

References SCP_INSTANCE::nrowscovered, and SCP_INSTANCE::rowscovered.

Referenced by greedySetCover(), and markRowsCoveredByFixedVariables().

◆ getVarIndex()

static SCIP_RETCODE getVarIndex ( SCIP *  scip,
SCP_CORE core,
SCIP_VAR *  variable,
int *  pos 
)
static

returns the position of 'variable' within the array core->variables

Parameters
scipmaster SCIP data structure
coreSCP core data structure
variableSCIP variable
posaddress where the position is to be stored

Definition at line 695 of file heur_setcover.c.

References SCP_CORE::mapvariables.

Referenced by checkSetCover(), computeCoreColumns(), computeCoreRows(), computeDelta(), computeGlobalLagrangianCosts(), computeInitialLagrangeMultiplier(), computeLocalLagrangianCosts(), computeOptimalSolution(), exploreNeighborhood(), greedySetCover(), initTentativeCore(), redefineCore(), and removeRedundantColumns().

◆ getConsVars()

static SCIP_RETCODE getConsVars ( SCIP *  scip,
SCP_CORE core,
int  pos,
SCIP_VAR **  vars,
int *  nvars,
SCIP_Bool *  success 
)
static

get all variables that are part of the constraint at position 'pos' (within SCIP) and saves them into 'vars'

Parameters
scipmaster SCIP data structure
coreSCP core data structure
posposition of the constraint within SCIP
varsallocated memory that can hold all variables
nvarsaddress where the number of variables will be stored
successaddress where the result of the operation will be stored

Definition at line 717 of file heur_setcover.c.

References SCP_CORE::conss, and SCP_CORE::maxconstraintvariables.

Referenced by checkSetCover(), computeCoreColumns(), computeCoreRows(), computeDelta(), computeGlobalLagrangianCosts(), computeInitialLagrangeMultiplier(), computeLocalLagrangianCosts(), computeOptimalSolution(), exploreNeighborhood(), greedySetCover(), markRowsCoveredByFixedVariables(), redefineCore(), and removeRedundantColumns().

◆ freeMemoryForSolution()

static void freeMemoryForSolution ( SCIP *  scip,
SCP_Lagrange_Sol mult 
)
static

releases all memory of a lagrange multiplier

Parameters
scipmaster SCIP data structure
multinitialized SCP lagrange multiplier that is to be freed

Definition at line 743 of file heur_setcover.c.

References SCP_Lagrange_Sol::lagrangiancostsglobal, SCP_Lagrange_Sol::lagrangiancostslocal, SCP_Lagrange_Sol::subgradient, SCP_Lagrange_Sol::u, and SCP_Lagrange_Sol::xgreedylocal.

Referenced by exploreNeighborhood(), setCoveringHeuristic(), and subgradientOptimization().

◆ copySetCoverSolution()

static void copySetCoverSolution ( SCIP *  scip,
SCP_CORE core,
SCP_INSTANCE inst,
SCIP_Bool *  dest,
SCIP_Real *  destcosts,
SCIP_Bool *  source 
)
static

creates a set covering solution. Adds all fixed variables of 'inst' and all variables of 'source' to 'dest'. 'destcosts' contains the total costs of the solution.

Parameters
scipmaster SCIP data structure
coreSCP core data structure
instSCP instance
destarray where variables belonging to the solution are inserted
destcostsaddress where the total costs of the solution will be stored
sourceSCP solution to the (reduced) instance 'inst'

Definition at line 759 of file heur_setcover.c.

References addVarToSolution(), clearSolution(), isFixedVariable(), isVarInSolution(), SCP_CORE::nvariables, and SCP_CORE::variables.

Referenced by exploreNeighborhood(), and threePhase().

◆ copySolution()

static void copySolution ( SCIP *  scip,
SCP_CORE core,
SCP_Lagrange_Sol dest,
SCP_Lagrange_Sol source 
)
static

copies all data of the lagrange multiplier 'source' to the lagrange multiplier 'dest'

Parameters
scipmaster SCIP data structure
coreSCP core data structure
destSCP lagrange multiplier where data will be copied to
sourceSCP lagrange multiplier where data will be copied from

Definition at line 792 of file heur_setcover.c.

References addVarToSolution(), clearSolution(), isVarInSolution(), SCP_Lagrange_Sol::lagrangiancostsglobal, SCP_Lagrange_Sol::lagrangiancostslocal, SCP_Lagrange_Sol::lblagrangeglobal, SCP_Lagrange_Sol::lblagrangelocal, SCP_CORE::nconss, SCP_CORE::nvariables, SCP_Lagrange_Sol::subgradient, SCP_Lagrange_Sol::u, SCP_Lagrange_Sol::ubgreedylocal, SCP_CORE::variables, and SCP_Lagrange_Sol::xgreedylocal.

Referenced by exploreNeighborhood(), subgradientOptimization(), and threePhase().

◆ initInstance()

static SCIP_RETCODE initInstance ( SCIP *  scip,
SCP_INSTANCE inst 
)
static

initializes an instance where no variables are fixed and no rows are covered

Parameters
scipmaster SCIP data structure
instunitialized SCP instance

Definition at line 821 of file heur_setcover.c.

References SCP_INSTANCE::costsfixed, SCP_INSTANCE::nrowscovered, SCP_INSTANCE::nvarsfixed, SCP_INSTANCE::rowscovered, and SCP_INSTANCE::varsfixed.

Referenced by setCoveringHeuristic().

◆ copyInstance()

static void copyInstance ( SCIP *  scip,
SCP_CORE core,
SCP_INSTANCE dest,
SCP_INSTANCE source 
)
static

copies the fixed variables from 'source' to 'dest', but not the set of covered rows. this must be done separately.

Parameters
scipmaster SCIP data structure
coreSCP core data structure
destinitialized SCP instance
sourceinitialized SCP instance that is to be copied

Definition at line 837 of file heur_setcover.c.

References SCP_INSTANCE::costsfixed, fixVariable(), isFixedVariable(), SCP_INSTANCE::nrowscovered, SCP_INSTANCE::nvarsfixed, SCP_INSTANCE::rowscovered, SCP_CORE::variables, and SCP_INSTANCE::varsfixed.

Referenced by threePhase().

◆ freeInstance()

static void freeInstance ( SCIP *  scip,
SCP_INSTANCE inst 
)
static

releases all memory used by an instance

Parameters
scipmaster SCIP data structure
instinitialized SCP instance that is to be freed

Definition at line 866 of file heur_setcover.c.

References SCP_INSTANCE::rowscovered, and SCP_INSTANCE::varsfixed.

Referenced by setCoveringHeuristic().

◆ initTentativeCore()

static SCIP_RETCODE initTentativeCore ( SCIP *  scip,
SCP_CORE core,
SCIP_HEURDATA *  heurdata 
)
static

◆ extendSolution()

static void extendSolution ( SCIP *  scip,
SCP_CORE core,
SCP_INSTANCE inst,
SCIP_Bool *  solution 
)
static

adds all fixed variables of 'inst' to a set covering solution 'solution'

Parameters
scipmaster SCIP data structure
coreSCP core data structure
inst(reduced) SCP instance
solutionSCP solution (a hashtable that contains SCIP variables)

Definition at line 994 of file heur_setcover.c.

References addVarToSolution(), isFixedVariable(), isVarInSolution(), SCP_CORE::nvariables, and SCP_CORE::variables.

Referenced by exploreNeighborhood().

◆ computeCoreRows()

static SCIP_RETCODE computeCoreRows ( SCIP *  scip,
SCP_CORE core,
SCIP_HEURDATA *  heurdata 
)
static

constructs rows of all constraints, but only includes core variables

Parameters
scipmaster SCIP data structure
coreSCP core data structure
heurdatapointer to the heuristics's data

Definition at line 1016 of file heur_setcover.c.

References getConsVars(), getVarIndex(), isCoreVariable(), SCP_CORE::maxconstraintvariables, SCP_CORE::nconss, SCP_CORE::nrowvars, SCP_CORE::rows, SCP_CORE::rowsavailable, and SCP_CORE::variables.

Referenced by redefineCore(), and setCoveringHeuristic().

◆ computeCoreColumns()

static SCIP_RETCODE computeCoreColumns ( SCIP *  scip,
SCP_CORE core 
)
static

constructs columns of core variables to provide faster access

Parameters
scipmaster SCIP data structure
coreSCP core data structure

Definition at line 1092 of file heur_setcover.c.

References SCP_CORE::columns, SCP_CORE::columnsavailable, getConsVars(), getVarIndex(), isCoreVariable(), SCP_CORE::maxconstraintvariables, SCP_CORE::nconss, SCP_CORE::nvarconss, SCP_CORE::nvariables, and SCP_CORE::variables.

Referenced by redefineCore(), and setCoveringHeuristic().

◆ freeCore()

static void freeCore ( SCIP *  scip,
SCP_CORE core 
)
static

releases memory that is used by the core, including rows and columns, if they were computed

Parameters
scipmaster SCIP data structure
coreSCP core data structure that is to be freed

Definition at line 1168 of file heur_setcover.c.

References SCP_CORE::columns, SCP_CORE::columnsavailable, SCP_CORE::constraintid, SCP_CORE::delta, SCP_CORE::delta_pos, SCP_CORE::listcorevariables, SCP_CORE::mapvariables, SCP_CORE::nconss, SCP_CORE::nrowvars, SCP_CORE::nvarconss, SCP_CORE::nvariables, SCP_CORE::rows, SCP_CORE::rowsavailable, SCP_CORE::solgreedy, and SCP_CORE::varincore.

Referenced by setCoveringHeuristic().

◆ redefineCore()

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

computes a new core based on the delta values of variables, see formula (9) in the paper

Parameters
scipmaster SCIP data structure
heurdatapointer to the heuristic's data; this contains the SCP core

Definition at line 1213 of file heur_setcover.c.

References addVarToCore(), SCP_CORE::columns, SCP_CORE::columnsavailable, computeCoreColumns(), computeCoreRows(), SCP_CORE::delta, SCP_CORE::delta_pos, getConsVars(), getVarIndex(), isCoreVariable(), SCP_CORE::listcorevariables, SCP_CORE::nactiveconss, SCP_CORE::nconss, SCP_CORE::ncorevariables, SCP_CORE::nrowvars, SCP_CORE::nvariables, removeVarsFromCore(), SCP_CORE::rows, SCP_CORE::rowsavailable, and SCP_CORE::variables.

Referenced by setCoveringHeuristic().

◆ markRowsCoveredByFixedVariables()

static SCIP_RETCODE markRowsCoveredByFixedVariables ( SCIP *  scip,
SCP_CORE core,
SCP_INSTANCE inst,
SCIP_HEURDATA *  heurdata 
)
static

for all rows that are covered by the variables in inst->varsfixed, this function adds their indices to inst->rowscovered

Parameters
scipmaster SCIP data structure
coreSCP core data structure
instinitialized SCP instance where some variables may be fixed
heurdatapointer to the heuristic's data

Definition at line 1380 of file heur_setcover.c.

References SCP_CORE::columns, SCP_CORE::columnsavailable, getConsVars(), isFixedVariable(), isRowCovered(), SCP_CORE::listcorevariables, markRowAsCovered(), SCP_CORE::nconss, SCP_CORE::ncorevariables, SCP_INSTANCE::nrowscovered, SCP_CORE::nvarconss, SCP_INSTANCE::rowscovered, and SCP_CORE::variables.

Referenced by setCoveringHeuristic(), and threePhase().

◆ checkSetCover()

static SCIP_RETCODE checkSetCover ( SCIP *  scip,
SCP_CORE core,
SCP_INSTANCE inst,
SCIP_Bool *  solution,
SCIP_Bool *  issetcover,
SCIP_HEURDATA *  heurdata 
)
static

checks whether the given 'solution' is actually a set cover

Parameters
scipmaster SCIP data structure
coreSCP core data structure
instSCP instance
solutionpossible SCP solution
issetcoveraddress where TRUE will be stored if 'solution' is a set cover
heurdatapointer to the heuristic's data

Definition at line 1448 of file heur_setcover.c.

References getConsVars(), getVarIndex(), isVarInSolution(), SCP_CORE::nconss, and SCP_CORE::variables.

Referenced by setCoveringHeuristic(), and threePhase().

◆ computeDelta()

static SCIP_RETCODE computeDelta ( SCIP *  scip,
SCP_CORE core,
SCP_INSTANCE inst,
SCIP_Real *  lagrangiancosts,
SCIP_Bool *  solution,
SCIP_Real  pi,
SCIP_HEURDATA *  heurdata 
)
static

computes delta values for variables and fixes new variables within inst, see formula (9) of the paper

Parameters
scipmaster SCIP data structure
coreSCP core data structure
instSCP instance
lagrangiancostsarray with lagrangian costs of the rows
solutionvalid solution to the global SCP instance
pipercentage of rows that need be covered by new fixed variables
heurdatapointer to the heuristic's data

Definition at line 1507 of file heur_setcover.c.

References SCP_CORE::columns, SCP_CORE::conss, SCP_INSTANCE::costsfixed, SCP_CORE::delta, SCP_CORE::delta_pos, fixVariable(), getConsVars(), getVarIndex(), isRowCovered(), isVarInSolution(), SCP_CORE::nactiveconss, SCP_CORE::nconss, SCP_CORE::nrowvars, SCP_CORE::nvarconss, SCP_CORE::nvariables, SCP_INSTANCE::nvarsfixed, SCP_CORE::rows, SCP_CORE::rowsavailable, SCP_CORE::variables, and SCP_INSTANCE::varsfixed.

Referenced by setCoveringHeuristic().

◆ removeRedundantColumns()

static SCIP_RETCODE removeRedundantColumns ( SCIP *  scip,
SCIP_HEURDATA *  heurdata,
SCIP_Bool *  solution,
SCIP_Real *  solcosts 
)
static
Parameters
scipmaster SCIP data structure
heurdatapointer to the heuristic's data
solutionsolution to the global SCP instance
solcostspointer to original costs of 'solution'; contains updated costs

Definition at line 1636 of file heur_setcover.c.

References SCP_CORE::columns, SCP_CORE::columnsavailable, SCP_CORE::conss, getConsVars(), getVarIndex(), isVarInSolution(), SCP_CORE::nconss, SCP_CORE::nrowvars, SCP_CORE::nvarconss, SCP_CORE::nvariables, removeVarFromSolution(), SCP_CORE::rows, SCP_CORE::rowsavailable, and SCP_CORE::variables.

Referenced by exploreNeighborhood(), and threePhase().

◆ greedySetCover()

static SCIP_RETCODE greedySetCover ( SCIP *  scip,
SCP_CORE core,
SCP_INSTANCE inst,
SCP_Lagrange_Sol mult,
SCIP_HEURDATA *  heurdata 
)
static

greedy set cover algorithm that uses lagrangian costs instead of original costs.

Parameters
scipmaster SCIP data structure
coreSCP core data structure
inst(reduced) SCP instance
multlagrange multiplier that is used to compute lagrangian costs
heurdatapointer to the heuristic's data

Definition at line 1770 of file heur_setcover.c.

References addVarToSolution(), clearSolution(), SCP_CORE::columns, SCP_CORE::columnsavailable, SCP_CORE::conss, getConsVars(), getVarIndex(), isCoreVariable(), isFixedVariable(), isRowCovered(), markRowAsCovered(), SCP_INSTANCE::nrowscovered, SCP_CORE::nsolgreedy, SCP_CORE::nvarconss, SCP_CORE::nvariables, pqueue_clear(), pqueue_decrease_key(), pqueue_get_min(), pqueue_increase_key(), pqueue_insert(), SCP_INSTANCE::rowscovered, SCP_CORE::solgreedy, SCP_Lagrange_Sol::u, SCP_Lagrange_Sol::ubgreedylocal, SCP_CORE::variables, and SCP_Lagrange_Sol::xgreedylocal.

Referenced by exploreNeighborhood(), and threePhase().

◆ computeLocalLagrangianCosts()

static SCIP_RETCODE computeLocalLagrangianCosts ( SCIP *  scip,
SCP_CORE core,
SCP_INSTANCE inst,
SCP_Lagrange_Sol mult,
SCIP_HEURDATA *  heurdata 
)
static

computes lagrangian costs for all columns, only considering rows that are uncovered by fixed variables in 'inst'

Parameters
scipmaster SCIP data structure
coreSCP core data structure
inst(reduced) SCP instance
multlagrange multiplier that is used to compute the lagrangian costs
heurdatapointer to the heuristic's data

Definition at line 1944 of file heur_setcover.c.

References SCP_CORE::conss, getConsVars(), getVarIndex(), isRowCovered(), SCP_Lagrange_Sol::lagrangiancostslocal, SCP_CORE::nconss, SCP_CORE::nrowvars, SCP_CORE::nvariables, SCP_CORE::rows, SCP_CORE::rowsavailable, SCP_Lagrange_Sol::u, and SCP_CORE::variables.

Referenced by computeOptimalSolution().

◆ computeGlobalLagrangianCosts()

static SCIP_RETCODE computeGlobalLagrangianCosts ( SCIP *  scip,
SCP_CORE core,
SCP_Lagrange_Sol mult,
SCIP_HEURDATA *  heurdata 
)
static

computes lagrangian costs for all columns of the unrestricted instance and a global lower bound.

Parameters
scipmaster SCIP data structure
coreSCP core data structure
multlagrange multiplier that is used to compute the lagrangian costs
heurdatapointer to the heuristic's data

Definition at line 2012 of file heur_setcover.c.

References getConsVars(), getVarIndex(), SCP_Lagrange_Sol::lagrangiancostsglobal, SCP_Lagrange_Sol::lblagrangeglobal, SCP_CORE::nconss, SCP_CORE::nvariables, SCP_Lagrange_Sol::u, and SCP_CORE::variables.

Referenced by computeOptimalSolution().

◆ computeOptimalSolution()

static SCIP_RETCODE computeOptimalSolution ( SCIP *  scip,
SCP_CORE core,
SCP_INSTANCE inst,
SCP_Lagrange_Sol mult,
SCIP_HEURDATA *  heurdata 
)
static

computes an optimal solution to the lagrangian relaxation, see formulae (4), (5) in the paper

Parameters
scipmaster SCIP data structure
coreSCP core data structure
inst(reduced) SCP instance
multlagrange multiplier
heurdatapointer to the heuristic's data

Definition at line 2063 of file heur_setcover.c.

References computeGlobalLagrangianCosts(), computeLocalLagrangianCosts(), SCP_CORE::conss, getConsVars(), getVarIndex(), isCoreVariable(), isFixedVariable(), isRowCovered(), SCP_Lagrange_Sol::lagrangiancostslocal, SCP_Lagrange_Sol::lblagrangeglobal, SCP_Lagrange_Sol::lblagrangelocal, SCP_CORE::listcorevariables, SCP_CORE::nconss, SCP_CORE::ncorevariables, SCP_CORE::nrowvars, SCP_CORE::rows, SCP_CORE::rowsavailable, SCP_Lagrange_Sol::subgradient, SCP_Lagrange_Sol::u, and SCP_CORE::variables.

Referenced by exploreNeighborhood(), subgradientOptimization(), and threePhase().

◆ subgradientOptimization()

static SCIP_RETCODE subgradientOptimization ( SCIP *  scip,
SCP_CORE core,
SCP_INSTANCE inst,
SCP_Lagrange_Sol best_mult_lb,
SCIP_Real  bestub,
SCIP_HEURDATA *  heurdata 
)
static

subgradient method with Held-Karp update of subgradients

Parameters
scipmaster SCIP data structure
coreSCP core data structure
inst(reduced) SCP instance
best_mult_lblagrange multiplier that gives the best lower bound for 'inst'
bestubcosts of the best known solution for 'inst'
heurdatapointer the heuristic's data

Definition at line 2170 of file heur_setcover.c.

References allocateMemoryForSolution(), computeOptimalSolution(), copySolution(), SCP_INSTANCE::costsfixed, freeMemoryForSolution(), isRowCovered(), SCP_Lagrange_Sol::lblagrangeglobal, SCP_Lagrange_Sol::lblagrangelocal, SCP_CORE::nconss, SCP_Lagrange_Sol::subgradient, and SCP_Lagrange_Sol::u.

Referenced by threePhase().

◆ computeInitialLagrangeMultiplier()

static SCIP_RETCODE computeInitialLagrangeMultiplier ( SCIP *  scip,
SCP_CORE core,
SCP_INSTANCE inst,
SCP_Lagrange_Sol mult,
SCIP_HEURDATA *  heurdata 
)
static

computes an initial lagrange multiplier, see formula (8) in the paper

Parameters
scipmaster SCIP data structure
coreSCP core data structure
inst(reduced) SCP instance
multinitialized lagrange multiplier were the new one will be stored
heurdatapointer to the heuristic's data

Definition at line 2308 of file heur_setcover.c.

References SCP_CORE::columns, SCP_CORE::columnsavailable, SCP_CORE::conss, getConsVars(), getVarIndex(), isCoreVariable(), isFixedVariable(), isRowCovered(), SCP_CORE::nconss, SCP_CORE::nvarconss, SCP_CORE::nvariables, SCP_Lagrange_Sol::u, and SCP_CORE::variables.

Referenced by threePhase().

◆ exploreNeighborhood()

◆ reportSolution()

static SCIP_RETCODE reportSolution ( SCIP *  scip,
SCP_INSTANCE inst,
SCIP_Bool *  solution,
SCIP_HEUR *  heur 
)
static
Parameters
scipmaster SCIP data structure
inst(reduced) SCP instance
solutionsolution for 'inst'; will be extended to global solution
heurpointer to the heuristic's data

Definition at line 2599 of file heur_setcover.c.

References isFixedVariable(), and isVarInSolution().

Referenced by setCoveringHeuristic(), and threePhase().

◆ threePhase()

static SCIP_RETCODE threePhase ( SCIP *  scip,
SCIP_HEUR *  heur,
SCIP_HEURDATA *  heurdata 
)
static

the three-phase procedure from the paper. It tries to find near-optimal lagrange multipliers and reduces the size of an instance by fixing variables that are likely to be in an optimal solution.

Parameters
scipmaster SCIP data structure
heurmaster SCIP heur data structure
heurdatapointer to the heuristic's data

Definition at line 2730 of file heur_setcover.c.

References checkSetCover(), computeInitialLagrangeMultiplier(), computeOptimalSolution(), copyInstance(), copySetCoverSolution(), copySolution(), SCP_INSTANCE::costsfixed, exploreNeighborhood(), fixVariable(), greedySetCover(), SCP_Lagrange_Sol::lblagrangelocal, markRowsCoveredByFixedVariables(), SCP_CORE::nactiveconss, SCP_CORE::nconss, SCP_INSTANCE::nrowscovered, SCP_CORE::nsolgreedy, removeRedundantColumns(), reportSolution(), SCP_CORE::solgreedy, subgradientOptimization(), SCP_CORE::variables, and SCP_Lagrange_Sol::xgreedylocal.

Referenced by setCoveringHeuristic().

◆ setCoveringHeuristic()

◆ SCIP_DECL_HEURFREE()

static SCIP_DECL_HEURFREE ( heurFreeSetcover  )
static

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

Definition at line 3060 of file heur_setcover.c.

◆ SCIP_DECL_HEURINIT()

static SCIP_DECL_HEURINIT ( heurInitSetcover  )
static

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

Definition at line 3080 of file heur_setcover.c.

References DEFAULT_RANDSEED.

◆ SCIP_DECL_HEUREXIT()

static SCIP_DECL_HEUREXIT ( heurExitSetcover  )
static

deinitialization method of primal heuristic (called before transformed problem is freed)

Definition at line 3100 of file heur_setcover.c.

◆ SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecSetcover  )
static

execution method of primal heuristic

Definition at line 3120 of file heur_setcover.c.

References GCGisMasterSetCovering(), GCGmasterGetOrigprob(), and setCoveringHeuristic().

◆ SCIPincludeHeurSetcover()

SCIP_RETCODE SCIPincludeHeurSetcover ( SCIP *  scip)