82#define PRICER_NAME "ringpacking"
83#define PRICER_DESC "pricer for ringpacking"
84#define PRICER_PRIORITY 0
85#define PRICER_DELAY TRUE
88#define DEFAULT_PRICING_NLPTILIM 1e+20
89#define DEFAULT_PRICING_NLPNODELIM 1000L
90#define DEFAULT_PRICING_HEURTILIM 1e+20
91#define DEFAULT_PRICING_HEURITERLIM 1000
92#define DEFAULT_PRICING_TOTALTILIM 1e+20
97#define M_PI 3.141592653589793238462643
105struct SCIP_PricerData
113 SCIP_Longint nlpnodelim;
132 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)) );
156 volrect = width * height;
165 SCIP_Real
c = sqrt(4.0 * rext * height -
SQR(height));
170 SCIP_Real
c =
MIN(sqrt(3.0*rext*rext + rext * height - height * height / 4.0),
171 sqrt(8.0 * rext * height - height * height - 12.0 * rext * rext));
173 SCIP_Real l = (width - 2.0 * rext) /
c;
214 for(
i = 0;
i < nelems; ++
i )
216 if( ispacked ==
NULL || ispacked[
i] )
219 (void) strcat(name, strtmp);
236 for(
i = 0;
i < nelems; ++
i )
238 if( ispacked ==
NULL || ispacked[
i] )
310 selectedtypes[nselected] = types[
i];
347 for(
i = 0;
i < nelements; ++
i )
349 int elemtype = elements[
i];
350 SCIP_Real rext = rexts[elemtype];
354 scores[
i] = lambdas[elemtype];
365 else if( iter <= iterlim * 0.1 )
369 else if( iter <= iterlim * 0.4 )
373 else if( iter <= iterlim * 0.8 )
404 SCIP_Real bestredcosts;
430 for( t = 0; t < ntypes; ++t )
431 nelements +=
getNCircles(
scip, rexts[t], demands[t], width, height, lambdas[t]);
442 for( t = 0; t < ntypes; ++t )
447 n =
getNCircles(
scip, rexts[t], demands[t], width, height, lambdas[t]);
449 for(
i = 0;
i < n; ++
i )
451 elements[nelements] = t;
457 while( niters < iterlim
461 SCIP_Real redcosts = 1.0;
466 computeScores(
scip, rexts, pricerdata->randnumgen, elements, nelements, lambdas, scores, niters, iterlim);
472 SCIPpackCirclesGreedy(
scip, rexts, xs, ys, -1.0, width, height, ispacked, elements, nelements,
476 for(
i = 0;
i < nelements; ++
i )
480 redcosts -= lambdas[elements[
i]];
481 vol += rexts[elements[
i]];
488 SCIPdebugMsg(
scip,
"pricing heuristic found column with reduced costs %g and volume %g after %d iterations\n", redcosts, vol, niters + 1);
492 bestredcosts =
MIN(bestredcosts, redcosts);
493 bestvol =
MAX(bestvol, vol);
516 SCIP_Longint nodelim,
529 SCIP_Real quadcoefs[6];
530 SCIP_Real lincoefs[2];
585 for( t = 0; t < ntypes; ++t )
601 for( t = 0; t < ntypes; ++t )
603 SCIP_Real
obj = lambdas[t];
621 vols[pos] =
SQR(rexts[t]) *
M_PI;
634 assert(type1 >= 0 && type1 < ntypes);
636 for( j =
i+1; j <
nvars; ++j )
642 assert(types2 >= 0 && types2 < ntypes);
644 c = (rexts[type1] + rexts[types2]) * (rexts[type1] + rexts[types2]);
647 linvars[0] =
w[
i]; lincoefs[0] = -
c;
648 linvars[1] =
w[j]; lincoefs[1] = -
c;
651 quadvars1[0] =
x[
i]; quadvars2[0] =
x[
i]; quadcoefs[0] = 1.0;
652 quadvars1[1] =
x[
i]; quadvars2[1] =
x[j]; quadcoefs[1] = -2.0;
653 quadvars1[2] =
x[j]; quadvars2[2] =
x[j]; quadcoefs[2] = 1.0;
654 quadvars1[3] =
y[
i]; quadvars2[3] =
y[
i]; quadcoefs[3] = 1.0;
655 quadvars1[4] =
y[
i]; quadvars2[4] =
y[j]; quadcoefs[4] = -2.0;
656 quadvars1[5] =
y[j]; quadvars2[5] =
y[j]; quadcoefs[5] = 1.0;
661 quadcoefs, -
c,
SCIPinfinity(subscip),
TRUE,
TRUE,
TRUE,
TRUE,
TRUE,
FALSE,
FALSE,
FALSE,
FALSE) );
723 SCIPdebugMsg(
scip,
"----------------------- solve pricing problem -----------------------\n");
725 SCIPdebugMsg(
scip,
"---------------------------------------------------------------------\n");
810 SCIP_Real redcostslb;
811 SCIP_Real nlptimelimit;
812 SCIP_Real heurtimelimit;
813 SCIP_Real totaltilim;
869 SCIPdebugMsg(
scip,
"result of pricing MINLP: addedvar=%u soltat=%d\n", success, solstat);
933 pricerRedcostRingpacking, pricerFarkasRingpacking, pricerdata) );
941 "ringpacking/pricing/nlptilim",
942 "time limit for each pricing NLP",
946 "ringpacking/pricing/nlpnodelim",
947 "node limit for each pricing NLP",
951 "ringpacking/pricing/heurtilim",
952 "time limit for each heuristic pricing",
956 "ringpacking/pricing/heuriterlim",
957 "iteration limit for each heuristic pricing",
961 "ringpacking/pricing/totaltilim",
962 "total time limit for all pricing NLPs and heuristic calls",
SCIP_Real SCIPgetDualsolLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
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)
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)
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_RETCODE SCIPfree(SCIP **scip)
SCIP_RETCODE SCIPcreate(SCIP **scip)
SCIP_STATUS SCIPgetStatus(SCIP *scip)
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
SCIP_RETCODE SCIPaddPricedVar(SCIP *scip, SCIP_VAR *var, SCIP_Real score)
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
SCIP_PROBDATA * SCIPgetProbData(SCIP *scip)
SCIP_RETCODE SCIPcreateProbBasic(SCIP *scip, const char *name)
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
void SCIPsetMessagehdlrQuiet(SCIP *scip, SCIP_Bool quiet)
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)
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)
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
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)
SCIP_RETCODE SCIPsetHeuristics(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
SCIP_Real SCIPgetLPObjval(SCIP *scip)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
#define SCIPfreeBlockMemoryNull(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_RETCODE SCIPsetPricerFree(SCIP *scip, SCIP_PRICER *pricer,)
SCIP_RETCODE SCIPsetPricerInit(SCIP *scip, SCIP_PRICER *pricer,)
SCIP_PRICER * SCIPfindPricer(SCIP *scip, const char *name)
SCIP_PRICERDATA * SCIPpricerGetData(SCIP_PRICER *pricer)
SCIP_RETCODE SCIPsetPricerExit(SCIP *scip, SCIP_PRICER *pricer,)
SCIP_RETCODE SCIPactivatePricer(SCIP *scip, SCIP_PRICER *pricer)
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)
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
int SCIPgetNSols(SCIP *scip)
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
SCIP_RETCODE SCIPsolve(SCIP *scip)
SCIP_Real SCIPgetDualbound(SCIP *scip)
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
SCIP_Real SCIPgetTotalTime(SCIP *scip)
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
int SCIPgetDepth(SCIP *scip)
void SCIPvarMarkDeletable(SCIP_VAR *var)
SCIP_RETCODE SCIPvarSetInitial(SCIP_VAR *var, SCIP_Bool initial)
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
SCIP_RETCODE SCIPvarSetRemovable(SCIP_VAR *var, SCIP_Bool removable)
SCIP_RETCODE SCIPcreateVarBasic(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype)
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
int SCIPsnprintf(char *t, int len, const char *s,...)
SCIPfreeRandom(scip, &heurdata->randnumgen)
SCIPcreateRandom(scip, &heurdata->randnumgen, DEFAULT_RANDSEED, TRUE))
assert(minobj< SCIPgetCutoffbound(scip))
#define BMSclearMemory(ptr)
SCIP_RETCODE SCIPpatternAddElement(SCIP_PATTERN *pattern, int type, SCIP_Real x, SCIP_Real y)
void SCIPpatternSetPackableStatus(SCIP_PATTERN *pattern, SCIP_PACKABLE packable)
SCIP_RETCODE SCIPpatternCreateRectangular(SCIP *scip, SCIP_PATTERN **pattern)
void SCIPpatternRelease(SCIP *scip, SCIP_PATTERN **pattern)
pattern data for ringpacking problem
@ SCIP_PATTERNTYPE_RECTANGULAR
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)
static SCIP_RETCODE addVariable(SCIP *scip, SCIP_PROBDATA *probdata, int *types, SCIP_Real *xs, SCIP_Real *ys, SCIP_Bool *ispacked, int nelems)
#define DEFAULT_PRICING_HEURTILIM
#define DEFAULT_PRICING_NLPNODELIM
static SCIP_RETCODE solvePricingHeuristic(SCIP *scip, SCIP_PROBDATA *probdata, SCIP_PRICERDATA *pricerdata, SCIP_Real *lambdas, SCIP_Real timelim, int iterlim, SCIP_Bool *addedvar)
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)
#define DEFAULT_PRICING_NLPTILIM
static SCIP_Real getDensityUb(int n)
SCIP_RETCODE SCIPpricerRpaActivate(SCIP *scip)
SCIP_RETCODE SCIPincludePricerRpa(SCIP *scip)
#define DEFAULT_PRICING_TOTALTILIM
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)
static int getNCircles(SCIP *scip, SCIP_Real rext, int demand, SCIP_Real width, SCIP_Real height, SCIP_Real lambda)
#define DEFAULT_PRICING_HEURITERLIM
Ringpacking variable pricer.
SCIP_Real SCIPprobdataGetHeight(SCIP_PROBDATA *probdata)
SCIP_Bool SCIPprobdataIsDualboundInvalid(SCIP_PROBDATA *probdata)
int * SCIPprobdataGetDemands(SCIP_PROBDATA *probdata)
int SCIPprobdataGetNTypes(SCIP_PROBDATA *probdata)
SCIP_RETCODE SCIPprobdataAddVar(SCIP *scip, SCIP_PROBDATA *probdata, SCIP_PATTERN *pattern, SCIP_VAR *var)
SCIP_Real * SCIPprobdataGetRexts(SCIP_PROBDATA *probdata)
SCIP_CONS ** SCIPprobdataGetPatternConss(SCIP_PROBDATA *probdata)
void SCIPprobdataUpdateDualbound(SCIP *scip, SCIP_PROBDATA *probdata, SCIP_Real dualbound)
void SCIPprobdataInvalidateDualbound(SCIP *scip, SCIP_PROBDATA *probdata)
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)
SCIP_Real SCIPprobdataGetWidth(SCIP_PROBDATA *probdata)
Problem data for ringpacking problem.
SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip)
@ SCIP_PARAMSETTING_AGGRESSIVE
#define SCIP_DECL_PRICERFREE(x)
#define SCIP_DECL_PRICERINIT(x)
#define SCIP_DECL_PRICERREDCOST(x)
#define SCIP_DECL_PRICEREXIT(x)
#define SCIP_DECL_PRICERFARKAS(x)
struct SCIP_PricerData SCIP_PRICERDATA
struct SCIP_ProbData SCIP_PROBDATA
enum SCIP_Retcode SCIP_RETCODE
enum SCIP_Status SCIP_STATUS
@ SCIP_VARTYPE_CONTINUOUS