heur_setcover.c
Go to the documentation of this file.
34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
46 #define HEUR_DESC "set covering primal heuristic according to Caprara, Fischetti, and Toth (1999)"
55 #define DEF_CORE_TENT_SIZE 10 /**< number of columns covering each row that are added to the tentative core at the beginning */
59 #define DEF_STOP_CRIT_ITER 300 /**< number of iterations of the subgradient phase after which the stopping criterion is tested again */
60 #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 */
61 #define DEF_STOP_CRIT_RATIO 0.99 /**< the relative ratio between best lower and upper bound is less than DEF_STOP_CRIT_RATIO */
63 #define DEF_PI_ALPHA 1.1 /**< increase of pi when no improvement was made, i.e. more columns will be fixed */
64 #define DEF_BETA 1.025 /**< allowed gap between lowerbound and upper bound during the subgradient phase */
66 #define DEF_MAX_ITER_NO_IMP 1 /**< stop of no improvements during the last X iterations of three-phase */
68 #define DEF_GREEDY_MAX_ITER 100 /**< number of multipliers that are used for computing greedy solutions during each iteration */
69 #define DEF_MIN_PROB_SIZE 1000 /**< minimum number of variables the problem has to contain for the heuristic to start */
91 SCIP_Bool* rowscovered; /**< boolean array that indicates which rows are covered by the fixed variables */
101 SCIP_HASHMAP* mapvariables; /**< maps variables-indices to [0, nvariables) in array 'variables' */
103 int* nvarconss; /**< array that contains for each variable the number of constraints it is part of */
105 SCIP_Bool columnsavailable; /**< if set then 'columns' contains the columns for all core variables */
111 int nactiveconss; /**< total number of active constraints for which the variables can be retrieved */
123 SCIP_Bool* xgreedylocal; /**< contains variables that are part of a greedy solution, this is not necessarily a global solution */
126 SCIP_Real* lagrangiancostslocal; /**< lagrangian costs (for a certain instance) when only uncovered rows are considered */
127 SCIP_Real* lagrangiancostsglobal; /**< lagrangian costs for the whole instance when all rows and columns are considered */
128 SCIP_Real ubgreedylocal; /**< bound computed by the greedy set cover algorithm for the restricted instance */
129 SCIP_Real lblagrangelocal; /**< lower bound by lagrange relaxation for the restricted instance */
130 SCIP_Real lblagrangeglobal; /**< lower bound by lagrange relaxation for the unrestricted instance */
135 int param_core_tent_size; /**< number of columns covering each row that are added to the tentative core at the beginning */
139 int param_stop_crit_iter; /**< number of iterations of the subgradient phase after which the stopping criterion is tested again */
140 SCIP_Real param_stop_crit_diff; /**< stop if absolute difference between best lower and upper bound is less than SCP_STOP_CRIT_DIFF, and */
141 SCIP_Real param_stop_crit_ratio; /**< the relative gap between best lower and upper bound is less than (1 - SCP_STOP_CRIT_PER */
143 SCIP_Real param_pi_alpha; /**< increase of pi when no improvement was made, i.e. more columns will be fixed */
144 SCIP_Real param_beta; /**< allowed a gap between lowerbound and upper bound during the subgradient phase */
146 int param_max_iter_no_imp; /**< stop of no improvements during the last X iterations of three-phase */
148 int param_greedy_max_iter; /**< number of multipliers that are used for computing greedy solutions during each iteration */
149 int param_min_prob_size; /**< minimum number of variables the master problem needs to contain before the heuristic starts at all */
152 SCP_INSTANCE inst; /**< reduced instance where some variables may be fixed and some rows be covered */
155 SCP_Lagrange_Sol multbestlbtotal; /**< lagrange multiplier that gives the best lower bound for the complete problem */
161 SCIP_Real bestubinst; /**< best upper bound for the reduced instance 'inst' (including fixed costs) */
162 SCIP_Bool* bestubinst_sol; /**< actual solution for the instance 'inst' (including fixed variables) */
163 SCIP_Real bestubsubinst; /**< best upper bound for the reduced instance 'subinst' (including fixed costs) */
164 SCIP_Bool* bestubsubinstsol; /**< actual solution for the instance 'subinst' (including fixed variables) */
171 SCIP_Bool useinitialmultiplier; /**< compute an own initial lagrange multiplier instead of using the best known */
234 * If 'position' is not NULL, the referenced memory location will always contain the internal position of the element
437 /** returns the value of a minimum element in 'elem'. Sets 'elem' to -1 if the queue is empty */
710 *pos = (int) (size_t) SCIPhashmapGetImage(core->mapvariables, (void *) ((size_t) (varidx + 1))); /*lint !e507*/
715 /** get all variables that are part of the constraint at position 'pos' (within SCIP) and saves them into 'vars' */
736 SCIP_CALL( SCIPgetConsVars(scip, core->conss[pos], vars, core->maxconstraintvariables, success) );
755 /** creates a set covering solution. Adds all fixed variables of 'inst' and all variables of 'source' to 'dest'.
803 memcpy(dest->lagrangiancostslocal, source->lagrangiancostslocal, sizeof(*dest->lagrangiancostslocal) * core->nvariables);
804 memcpy(dest->lagrangiancostsglobal, source->lagrangiancostsglobal, sizeof(*dest->lagrangiancostsglobal) * core->nvariables);
835 /** copies the fixed variables from 'source' to 'dest', but not the set of covered rows. this must be done separately. */
875 /** initializes a tentative core: for each row the first few columns covering this row are added to the core */
917 SCIP_CALL( SCIPhashmapInsert(core->mapvariables, (void *) ((size_t) (varidx + 1)), (void *) (size_t) i) );
943 SCIPdebugMessage("constraint %i (%s): can't get number of variables\n", i, SCIPconsGetName(core->conss[i]));
950 SCIPdebugMessage("constraint %i (%s): can't get variables\n", i, SCIPconsGetName(core->conss[i]));
1121 /* only allocate memory of it is part of any constraints at all (this should always be the case for core variables) */
1125 SCIP_CALL( SCIPallocBufferArray(scip, &(core->columns[i]), core->nvarconss[i]) ); /*lint !e866*/
1166 /** releases memory that is used by the core, including rows and columns, if they were computed */
1211 /** computes a new core based on the delta values of variables, see formula (9) in the paper */
1228 /* assumption: delta values were already computed and are sorted in increasing order, this happens in computeDelta */
1241 /* release memory that is used for the core rows and columns. it will be allocated again later on */
1291 /* then add the first 'SCP_CORE_TENT_SIZE' columns covering each row in increasing order of their delta values */
1308 /* iterate through list of variables that are part of this constraint, and find the 'param_core_tent_size' variables with lowest delta values */
1378 /** for all rows that are covered by the variables in inst->varsfixed, this function adds their indices to inst->rowscovered */
1421 /* if the core columns are not available, iterate through list of constraints and test which conss are covered */
1474 /* iterate through all constraints and check whether each of them contains a variable that is part of the cover */
1505 /** computes delta values for variables and fixes new variables within inst, see formula (9) of the paper */
1594 delta[i] += lagrangiancosts[rowpos] * (nvarcovering[rowpos] - 1) / ((SCIP_Real) nvarcovering[rowpos]);
1598 /* sort the variables in increasing order of their delta values, delta_pos is used to track the variables within the array */
1633 /* removes redundant columns from 'solution' by removing them one by one (in the order of decreasing costs),
1717 * We use negative costs because we only sort them in increasing order and want to remove the ones with highest costs first.
1718 * The 'varpos' array is used to track which variable is where within the sorted array (it is permutated in the same way as 'costs') */
1733 /* for each variable of the solution: try to remove it and check whether it is still a set cover */
1739 /* we can only remove this variable if every column it covers is covered by another variable */
1808 /* this is actually necessary because there exist constraints where this fails, and we simply need to ignore them */
1826 colpos = heurdata->greedycolpos; /* this array contains the position of the element within the queue and is needed to update the costs */
1827 colmu = heurdata->greedycolmu; /* for each column this contains the number of uncovered rows that it covers */
1828 colgamma = heurdata->greedycolgamma; /* for each column this contains the lagrangian costs of uncovered rows that it covers */
1835 /* compute initial scores for all unfixed columns, see "3. Heuristic Phase" of the paper, and add them to the priority queue */
1889 /* mark all rows covered by this variable as covered and update scores of variables that are affected by this */
1927 colscore[varpos] = (colgamma[varpos] > 0) ? (colgamma[varpos] / ((SCIP_Real) colmu[varpos])) : (colgamma[varpos] * colmu[varpos]);
1942 /** computes lagrangian costs for all columns, only considering rows that are uncovered by fixed variables in 'inst' */
1948 SCP_Lagrange_Sol* mult, /**< lagrange multiplier that is used to compute the lagrangian costs*/
2010 /** computes lagrangian costs for all columns of the unrestricted instance and a global lower bound. */
2015 SCP_Lagrange_Sol* mult, /**< lagrange multiplier that is used to compute the lagrangian costs*/
2061 /** computes an optimal solution to the lagrangian relaxation, see formulae (4), (5) in the paper */
2084 /* also, compute costs for the unrestricted instance. This even computes mult->lblagrangeglobal */
2126 /* to get a lower bound from the multiplier we still need to subtract sum_i u[i] from lblagrangelocal */
2174 SCP_Lagrange_Sol* best_mult_lb, /**< lagrange multiplier that gives the best lower bound for 'inst' */
2198 /* permutate best u by multiplying each entry with a uniformly random value in the range [0.9, 1.1] */
2218 norm = norm + last_mult.subgradient[i] * last_mult.subgradient[i]; /* we have subgradient[i] = 0.0 if row i is not to be considered */
2227 SCIP_Real hk = last_mult.u[i] + lambda * (bestub - last_mult.lblagrangelocal) * last_mult.subgradient[i] / norm; /*lint !e795*/
2286 /* we test how the current best lower bound compares to the best lower bound that was known 'stop_crit_iter' iterations ago:
2290 if( (iter > 0) && (best_mult_lb->lblagrangelocal - stop_crit_lb <= heurdata->param_stop_crit_diff )
2312 SCP_Lagrange_Sol* mult, /**< initialized lagrange multiplier were the new one will be stored */
2562 SCIP_Real hk = mult.u[i] + heurdata->param_lambda * (bestub - mult.lblagrangelocal) * mult.subgradient[i] / norm; /*lint !e795*/
2580 /* apply the greedy algorithm and extend it to a solution of the unrestricted instance by adding fixed variables */
2589 copySetCoverSolution(scip, core, subinst, heurdata->bestubsubinstsol, &heurdata->bestubsubinst, mult.xgreedylocal);
2624 else if( (isFixedVariable(inst, solvars[i]) == TRUE) && (SCIPisZero(scip, SCIPvarGetObj(solvars[i])) == FALSE) )
2632 /* test all constraints and check if the activity is correct, adjust some free variable if necessary */
2659 SCIPerrorMessage("constraint is '%s', can't handle this\n", SCIPconshdlrGetName(SCIPconsGetHdlr(conss[i])));
2727 /** the three-phase procedure from the paper. It tries to find near-optimal lagrange multipliers and
2728 * reduces the size of an instance by fixing variables that are likely to be in an optimal solution. */
2749 /* we first create our own copy of the instance, as we need to mark variables as fixed until all variables are fixed */
2753 /* if this function is called for the first time, no multiplier is available and we need to compute one to start with */
2766 /* computeOptimalSolution computes an optimal solution to the lagrange relaxation. Also, it computes the subgradient */
2770 /* we now have a lower and upper bound in mult_lb_local for the instance 'inst' and take these as our starting values */
2771 copySetCoverSolution(scip, core, inst, heurdata->bestubinst_sol, &heurdata->bestubinst, mult_lb_subinst->xgreedylocal);
2772 copySetCoverSolution(scip, core, subinst, heurdata->bestubsubinstsol, &heurdata->bestubsubinst, mult_lb_subinst->xgreedylocal);
2783 /* in the first call of this proceduce there is no best upper bound for the unrestricted instance */
2786 copySetCoverSolution(scip, core, inst, heurdata->bestubsol, &heurdata->bestub, heurdata->bestubinst_sol);
2797 * 1. Derive the subinstance 'subinst' by marking all rows as covered that are covered by fixed variables of 'subinst'. If all rows are covered by fixed variables, stop.
2798 * 2. Perform subgradient optimization to find a lagrange multiplier that gives a better lower bound for 'subinst'.
2799 * 3. Explore the neighborhood of this best multiplier by doing additional subgradient steps and calling the greedy algorithm with each multiplier as argument.
2804 /* stop if all rows are covered by fixed variables or a maximum number of iterations has been reached */
2805 for( niter = 0; niter < heurdata->param_threephase_max_iter && core->nactiveconss > subinst->nrowscovered; ++niter )
2807 /* we mark all rows covered by fixed variables, in addition to the ones that were already covered */
2809 SCIP_CALL( subgradientOptimization(scip, core, subinst, mult_lb_subinst, heurdata->bestubsubinst, heurdata) );
2811 /* explore neighborhood of the best lower bound multiplier by applying the held-karp update again.
2818 copySetCoverSolution(scip, core, subinst, heurdata->bestubinst_sol, &heurdata->bestubinst, heurdata->bestubsubinstsol);
2820 /* extend a solution of 'inst' to a solution of the whole instance and check whether this gives a better global upper bound */
2823 copySetCoverSolution(scip, core, inst, heurdata->bestubsol, &heurdata->bestub, heurdata->bestubinst_sol);
2864 int niternoimp = 0; /* number of iterations for how long no improvement on the upper bound was made */
2879 SCIP_CALL( SCIPallocBufferArray(scip, &heurdata->rccoldelta, heurdata->param_core_tent_size) );
2884 /* we always consider core variables (columns) only to cover rows, so we need to define the first core.
2885 * This is done by choosing for each row the first five columns covering it and adding them to the core. */
2889 * 'maxconstraintvariables' is the maximum number of variables any constraint of the problem contains. */
2890 SCIP_CALL( SCIPallocBufferArray(scip, &heurdata->vars, heurdata->core.maxconstraintvariables) );
2940 SCIPdebugMessage("%d variables are fixed, %d rows are covered\n", inst->nvarsfixed, inst->nrowscovered);
2963 /* increase pi if no better solution was found, i.e. fix more variables in order to cover more rows */
2983 /* compute delta fixes variables of 'bestubsol' within the core that are likely to be part of an optimal solution */
2985 SCIP_CALL( computeDelta(scip, core, inst, heurdata->multbestlbtotal.lagrangiancostsglobal, heurdata->bestubsol, pi, heurdata) );
3005 SCIPdebugMessage("iteration %i: best lower bound: %f, best upper bound: %f\n", niter, heurdata->multbestlbtotal.lblagrangeglobal, heurdata->bestub);
3098 /** deinitialization method of primal heuristic (called before transformed problem is freed) */
3140 SCIPdebugMessage("not running set covering heuristic because instance is too small (only %i variables)\n", SCIPgetNVars(scip));
3213 "maximum absolute difference between lower and upper bound that is allowed for the stopping criterion",
3217 "minimum ratio between lower and upper bound that is allowed that is allowed for the stopping criterion",
3238 &heurdata->param_threephase_max_iter, FALSE, DEF_THREEPHASE_MAX_ITER, 1, INT_MAX, NULL, NULL) );
static void clearSolution(SCIP *scip, SCIP_Bool *solution)
Definition: heur_setcover.c:653
static SCIP_RETCODE checkSetCover(SCIP *scip, SCP_CORE *core, SCP_INSTANCE *inst, SCIP_Bool *solution, SCIP_Bool *issetcover, SCIP_HEURDATA *heurdata)
Definition: heur_setcover.c:1448
static SCIP_Bool isFixedVariable(SCP_INSTANCE *inst, SCIP_VAR *var)
Definition: heur_setcover.c:523
static SCIP_Bool isVarInSolution(SCIP_Bool *solution, SCIP_VAR *var)
Definition: heur_setcover.c:541
GCG interface methods.
static void copySolution(SCIP *scip, SCP_CORE *core, SCP_Lagrange_Sol *dest, SCP_Lagrange_Sol *source)
Definition: heur_setcover.c:792
static void copySetCoverSolution(SCIP *scip, SCP_CORE *core, SCP_INSTANCE *inst, SCIP_Bool *dest, SCIP_Real *destcosts, SCIP_Bool *source)
Definition: heur_setcover.c:759
static SCIP_RETCODE computeCoreRows(SCIP *scip, SCP_CORE *core, SCIP_HEURDATA *heurdata)
Definition: heur_setcover.c:1016
Definition: heur_setcover.c:87
static void freeMemoryForSolution(SCIP *scip, SCP_Lagrange_Sol *mult)
Definition: heur_setcover.c:743
static void fixVariable(SCP_INSTANCE *inst, SCIP_VAR *var)
Definition: heur_setcover.c:579
static SCIP_RETCODE greedySetCover(SCIP *scip, SCP_CORE *core, SCP_INSTANCE *inst, SCP_Lagrange_Sol *mult, SCIP_HEURDATA *heurdata)
Definition: heur_setcover.c:1770
Definition: heur_setcover.c:121
static SCIP_RETCODE pqueue_init(SCIP *scip, PQUEUE *queue)
Definition: heur_setcover.c:196
static SCIP_Bool isRowCovered(SCP_INSTANCE *inst, int rowpos)
Definition: heur_setcover.c:669
static SCIP_RETCODE markRowsCoveredByFixedVariables(SCIP *scip, SCP_CORE *core, SCP_INSTANCE *inst, SCIP_HEURDATA *heurdata)
Definition: heur_setcover.c:1380
SCIP_Bool param_lambda_adjustments
Definition: heur_setcover.c:136
static SCIP_RETCODE computeDelta(SCIP *scip, SCP_CORE *core, SCP_INSTANCE *inst, SCIP_Real *lagrangiancosts, SCIP_Bool *solution, SCIP_Real pi, SCIP_HEURDATA *heurdata)
Definition: heur_setcover.c:1507
static SCIP_RETCODE setCoveringHeuristic(SCIP *scip, SCIP_HEUR *heur)
Definition: heur_setcover.c:2855
SCIP_RETCODE SCIPincludeHeurSetcover(SCIP *scip)
Definition: heur_setcover.c:3163
static SCIP_RETCODE computeOptimalSolution(SCIP *scip, SCP_CORE *core, SCP_INSTANCE *inst, SCP_Lagrange_Sol *mult, SCIP_HEURDATA *heurdata)
Definition: heur_setcover.c:2063
static void removeVarsFromCore(SCIP *scip, SCP_CORE *core)
Definition: heur_setcover.c:618
static SCIP_RETCODE threePhase(SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur_setcover.c:2730
GCG variable pricer.
static SCIP_RETCODE initInstance(SCIP *scip, SCP_INSTANCE *inst)
Definition: heur_setcover.c:821
static void pqueue_get_min(SCIP *scip, PQUEUE *queue, int *elem)
Definition: heur_setcover.c:439
static SCIP_Bool isCoreVariable(SCP_CORE *core, SCIP_VAR *var)
Definition: heur_setcover.c:505
static void copyInstance(SCIP *scip, SCP_CORE *core, SCP_INSTANCE *dest, SCP_INSTANCE *source)
Definition: heur_setcover.c:837
static SCIP_RETCODE computeInitialLagrangeMultiplier(SCIP *scip, SCP_CORE *core, SCP_INSTANCE *inst, SCP_Lagrange_Sol *mult, SCIP_HEURDATA *heurdata)
Definition: heur_setcover.c:2308
static SCIP_RETCODE computeCoreColumns(SCIP *scip, SCP_CORE *core)
Definition: heur_setcover.c:1092
static SCIP_RETCODE getConsVars(SCIP *scip, SCP_CORE *core, int pos, SCIP_VAR **vars, int *nvars, SCIP_Bool *success)
Definition: heur_setcover.c:717
static void markRowAsCovered(SCP_INSTANCE *inst, int rowpos)
Definition: heur_setcover.c:681
static void pqueue_decrease_key(SCIP *scip, PQUEUE *queue, int pos, SCIP_Real key)
Definition: heur_setcover.c:290
static SCIP_RETCODE exploreNeighborhood(SCIP *scip, SCP_Lagrange_Sol *startmult, SCIP_HEURDATA *heurdata)
Definition: heur_setcover.c:2463
SCIP_Real * lagrangiancostsglobal
Definition: heur_setcover.c:127
static SCIP_RETCODE computeLocalLagrangianCosts(SCIP *scip, SCP_CORE *core, SCP_INSTANCE *inst, SCP_Lagrange_Sol *mult, SCIP_HEURDATA *heurdata)
Definition: heur_setcover.c:1944
static SCIP_RETCODE subgradientOptimization(SCIP *scip, SCP_CORE *core, SCP_INSTANCE *inst, SCP_Lagrange_Sol *best_mult_lb, SCIP_Real bestub, SCIP_HEURDATA *heurdata)
Definition: heur_setcover.c:2170
static SCIP_RETCODE computeGlobalLagrangianCosts(SCIP *scip, SCP_CORE *core, SCP_Lagrange_Sol *mult, SCIP_HEURDATA *heurdata)
Definition: heur_setcover.c:2012
static SCIP_RETCODE getVarIndex(SCIP *scip, SCP_CORE *core, SCIP_VAR *variable, int *pos)
Definition: heur_setcover.c:695
static void addVarToSolution(SCIP_Bool *solution, SCIP_VAR *var)
Definition: heur_setcover.c:599
Definition: heur_setcover.c:78
set covering primal heuristic according to Caprara, Fischetti, and Toth (1999)
static SCIP_RETCODE initTentativeCore(SCIP *scip, SCP_CORE *core, SCIP_HEURDATA *heurdata)
Definition: heur_setcover.c:877
Definition: heur_setcover.c:96
Definition: heur_gcgdins.c:74
static void extendSolution(SCIP *scip, SCP_CORE *core, SCP_INSTANCE *inst, SCIP_Bool *solution)
Definition: heur_setcover.c:994
static SCIP_RETCODE removeRedundantColumns(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_Bool *solution, SCIP_Real *solcosts)
Definition: heur_setcover.c:1636
static void pqueue_increase_key(SCIP *scip, PQUEUE *queue, int pos, SCIP_Real key)
Definition: heur_setcover.c:333
static SCIP_RETCODE redefineCore(SCIP *scip, SCIP_HEURDATA *heurdata)
Definition: heur_setcover.c:1213
SCIP_Real * lagrangiancostslocal
Definition: heur_setcover.c:126
static SCIP_RETCODE pqueue_insert(SCIP *scip, PQUEUE *queue, SCIP_Real key, int elem, int *position)
Definition: heur_setcover.c:237
int param_threephase_max_iter
Definition: heur_setcover.c:147
static SCIP_RETCODE allocateMemoryForSolution(SCIP *scip, SCP_CORE *core, SCP_Lagrange_Sol *mult)
Definition: heur_setcover.c:470
static void removeVarFromSolution(SCIP_Bool *solution, SCIP_VAR *var)
Definition: heur_setcover.c:634
static SCIP_RETCODE reportSolution(SCIP *scip, SCP_INSTANCE *inst, SCIP_Bool *solution, SCIP_HEUR *heur)
Definition: heur_setcover.c:2599