pricer_binpacking.c
Go to the documentation of this file.
21 * This file implements the variable pricer which check if variables exist with negative reduced cost. See
26 * The task of the pricer is to search for new variables with negative reduced costs. For this, the following integer
39 * where \f$ (\lambda_S)_i \f$ for \f$i\in\{1,\dots,n\}\f$ are binary variables and \f$y^\star_i\f$ given by the dual
40 * solution of the restricted master problem. See the \ref BINPACKING_PROBLEM "problem description" for more details.
42 * To solve the above integer program, we create a new SCIP instance within SCIP and use the usual functions to create
43 * variables and constraints. Besides, we need the current dual solutions to all set covering constraints (each stands
44 * for one item) which are the objective coefficients of the binary variables. Therefore, we use the function
47 * Since we also want to generate new variables during search, we have to care that we do not generate variables over
48 * and over again. For example, if we branched or fixed a certain packing to zero, we have to make sure that we do not
49 * generate the corresponding variables at that node again. For this, we have to add constraints forbidding to generate
50 * variables which are locally fixed to zero. See the function addFixedVarsConss() for more details. While using the
51 * \ref BINPACKING_BRANCHING "Ryan/Foster branching", we also have to ensure that these branching decisions are respected. This is
54 * @note In case of this binpacking example, the master LP should not get infeasible after branching, because of the way
56 * 1. In case of Ryan/Foster branching, the two items are selected in a way such that the sum of the LP values of
57 * all columns/packings containing both items is fractional. Hence, it exists at least one column/packing which
58 * contains both items and also at least one column/packing for each item containing this but not the other
59 * item. That means, branching in the "same" direction stays LP feasible since there exists at least one
60 * column/packing with both items and branching in the "differ" direction stays LP feasible since there exists
62 * 2. In case of variable branching, we only branch on fractional variables. If a variable is fixed to one, there
63 * is no issue. If a variable is fixed to zero, then we know that for each item which is part of that
64 * column/packing, there exists at least one other column/packing containing this particular item due to the
68 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
92 #define PRICER_DELAY TRUE /* only call pricer if all problem variables have non-negative reduced costs */
149 /* loop over all branching decision constraints and apply the branching decision if the corresponding constraint is
156 /* ignore constraints which are not active since these are not laying on the current active path of the search
162 /* collect the two item ids and the branching type (SAME or DIFFER) on which the constraint branched */
168 SCIPprobdataGetIds(SCIPgetProbData(scip))[id1], SCIPprobdataGetIds(SCIPgetProbData(scip))[id2]);
170 /* depending on the branching type select the correct left and right hand side for the linear constraint which
191 /* add linear (in that case a variable bound) constraint to pricing MIP depending on the branching type:
197 * note a setppc constraint would be sufficient and even better suitable for such kind of constraint
211 /** avoid to generate columns which are fixed to zero; therefore add for each variable which is fixed to zero a
214 * @note variable which are fixed locally to zero should not be generated again by the pricing MIP
253 /* if the upper bound is smaller than 0.5 if follows due to the integrality that the binary variable is fixed to zero */
271 /* loop over these items and create a linear (logicor) constraint which forbids this item combination in the
313 SCIP_CALL( SCIPcreateConsBasicLogicor(subscip, &cons, SCIPvarGetName(origvars[v]), nlogicorvars, logicorvars) );
383 SCIP_CALL( SCIPcreateVarBasic(subscip, &var, SCIPconsGetName(cons), 0.0, 1.0, dual, SCIP_VARTYPE_BINARY) );
395 SCIP_CALL( SCIPcreateConsBasicKnapsack(subscip, &cons, "capacity", nvars, vars, vals, capacity) );
476 /** solving process deinitialization method of variable pricer (called before branch and bound process data is freed) */
576 /* loop over all solutions and create the corresponding column to master if the reduced cost are negative for master,
585 assert(s == 0 || SCIPisFeasGE(subscip, SCIPgetSolOrigObj(subscip, sols[s-1]), SCIPgetSolOrigObj(subscip, sols[s])));
595 SCIPwarningMessage(scip, "solution in pricing problem (capacity <%d>) is infeasible\n", capacity);
649 /* change the upper bound of the binary variable to lazy since the upper bound is already enforced due to
650 * the objective function the set covering constraint; The reason for doing is that, is to avoid the bound
651 * of x <= 1 in the LP relaxation since this bound constraint would produce a dual variable which might have
689 /** @note In case of this binpacking example, the master LP should not get infeasible after branching, because of the
691 * 1. In case of Ryan/Foster branching, the two items are selected in a way such that the sum of the LP values
693 * column/packing which contains both items and also at least one column/packing for each item containing
694 * this but not the other item. That means, branching in the "same" direction stays LP feasible since there
695 * exists at least one column/packing with both items and branching in the "differ" direction stays LP
696 * feasible since there exists at least one column/packing containing one item, but not the other.
697 * 2. In case of variable branching, we only branch on fractional variables. If a variable is fixed to one,
698 * there is no issue. If a variable is fixed to zero, then we know that for each item which is part of
699 * that column/packing, there exists at least one other column/packing containing this particular item due
702 SCIPwarningMessage(scip, "Current master LP is infeasible, but Farkas pricing was not implemented\n");
737 SCIP_CALL( SCIPincludePricerBasic(scip, &pricer, PRICER_NAME, PRICER_DESC, PRICER_PRIORITY, PRICER_DELAY,
SCIP_RETCODE SCIPpricerBinpackingActivate(SCIP *scip, SCIP_CONS **conss, SCIP_Longint *weights, int *ids, int nitems, SCIP_Longint capacity)
Definition: pricer_binpacking.c:752
Definition: type_result.h:33
static SCIP_RETCODE addFixedVarsConss(SCIP *scip, SCIP *subscip, SCIP_VAR **vars, SCIP_CONS **conss, int nitems)
Definition: pricer_binpacking.c:217
static SCIP_DECL_PRICEREXITSOL(pricerExitsolBinpacking)
Definition: pricer_binpacking.c:478
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:851
SCIP_RETCODE SCIPaddCoefSetppc(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition: cons_setppc.c:9227
Definition: struct_scip.h:58
Constraint handler for variable bound constraints .
int SCIPgetNFixedonesSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9383
Definition: type_prob.h:38
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:954
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:379
Definition: type_result.h:49
SCIP_RETCODE SCIPincludePricerBinpacking(SCIP *scip)
Definition: pricer_binpacking.c:717
Definition: struct_var.h:198
SCIP_RETCODE SCIPchgVarUbLazy(SCIP *scip, SCIP_VAR *var, SCIP_Real lazyub)
Definition: scip_var.c:5086
Constraint handler stores the local branching decision data.
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:903
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4563
Binpacking variable pricer.
SCIP_PRICER * SCIPfindPricer(SCIP *scip, const char *name)
Definition: scip_pricer.c:381
Definition: type_var.h:53
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:184
Variable data containing the ids of constraints in which the variable appears.
SCIP_RETCODE SCIPsetPricerExitsol(SCIP *scip, SCIP_PRICER *pricer, SCIP_DECL_PRICEREXITSOL((*pricerexitsol)))
Definition: scip_pricer.c:365
Constraint handler for the set partitioning / packing / covering constraints .
int * SCIPvardataGetConsids(SCIP_VARDATA *vardata)
Definition: vardata_binpacking.c:124
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
Definition: scip_param.c:694
Definition: struct_pricer.h:37
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:203
SCIP_RETCODE SCIPcreateProbBasic(SCIP *scip, const char *name)
Definition: scip_prob.c:223
static SCIP_DECL_PRICERINIT(pricerInitBinpacking)
Definition: pricer_binpacking.c:445
Definition: struct_sol.h:63
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:111
SCIP_RETCODE SCIPsetObjsense(SCIP *scip, SCIP_OBJSENSE objsense)
Definition: scip_prob.c:1298
Constraint handler for knapsack constraints of the form , x binary and .
SCIP_RETCODE SCIPcreateVarBinpacking(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real obj, SCIP_Bool initial, SCIP_Bool removable, SCIP_VARDATA *vardata)
Definition: vardata_binpacking.c:142
static SCIP_DECL_PRICERFARKAS(pricerFarkasBinpacking)
Definition: pricer_binpacking.c:686
Definition: struct_cons.h:37
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:197
Definition: struct_cons.h:117
SCIP_Real SCIPgetDualsolSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9312
SCIP_RETCODE SCIPdelConsLocal(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:3527
Constraint handler for logicor constraints (equivalent to set covering, but algorithms are suited fo...
Definition: type_stat.h:52
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip_param.c:520
int SCIPgetItemid2Samediff(SCIP *scip, SCIP_CONS *cons)
Definition: cons_samediff.c:604
SCIP_RETCODE SCIPcheckSolOrig(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *feasible, SCIP_Bool printreason, SCIP_Bool completely)
Definition: scip_sol.c:3533
static SCIP_DECL_PRICERFREE(pricerFreeBinpacking)
Definition: pricer_binpacking.c:420
SCIP_RETCODE SCIPcreateConsBasicLogicor(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars)
Definition: cons_logicor.c:5242
Definition: type_retcode.h:33
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:890
SCIP_RETCODE SCIPsetPricerInit(SCIP *scip, SCIP_PRICER *pricer, SCIP_DECL_PRICERINIT((*pricerinit)))
Definition: scip_pricer.c:293
SCIP_RETCODE SCIPgetTransformedCons(SCIP *scip, SCIP_CONS *cons, SCIP_CONS **transcons)
Definition: scip_cons.c:1688
SCIP_RETCODE SCIPcreateConsBasicKnapsack(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Longint *weights, SCIP_Longint capacity)
Definition: cons_knapsack.c:13547
SCIP_RETCODE SCIPcaptureCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_cons.c:1152
SCIP_RETCODE SCIPvardataCreateBinpacking(SCIP *scip, SCIP_VARDATA **vardata, int *consids, int nconsids)
Definition: vardata_binpacking.c:103
int * SCIPprobdataGetIds(SCIP_PROBDATA *probdata)
Definition: probdata_binpacking.c:431
SCIP_RETCODE SCIPactivatePricer(SCIP *scip, SCIP_PRICER *pricer)
Definition: scip_pricer.c:454
SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip)
Definition: scipdefplugins.c:27
Definition: cons_samediff.h:37
Problem data for binpacking problem.
CONSTYPE SCIPgetTypeSamediff(SCIP *scip, SCIP_CONS *cons)
Definition: cons_samediff.c:620
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:578
SCIP_RETCODE SCIPsetPricerFree(SCIP *scip, SCIP_PRICER *pricer, SCIP_DECL_PRICERFREE((*pricerfree)))
Definition: scip_pricer.c:269
SCIP_RETCODE SCIPcreateConsBasicVarbound(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *var, SCIP_VAR *vbdvar, SCIP_Real vbdcoef, SCIP_Real lhs, SCIP_Real rhs)
Definition: cons_varbound.c:4869
int SCIPgetItemid1Samediff(SCIP *scip, SCIP_CONS *cons)
Definition: cons_samediff.c:588
Definition: cons_samediff.h:38
Definition: type_set.h:36
SCIP_RETCODE SCIPaddPricedVar(SCIP *scip, SCIP_VAR *var, SCIP_Real score)
Definition: scip_prob.c:1789
static SCIP_RETCODE addBranchingDecisionConss(SCIP *scip, SCIP *subscip, SCIP_VAR **vars, SCIP_CONSHDLR *conshdlr)
Definition: pricer_binpacking.c:121
static SCIP_DECL_PRICERREDCOST(pricerRedcostBinpacking)
Definition: pricer_binpacking.c:502
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1187
int SCIPvardataGetNConsids(SCIP_VARDATA *vardata)
Definition: vardata_binpacking.c:116
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:117
static SCIP_RETCODE initPricing(SCIP *scip, SCIP_PRICERDATA *pricerdata, SCIP *subscip, SCIP_VAR **vars)
Definition: pricer_binpacking.c:329
Definition: type_retcode.h:43
Definition: objbenders.h:33
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1410
default SCIP plugins
SCIP_RETCODE SCIPprintVar(SCIP *scip, SCIP_VAR *var, FILE *file)
Definition: scip_var.c:9684
SCIP_RETCODE SCIPgetNegatedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **negvar)
Definition: scip_var.c:1530
SCIP_RETCODE SCIPsetConsInitial(SCIP *scip, SCIP_CONS *cons, SCIP_Bool initial)
Definition: scip_cons.c:1285
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip_sol.c:1824