Detailed Description
set covering primal heuristic according to Caprara, Fischetti, and Toth (1999)
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 |
initializes a priority queue
- Parameters
-
scip master SCIP data structure queue priority 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 |
removes all elements from a priority queue, but does not release any memory
- Parameters
-
scip master SCIP data structure queue priority queue instance
Definition at line 213 of file heur_setcover.c.
References PQUEUE::size.
Referenced by greedySetCover().
◆ pqueue_destroy()
|
static |
releases all memory that is used by the priority queue
- Parameters
-
scip master SCIP data structure queue priority 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 |
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
-
scip master SCIP data structure queue priority queue instance key key of the new item elem value of the new item position address 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 |
decreases the key to 'key' of the element that is currently at position 'pos'
- Parameters
-
scip master SCIP data structure queue priority queue instance pos position of the item within the queue that is to be changed key new 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 |
increases the key to 'key' of the element that is currently at position 'pos'
- Parameters
-
scip master SCIP data structure queue priority queue instance pos position of the item within the queue that is to be changed key new 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 |
returns the value of a minimum element in 'elem'. Sets 'elem' to -1 if the queue is empty
- Parameters
-
scip master SCIP data structure queue priority queue instance elem address 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 |
allocates memory for a lagrange multiplier and a set covering solution
- Parameters
-
scip master SCIP data structure core core data structure mult uninitialized 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 |
checks if 'var' is a core variable
- Parameters
-
core initialized core data structure var SCIP 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 |
checks if 'var' is fixed within instance 'inst'
- Parameters
-
inst instance of the set covering problem var SCIP 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 |
checks if 'variable' is part of 'solution'
- Parameters
-
solution SCIP hashtable that contains SCIP variables var SCIP variable
Definition at line 541 of file heur_setcover.c.
Referenced by checkSetCover(), computeDelta(), copySetCoverSolution(), copySolution(), extendSolution(), removeRedundantColumns(), and reportSolution().
◆ addVarToCore()
|
static |
adds a variable to the core
- Parameters
-
core initialized core data structure var SCIP 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 |
fixes 'var' within instance 'inst'
- Parameters
-
inst SCP instance where 'variable' is to be fixed var SCIP 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 |
adds variable 'var' to 'solution'
- Parameters
-
solution solution represented as a boolean array var SCIP variable
Definition at line 599 of file heur_setcover.c.
Referenced by copySetCoverSolution(), copySolution(), extendSolution(), and greedySetCover().
◆ removeVarsFromCore()
|
static |
removes all variables from the core
- Parameters
-
scip SCIP data structure core initialized 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 |
removes a 'var' from 'solution'
- Parameters
-
solution solution represented as a boolean array var SCIP variable
Definition at line 634 of file heur_setcover.c.
Referenced by removeRedundantColumns().
◆ clearSolution()
|
static |
clears a solution
- Parameters
-
scip SCIP data structure solution solution represented as a boolean array
Definition at line 653 of file heur_setcover.c.
Referenced by copySetCoverSolution(), copySolution(), and greedySetCover().
◆ isRowCovered()
|
static |
checks if the row at position 'rowpos' is covered by fixed variables of 'inst'
- Parameters
-
inst SCP instance rowpos position 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 |
marks the row at position 'rowpos' as covered within instance 'inst'
- Parameters
-
inst SCP instance rowpos position 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 |
returns the position of 'variable' within the array core->variables
- Parameters
-
scip master SCIP data structure core SCP core data structure variable SCIP variable pos address 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 |
get all variables that are part of the constraint at position 'pos' (within SCIP) and saves them into 'vars'
- Parameters
-
scip master SCIP data structure core SCP core data structure pos position of the constraint within SCIP vars allocated memory that can hold all variables nvars address where the number of variables will be stored success address 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 |
releases all memory of a lagrange multiplier
- Parameters
-
scip master SCIP data structure mult initialized 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 |
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
-
scip master SCIP data structure core SCP core data structure inst SCP instance dest array where variables belonging to the solution are inserted destcosts address where the total costs of the solution will be stored source SCP 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 |
copies all data of the lagrange multiplier 'source' to the lagrange multiplier 'dest'
- Parameters
-
scip master SCIP data structure core SCP core data structure dest SCP lagrange multiplier where data will be copied to source SCP 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 |
initializes an instance where no variables are fixed and no rows are covered
- Parameters
-
scip master SCIP data structure inst unitialized 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 |
copies the fixed variables from 'source' to 'dest', but not the set of covered rows. this must be done separately.
- Parameters
-
scip master SCIP data structure core SCP core data structure dest initialized SCP instance source initialized 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 |
releases all memory used by an instance
- Parameters
-
scip master SCIP data structure inst initialized 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 |
initializes a tentative core: for each row the first few columns covering this row are added to the core
- Parameters
-
scip master SCIP data structure core SCP core data structure heurdata pointer to SCIP's heurdata
Definition at line 877 of file heur_setcover.c.
References addVarToCore(), SCP_CORE::columns, SCP_CORE::columnsavailable, SCP_CORE::conss, SCP_CORE::constraintid, SCP_CORE::delta, SCP_CORE::delta_pos, getVarIndex(), isCoreVariable(), SCP_CORE::listcorevariables, SCP_CORE::mapvariables, SCP_CORE::maxconstraintvariables, SCP_CORE::nactiveconss, SCP_CORE::nconss, SCP_CORE::ncorevariables, SCP_CORE::nrowvars, SCP_CORE::nsolgreedy, SCP_CORE::nvarconss, SCP_CORE::nvariables, SCP_CORE::rows, SCP_CORE::rowsavailable, SCP_CORE::solgreedy, SCP_CORE::variables, and SCP_CORE::varincore.
Referenced by setCoveringHeuristic().
◆ extendSolution()
|
static |
adds all fixed variables of 'inst' to a set covering solution 'solution'
- Parameters
-
scip master SCIP data structure core SCP core data structure inst (reduced) SCP instance solution SCP 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 |
constructs rows of all constraints, but only includes core variables
- Parameters
-
scip master SCIP data structure core SCP core data structure heurdata pointer 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 |
constructs columns of core variables to provide faster access
- Parameters
-
scip master SCIP data structure core SCP 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 |
releases memory that is used by the core, including rows and columns, if they were computed
- Parameters
-
scip master SCIP data structure core SCP 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 |
computes a new core based on the delta values of variables, see formula (9) in the paper
- Parameters
-
scip master SCIP data structure heurdata pointer 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 |
for all rows that are covered by the variables in inst->varsfixed, this function adds their indices to inst->rowscovered
- Parameters
-
scip master SCIP data structure core SCP core data structure inst initialized SCP instance where some variables may be fixed heurdata pointer 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 |
checks whether the given 'solution' is actually a set cover
- Parameters
-
scip master SCIP data structure core SCP core data structure inst SCP instance solution possible SCP solution issetcover address where TRUE will be stored if 'solution' is a set cover heurdata pointer 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 |
computes delta values for variables and fixes new variables within inst, see formula (9) of the paper
- Parameters
-
scip master SCIP data structure core SCP core data structure inst SCP instance lagrangiancosts array with lagrangian costs of the rows solution valid solution to the global SCP instance pi percentage of rows that need be covered by new fixed variables heurdata pointer 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 |
- Parameters
-
scip master SCIP data structure heurdata pointer to the heuristic's data solution solution to the global SCP instance solcosts pointer 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 |
greedy set cover algorithm that uses lagrangian costs instead of original costs.
- Parameters
-
scip master SCIP data structure core SCP core data structure inst (reduced) SCP instance mult lagrange multiplier that is used to compute lagrangian costs heurdata pointer 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 |
computes lagrangian costs for all columns, only considering rows that are uncovered by fixed variables in 'inst'
- Parameters
-
scip master SCIP data structure core SCP core data structure inst (reduced) SCP instance mult lagrange multiplier that is used to compute the lagrangian costs heurdata pointer 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 |
computes lagrangian costs for all columns of the unrestricted instance and a global lower bound.
- Parameters
-
scip master SCIP data structure core SCP core data structure mult lagrange multiplier that is used to compute the lagrangian costs heurdata pointer 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 |
computes an optimal solution to the lagrangian relaxation, see formulae (4), (5) in the paper
- Parameters
-
scip master SCIP data structure core SCP core data structure inst (reduced) SCP instance mult lagrange multiplier heurdata pointer 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 |
subgradient method with Held-Karp update of subgradients
- Parameters
-
scip master SCIP data structure core SCP core data structure inst (reduced) SCP instance best_mult_lb lagrange multiplier that gives the best lower bound for 'inst' bestub costs of the best known solution for 'inst' heurdata pointer 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 |
computes an initial lagrange multiplier, see formula (8) in the paper
- Parameters
-
scip master SCIP data structure core SCP core data structure inst (reduced) SCP instance mult initialized lagrange multiplier were the new one will be stored heurdata pointer 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()
|
static |
- Parameters
-
scip master SCIP data structure startmult lagrange multiplier where the search is started heurdata pointer to the heuristic's data
Definition at line 2463 of file heur_setcover.c.
References allocateMemoryForSolution(), computeOptimalSolution(), SCP_CORE::conss, copySetCoverSolution(), copySolution(), SCP_INSTANCE::costsfixed, extendSolution(), freeMemoryForSolution(), getConsVars(), getVarIndex(), greedySetCover(), isCoreVariable(), isRowCovered(), SCP_Lagrange_Sol::lagrangiancostslocal, SCP_Lagrange_Sol::lblagrangeglobal, SCP_Lagrange_Sol::lblagrangelocal, SCP_CORE::nconss, SCP_CORE::nrowvars, removeRedundantColumns(), SCP_CORE::rows, SCP_CORE::rowsavailable, SCP_Lagrange_Sol::subgradient, SCP_Lagrange_Sol::u, SCP_Lagrange_Sol::ubgreedylocal, SCP_CORE::variables, and SCP_Lagrange_Sol::xgreedylocal.
Referenced by threePhase().
◆ reportSolution()
|
static |
- Parameters
-
scip master SCIP data structure inst (reduced) SCP instance solution solution for 'inst'; will be extended to global solution heur pointer 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 |
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
-
scip master SCIP data structure heur master SCIP heur data structure heurdata pointer 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()
|
static |
driver for the three-phase procedure
- Parameters
-
scip master SCIP data structure heur original SCIP heuristic data structure
Definition at line 2855 of file heur_setcover.c.
References allocateMemoryForSolution(), checkSetCover(), computeCoreColumns(), computeCoreRows(), computeDelta(), SCP_INSTANCE::costsfixed, freeCore(), freeInstance(), freeMemoryForSolution(), initInstance(), initTentativeCore(), markRowsCoveredByFixedVariables(), SCP_CORE::nactiveconss, SCP_INSTANCE::nrowscovered, SCP_CORE::nvariables, SCP_INSTANCE::nvarsfixed, pqueue_destroy(), pqueue_init(), redefineCore(), reportSolution(), SCP_INSTANCE::rowscovered, threePhase(), and SCP_INSTANCE::varsfixed.
Referenced by SCIP_DECL_HEUREXEC().
◆ SCIP_DECL_HEURFREE()
|
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 |
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 |
deinitialization method of primal heuristic (called before transformed problem is freed)
Definition at line 3100 of file heur_setcover.c.
◆ SCIP_DECL_HEUREXEC()
|
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 | ) |
creates the setcover primal heuristic and includes it in SCIP
- Parameters
-
scip SCIP data structure
Definition at line 3163 of file heur_setcover.c.
References DEF_BETA, DEF_CORE_TENT_SIZE, DEF_GREEDY_MAX_ITER, DEF_LAMBDA, DEF_LAMBDA_ADJUSTMENTS, DEF_LAMBDA_P, DEF_MAX_ITER, DEF_MAX_ITER_NO_IMP, DEF_MIN_PROB_SIZE, DEF_PI_ALPHA, DEF_PI_MIN, DEF_STOP_CRIT_DIFF, DEF_STOP_CRIT_ITER, DEF_STOP_CRIT_RATIO, DEF_THREEPHASE_MAX_ITER, HEUR_DESC, HEUR_DISPCHAR, HEUR_FREQ, HEUR_FREQOFS, HEUR_MAXDEPTH, HEUR_NAME, HEUR_PRIORITY, HEUR_TIMING, and HEUR_USESSUBSCIP.
Referenced by GCGincludeMasterPlugins().