pricer_rpa.c
Go to the documentation of this file.
20 * This file implements the variable pricer which checks if variables negative reduced cost exist. See
25 * The task of the pricer is to search for new variables with negative reduced costs. For this, the following non-linear
37 * This problem is very hard, but can be modeled as a weighted circle packing problem for a single rectangle. Therefore,
38 * we first use a simple greedy heuristic to solve the problem. If the heuristic fails, the MINLP is solved with
39 * conventional methods on a new \SCIP instance and a given time limit. If the problem can be solved and the optimal
40 * value is non-negative, the LP relaxation has been solved to optimality and what remains is ensuring integrality of
41 * the solution by the normal \SCIP framework. If, on the other hand, the best solution found by both methods is negative,
42 * we have found an improving pattern, whose corresponding variable needs to be added to the restricted master problem.
43 * It is possible (and not unlikely) that neither method succeeds in finding a pattern with negative solution value. In
44 * that case, we also exit the pricing loop, just as if we had found an optimal solution, and proceed with enforcing
47 * In case that the pricing problem cannot be solved to optimality, we cannot directly deduce a lower bound for the
48 * master problem. However, the following theorem by Farley shows how a valid dual bound can be computed from the
50 * <a href="https://doi.org/10.1287/opre.38.5.922">A Note on Bounding a Class of Linear Programming Problems, Including
55 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
76 #define PRICER_DELAY TRUE /* only call pricer if all problem variables have non-negative reduced costs */
83 #define DEFAULT_PRICING_TOTALTILIM 1e+20 /**< total time limit for all pricing NLPs and heuristic calls */
114 /** returns an upper bound on the density for n equal circles in a square (holds also for rectangles); this is a result
123 return (n * M_PI) / SQR(2.0 - SQRT(3.0) + SQRT(7.0 - M_PI + SQRT(3.0)*(2.0*n - 6.0 + M_PI)) );/*lint !e666*/
153 /* special cases where too big circles have a minimum distance to each other (in x direction) */
219 SCIP_CALL( SCIPcreateVarBasic(scip, &var, name, 0.0, SCIPinfinity(scip), 1.0, SCIP_VARTYPE_INTEGER) );
257 SCIP_Bool* success /**< pointer to store if we could add at least one variable with negative reduced costs */
277 SCIPdebugMsg(scip, "found column with reduced cost = %f\n", 1.0 + SCIPgetSolOrigObj(subscip, sol));
382 SCIP_Bool* addedvar /**< pointer to store whether a variable with negative reduced cost has been added */
457 computeScores(scip, rexts, pricerdata->randnumgen, elements, nelements, lambdas, scores, niters, iterlim);
477 if( SCIPisFeasLT(scip, redcosts, bestredcosts) || (SCIPisGT(scip, vol, bestvol) && SCIPisFeasNegative(scip, redcosts)) )
479 SCIPdebugMsg(scip, "pricing heuristic found column with reduced costs %g and volume %g after %d iterations\n", redcosts, vol, niters + 1);
508 SCIP_Bool* addedvar, /**< pointer to store whether a variable with negative reduced cost has been added */
579 SCIPdebugMsg(scip, "use %d/%d circles of type %d\n", getNCircles(scip, rexts[t], demands[t], width, height, lambdas[t]), demands[t], t);
601 SCIP_CALL( SCIPcreateVarBasic(subscip, &x[pos], name, rexts[t], width - rexts[t], 0.0, SCIP_VARTYPE_CONTINUOUS) );
605 SCIP_CALL( SCIPcreateVarBasic(subscip, &y[pos], name, rexts[t], height - rexts[t], 0.0, SCIP_VARTYPE_CONTINUOUS) );
651 SCIP_CALL( SCIPcreateConsQuadraticNonlinear(subscip, &cons, name, 2, linvars, lincoefs, 6, quadvars1, quadvars2,
652 quadcoefs, -c, SCIPinfinity(subscip), TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE) );
709 SCIP_CALL( SCIPcreateConsBasicLinear(subscip, &cons, name, nvars, w, vols, 0.0, width * height) );
765 /** initialization method of variable pricer (called after problem was transformed and pricer is active) */
779 /** deinitialization method of variable pricer (called before transformed problem is freed and pricer is active) */
842 heurtimelimit = MIN(pricerdata->heurtilim, totaltilim - SCIPgetSolvingTime(scip)); /*lint !e666*/
844 SCIP_CALL( solvePricingHeuristic(scip, probdata, pricerdata, lambdas, heurtimelimit, pricerdata->heuriterlim, &success) );
851 /* solve pricing problem as MINLP if heuristic was not successful and dual bound is still valid */
854 nlptimelimit = MIN3(pricerdata->timeleft, pricerdata->nlptilim, totaltilim - SCIPgetSolvingTime(scip)); /*lint !e666*/
856 SCIP_CALL( solvePricingMINLP(scip, probdata, lambdas, nlptimelimit, pricerdata->nlpnodelim, &success, &solstat,
866 SCIPinfoMessage(scip, NULL, "+++++++++++++ LP(master) = ceil(%g) = %g\n", *lowerbound, SCIPfeasCeil(scip, *lowerbound));
872 SCIPinfoMessage(scip, NULL, "+++++++++++++ Farley's bound = ceil(%g/%g) = %g\n", SCIPgetLPObjval(scip), 1.0 - redcostslb,
923 SCIP_CALL( SCIPincludePricerBasic(scip, &pricer, PRICER_NAME, PRICER_DESC, PRICER_PRIORITY, PRICER_DELAY,
939 &pricerdata->nlpnodelim, FALSE, DEFAULT_PRICING_NLPNODELIM, 0L, SCIP_LONGINT_MAX, NULL, NULL) );
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
Definition: scip_randnumgen.c:70
static void computeScores(SCIP *scip, SCIP_Real *rexts, SCIP_RANDNUMGEN *randnumgen, int *elements, int nelements, SCIP_Real *lambdas, SCIP_Real *scores, int iter, int iterlim)
Definition: pricer_rpa.c:322
Definition: type_result.h:33
Definition: pattern.h:47
SCIP_RETCODE SCIPpatternAddElement(SCIP_PATTERN *pattern, int type, SCIP_Real x, SCIP_Real y)
Definition: pattern.c:173
SCIP_RETCODE SCIPcreateConsBasicLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs)
Definition: cons_linear.c:18010
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:786
Definition: struct_scip.h:59
static int getNCircles(SCIP *scip, SCIP_Real rext, int demand, SCIP_Real width, SCIP_Real height, SCIP_Real lambda)
Definition: pricer_rpa.c:128
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:298
Definition: type_result.h:49
Problem data for ringpacking problem.
Definition: struct_var.h:198
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:862
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:825
SCIP_RETCODE SCIPsetHeuristics(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:897
int * SCIPprobdataGetDemands(SCIP_PROBDATA *probdata)
Definition: probdata_rpa.c:1540
void SCIPprobdataInvalidateDualbound(SCIP *scip, SCIP_PROBDATA *probdata)
Definition: probdata_rpa.c:1675
SCIP_RETCODE SCIPaddLongintParam(SCIP *scip, const char *name, const char *desc, SCIP_Longint *valueptr, SCIP_Bool isadvanced, SCIP_Longint defaultvalue, SCIP_Longint minvalue, SCIP_Longint maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:102
static SCIP_RETCODE extractVariablesMINLP(SCIP *scip, SCIP_PROBDATA *probdata, SCIP *subscip, SCIP_VAR **x, SCIP_VAR **y, SCIP_VAR **w, int *types, int nvars, SCIP_Bool *success)
Definition: pricer_rpa.c:248
SCIP_PRICER * SCIPfindPricer(SCIP *scip, const char *name)
Definition: scip_pricer.c:302
Definition: type_var.h:53
Definition: struct_misc.h:259
SCIP_RETCODE SCIPcreateVarBasic(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype)
Definition: scip_var.c:185
SCIP_RETCODE SCIPsetPricerExit(SCIP *scip, SCIP_PRICER *pricer, SCIP_DECL_PRICEREXIT((*pricerexit)))
Definition: scip_pricer.c:238
void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
Definition: scip_param.c:594
Definition: struct_pricer.h:37
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:74
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
Definition: cons_linear.c:18162
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:199
SCIP_RETCODE SCIPcreateProbBasic(SCIP *scip, const char *name)
Definition: scip_prob.c:170
SCIP_Bool SCIPprobdataIsDualboundInvalid(SCIP_PROBDATA *probdata)
Definition: probdata_rpa.c:1690
static SCIP_DECL_PRICERREDCOST(pricerRedcostRingpacking)
Definition: pricer_rpa.c:794
Definition: struct_sol.h:64
Definition: pattern.h:43
void SCIPpackCirclesGreedy(SCIP *scip, SCIP_Real *rexts, SCIP_Real *xs, SCIP_Real *ys, SCIP_Real rbounding, SCIP_Real width, SCIP_Real height, SCIP_Bool *ispacked, int *elements, int nelements, SCIP_PATTERNTYPE patterntype, int *npacked, int ncalls)
Definition: probdata_rpa.c:1703
static SCIP_RETCODE solvePricingHeuristic(SCIP *scip, SCIP_PROBDATA *probdata, SCIP_PRICERDATA *pricerdata, SCIP_Real *lambdas, SCIP_Real timelim, int iterlim, SCIP_Bool *addedvar)
Definition: pricer_rpa.c:375
int SCIPprobdataGetNTypes(SCIP_PROBDATA *probdata)
Definition: probdata_rpa.c:1510
SCIP_Real SCIPprobdataGetHeight(SCIP_PROBDATA *probdata)
Definition: probdata_rpa.c:1561
Definition: struct_cons.h:37
SCIP_Real SCIPgetDualsolLinear(SCIP *scip, SCIP_CONS *cons)
Definition: cons_linear.c:18626
SCIP_RETCODE SCIPincludePricerBasic(SCIP *scip, SCIP_PRICER **pricerptr, const char *name, const char *desc, int priority, SCIP_Bool delay, SCIP_DECL_PRICERREDCOST((*pricerredcost)), SCIP_DECL_PRICERFARKAS((*pricerfarkas)), SCIP_PRICERDATA *pricerdata)
Definition: scip_pricer.c:118
static SCIP_RETCODE addVariable(SCIP *scip, SCIP_PROBDATA *probdata, int *types, SCIP_Real *xs, SCIP_Real *ys, SCIP_Bool *ispacked, int nelems)
Definition: pricer_rpa.c:174
Definition: type_stat.h:52
pattern data for ringpacking problem
SCIP_RETCODE SCIPcreateConsQuadraticNonlinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nlinvars, SCIP_VAR **linvars, SCIP_Real *lincoefs, int nquadterms, SCIP_VAR **quadvars1, SCIP_VAR **quadvars2, SCIP_Real *quadcoefs, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable)
Definition: cons_nonlinear.c:11206
SCIP_CONS ** SCIPprobdataGetPatternConss(SCIP_PROBDATA *probdata)
Definition: probdata_rpa.c:1607
Definition: type_retcode.h:33
Definition: type_stat.h:33
SCIP_RETCODE SCIPsetPricerInit(SCIP *scip, SCIP_PRICER *pricer, SCIP_DECL_PRICERINIT((*pricerinit)))
Definition: scip_pricer.c:214
Definition: pattern.h:35
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
Definition: scip_randnumgen.c:47
SCIP_RETCODE SCIPactivatePricer(SCIP *scip, SCIP_PRICER *pricer)
Definition: scip_pricer.c:375
SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip)
Definition: scipdefplugins.c:28
SCIP_Real * SCIPprobdataGetRexts(SCIP_PROBDATA *probdata)
Definition: probdata_rpa.c:1520
Definition: type_var.h:54
void SCIPsetMessagehdlrQuiet(SCIP *scip, SCIP_Bool quiet)
Definition: scip_message.c:99
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:478
SCIP_RETCODE SCIPsetPricerFree(SCIP *scip, SCIP_PRICER *pricer, SCIP_DECL_PRICERFREE((*pricerfree)))
Definition: scip_pricer.c:190
SCIP_RETCODE SCIPpatternCreateRectangular(SCIP *scip, SCIP_PATTERN **pattern)
Definition: pattern.c:98
SCIP_Real SCIPprobdataGetWidth(SCIP_PROBDATA *probdata)
Definition: probdata_rpa.c:1550
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:10025
SCIP_RETCODE SCIPaddPricedVar(SCIP *scip, SCIP_VAR *var, SCIP_Real score)
Definition: scip_prob.c:1731
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:477
void SCIPprobdataUpdateDualbound(SCIP *scip, SCIP_PROBDATA *probdata, SCIP_Real dualbound)
Definition: probdata_rpa.c:1659
void SCIPpatternRelease(SCIP *scip, SCIP_PATTERN **pattern)
Definition: pattern.c:117
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1110
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:850
SCIP_RETCODE SCIPvarSetInitial(SCIP_VAR *var, SCIP_Bool initial)
Definition: var.c:17338
void SCIPpatternSetPackableStatus(SCIP_PATTERN *pattern, SCIP_PACKABLE packable)
Definition: pattern.c:336
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:464
static SCIP_RETCODE solvePricingMINLP(SCIP *scip, SCIP_PROBDATA *probdata, SCIP_Real *lambdas, SCIP_Real timelim, SCIP_Longint nodelim, SCIP_Bool *addedvar, SCIP_STATUS *solstat, SCIP_Real *dualbound)
Definition: pricer_rpa.c:502
SCIP_RETCODE SCIPvarSetRemovable(SCIP_VAR *var, SCIP_Bool removable)
Definition: var.c:17354
SCIPallocBlockMemory(scip, subsol))
Ringpacking variable pricer.
SCIP_RETCODE SCIPprobdataAddVar(SCIP *scip, SCIP_PROBDATA *probdata, SCIP_PATTERN *pattern, SCIP_VAR *var)
Definition: probdata_rpa.c:1617
Definition: objbenders.h:33
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1352
default SCIP plugins
static SCIP_DECL_PRICERFARKAS(pricerFarkasRingpacking)
Definition: pricer_rpa.c:893
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:130
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip_param.c:536
SCIP callable library.
Definition: type_paramset.h:52
Definition: type_var.h:58