# SCIP

Solving Constraint Integer Programs

pricer_binpacking.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
7 /* fuer Informationstechnik Berlin */
8 /* */
10 /* */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file pricer_binpacking.c
17  * @brief Binpacking variable pricer
18  * @author Timo Berthold
19  * @author Stefan Heinz
20  *
21  * This file implements the variable pricer which check if variables exist with negative reduced cost. See
22  * @ref BINPACKING_PRICER for more details.
23  *
24  * @page BINPACKING_PRICER Pricing new variables
25  *
26  * The task of the pricer is to search for new variables with negative reduced costs. For this, the following integer
27  * program is solved:
28  *
29  * \f[
30  * \begin{array}[t]{rll}
31  * \max & \displaystyle \sum_{i=1}^n (\lambda_S)_i y^\star_i\\
32  * & \\
33  * subject \ to & \displaystyle \sum_{i=0}^n (\lambda_S)_i s_i \leq \kappa \\
34  * & \\
35  * & (\lambda_S)_i \in \{0,1\} & \quad \forall i \in \{ 1, \dots , n \} \\
36  * \end{array}
37  * \f]
38  *
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.
41  *
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
45  * SCIPgetDualsolSetppc() which returns the dual solutions for the given set covering constraint.
46  *
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
52  * realized within the function addBranchingDecisionConss().
53  *
54  * @note In case of this binpacking example, the master LP should not get infeasible after branching, because of the way
55  * branching is performed. Therefore, the Farkas pricing is not implemented.
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
61  * at least one column/packing containing one item, but not the other.
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
65  * covering constraints.
66  */
67
68 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
69
70 #include <assert.h>
71 #include <string.h>
72
73 #include "scip/cons_knapsack.h"
74 #include "scip/cons_logicor.h"
75 #include "scip/cons_setppc.h"
76 #include "scip/cons_varbound.h"
77 #include "scip/scipdefplugins.h"
78
79 #include "cons_samediff.h"
80 #include "pricer_binpacking.h"
81 #include "probdata_binpacking.h"
82 #include "vardata_binpacking.h"
83
84 /**@name Pricer properties
85  *
86  * @{
87  */
88
89 #define PRICER_NAME "binpacking"
90 #define PRICER_DESC "pricer for binpacking tours"
91 #define PRICER_PRIORITY 0
92 #define PRICER_DELAY TRUE /* only call pricer if all problem variables have non-negative reduced costs */
93
94 /**@} */
95
96
97 /*
98  * Data structures
99  */
100
101 /** @brief Variable pricer data used in the \ref pricer_binpacking.c "pricer" */
102 struct SCIP_PricerData
103 {
104  SCIP_CONSHDLR* conshdlr; /**< comstraint handler for "same" and "diff" constraints */
105  SCIP_CONS** conss; /**< set covering constraints for the items */
106  SCIP_Longint* weights; /**< weight of the items */
107  int* ids; /**< array of item ids */
108  int nitems; /**< number of items to be packed */
109  SCIP_Longint capacity; /**< capacity of the bins */
110 };
111
112
113
114 /**@name Local methods
115  *
116  * @{
117  */
118
119 /** add branching decisions constraints to the sub SCIP */
120 static
122  SCIP* scip, /**< SCIP data structure */
123  SCIP* subscip, /**< pricing SCIP data structure */
124  SCIP_VAR** vars, /**< variable array of the subscuip oder variables */
125  SCIP_CONSHDLR* conshdlr /**< constraint handler for branching data */
126  )
127 {
128  SCIP_CONS** conss;
129  SCIP_CONS* cons;
130  int nconss;
131  int id1;
132  int id2;
133  CONSTYPE type;
134
135  SCIP_Real vbdcoef;
136  SCIP_Real lhs;
137  SCIP_Real rhs;
138
139  int c;
140
141  assert( scip != NULL );
142  assert( subscip != NULL );
143  assert( conshdlr != NULL );
144
145  /* collect all branching decision constraints */
146  conss = SCIPconshdlrGetConss(conshdlr);
147  nconss = SCIPconshdlrGetNConss(conshdlr);
148
149  /* loop over all branching decision constraints and apply the branching decision if the corresponding constraint is
150  * active
151  */
152  for( c = 0; c < nconss; ++c )
153  {
154  cons = conss[c];
155
156  /* ignore constraints which are not active since these are not laying on the current active path of the search
157  * tree
158  */
159  if( !SCIPconsIsActive(cons) )
160  continue;
161
162  /* collect the two item ids and the branching type (SAME or DIFFER) on which the constraint branched */
163  id1 = SCIPgetItemid1Samediff(scip, cons);
164  id2 = SCIPgetItemid2Samediff(scip, cons);
165  type = SCIPgetTypeSamediff(scip, cons);
166
167  SCIPdebugMsg(scip, "create varbound for %s(%d,%d)\n", type == SAME ? "same" : "diff",
169
170  /* depending on the branching type select the correct left and right hand side for the linear constraint which
171  * enforces this branching decision in the pricing problem MIP
172  */
173  if( type == SAME )
174  {
175  lhs = 0.0;
176  rhs = 0.0;
177  vbdcoef = -1.0;
178  }
179  else if( type == DIFFER )
180  {
181  lhs = -SCIPinfinity(scip);
182  rhs = 1.0;
183  vbdcoef = 1.0;
184  }
185  else
186  {
187  SCIPerrorMessage("unknow constraint type <%d>\n, type");
188  return SCIP_INVALIDDATA;
189  }
190
191  /* add linear (in that case a variable bound) constraint to pricing MIP depending on the branching type:
192  *
193  * - branching type SAME: x1 = x2 <=> x1 - x2 = 0 <=> 0 <= x1 - x2 <= 0
194  *
195  * - branching type DIFFER: x1 + x2 <= 1 <=> -inf <= x1 + x2 <= 1
196  *
197  * note a setppc constraint would be sufficient and even better suitable for such kind of constraint
198  */
199  SCIP_CALL( SCIPcreateConsBasicVarbound(subscip, &cons, SCIPconsGetName(conss[c]),
200  vars[id1], vars[id2], vbdcoef, lhs, rhs) );
201
202  SCIPdebugPrintCons(subscip, cons, NULL);
203
205  SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
206  }
207
208  return SCIP_OKAY;
209 }
210
211 /** avoid to generate columns which are fixed to zero; therefore add for each variable which is fixed to zero a
212  * corresponding logicor constraint to forbid this column
213  *
214  * @note variable which are fixed locally to zero should not be generated again by the pricing MIP
215  */
216 static
218  SCIP* scip, /**< SCIP data structure */
219  SCIP* subscip, /**< pricing SCIP data structure */
220  SCIP_VAR** vars, /**< variable array of the subscuip */
221  SCIP_CONS** conss, /**< array of setppc constraint for each item one */
222  int nitems /**< number of items */
223  )
224 {
225  SCIP_VAR** origvars;
226  int norigvars;
227
228  SCIP_CONS* cons;
229  int* consids;
230  int nconsids;
231  int consid;
232  int nvars;
233
234  SCIP_VAR** logicorvars;
235  SCIP_VAR* var;
236  SCIP_VARDATA* vardata;
237  SCIP_Bool needed;
238  int nlogicorvars;
239
240  int v;
241  int c;
242  int o;
243
244  /* collect all variable which are currently existing */
245  origvars = SCIPgetVars(scip);
246  norigvars = SCIPgetNVars(scip);
247
248  /* loop over all these variables and check if they are fixed to zero */
249  for( v = 0; v < norigvars; ++v )
250  {
251  assert(SCIPvarGetType(origvars[v]) == SCIP_VARTYPE_BINARY);
252
253  /* if the upper bound is smaller than 0.5 if follows due to the integrality that the binary variable is fixed to zero */
254  if( SCIPvarGetUbLocal(origvars[v]) < 0.5 )
255  {
256  SCIPdebugMsg(scip, "variable <%s> glb=[%.15g,%.15g] loc=[%.15g,%.15g] is fixed to zero\n",
257  SCIPvarGetName(origvars[v]), SCIPvarGetLbGlobal(origvars[v]), SCIPvarGetUbGlobal(origvars[v]),
258  SCIPvarGetLbLocal(origvars[v]), SCIPvarGetUbLocal(origvars[v]) );
259
260  /* coolect the constraints/items the variable belongs to */
261  vardata = SCIPvarGetData(origvars[v]);
262  nconsids = SCIPvardataGetNConsids(vardata);
263  consids = SCIPvardataGetConsids(vardata);
264  needed = TRUE;
265
266  SCIP_CALL( SCIPallocBufferArray(subscip, &logicorvars, nitems) );
267  nlogicorvars = 0;
268  consid = consids[0];
269  nvars = 0;
270
271  /* loop over these items and create a linear (logicor) constraint which forbids this item combination in the
272  * pricing problem; thereby check if this item combination is already forbidden
273  */
274  for( c = 0, o = 0; o < nitems && needed; ++o )
275  {
276  assert(o <= consid);
277  cons = conss[o];
278
279  if( SCIPconsIsEnabled(cons) )
280  {
281  assert( SCIPgetNFixedonesSetppc(scip, cons) == 0 );
282
283  var = vars[nvars];
284  nvars++;
285  assert(var != NULL);
286
287  if( o == consid )
288  {
289  SCIP_CALL( SCIPgetNegatedVar(subscip, var, &var) );
290  }
291
292  logicorvars[nlogicorvars] = var;
293  nlogicorvars++;
294  }
295  else if( o == consid )
296  needed = FALSE;
297
298  if( o == consid )
299  {
300  c++;
301  if ( c == nconsids )
302  consid = nitems + 100;
303  else
304  {
305  assert(consid < consids[c]);
306  consid = consids[c];
307  }
308  }
309  }
310
311  if( needed )
312  {
313  SCIP_CALL( SCIPcreateConsBasicLogicor(subscip, &cons, SCIPvarGetName(origvars[v]), nlogicorvars, logicorvars) );
314  SCIP_CALL( SCIPsetConsInitial(subscip, cons, FALSE) );
315
317  SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
318  }
319
320  SCIPfreeBufferArray(subscip, &logicorvars);
321  }
322  }
323
324  return SCIP_OKAY;
325 }
326
327 /** initializes the pricing problem for the given capacity */
328 static
330  SCIP* scip, /**< SCIP data structure */
331  SCIP_PRICERDATA* pricerdata, /**< pricer data */
332  SCIP* subscip, /**< pricing SCIP data structure */
333  SCIP_VAR** vars /**< variable array for the items */
334  )
335 {
336  SCIP_CONS** conss;
337  SCIP_Longint* vals;
338  SCIP_CONS* cons;
339  SCIP_VAR* var;
340  SCIP_Longint* weights;
341  SCIP_Longint capacity;
342  SCIP_Real dual;
343
344  int nitems;
345  int nvars;
346  int c;
347
348  assert( SCIPgetStage(subscip) == SCIP_STAGE_PROBLEM );
349  assert(pricerdata != NULL);
350
351  nitems = pricerdata->nitems;
352  conss = pricerdata->conss;
353  weights = pricerdata->weights;
354  capacity = pricerdata->capacity;
355  nvars = 0;
356
357  SCIP_CALL( SCIPallocBufferArray(subscip, &vals, nitems) );
358
359  /* create for each order, which is not assigned yet, a variable with objective coefficient */
360  for( c = 0; c < nitems; ++c )
361  {
362  cons = conss[c];
363
364  /* check if each constraint is setppc constraint */
365  assert( !strncmp( SCIPconshdlrGetName( SCIPconsGetHdlr(cons) ), "setppc", 6) );
366
367  /* constraints which are (locally) disabled/redundant are not of
368  * interest since the corresponding job is assigned to a packing
369  */
370  if( !SCIPconsIsEnabled(cons) )
371  continue;
372
373  if( SCIPgetNFixedonesSetppc(scip, cons) == 1 )
374  {
375  /* disable constraint locally */
376  SCIP_CALL( SCIPdelConsLocal(scip, cons) );
377  continue;
378  }
379
380  /* dual value in original SCIP */
381  dual = SCIPgetDualsolSetppc(scip, cons);
382
383  SCIP_CALL( SCIPcreateVarBasic(subscip, &var, SCIPconsGetName(cons), 0.0, 1.0, dual, SCIP_VARTYPE_BINARY) );
385
386  vals[nvars] = weights[c];
387  vars[nvars] = var;
388  nvars++;
389
390  /* release variable */
391  SCIP_CALL( SCIPreleaseVar(subscip, &var) );
392  }
393
394  /* create capacity constraint */
395  SCIP_CALL( SCIPcreateConsBasicKnapsack(subscip, &cons, "capacity", nvars, vars, vals, capacity) );
396
398  SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
399
400  /* add constraint of the branching decisions */
401  SCIP_CALL( addBranchingDecisionConss(scip, subscip, vars, pricerdata->conshdlr) );
402
403  /* avoid to generate columns which are fixed to zero */
404  SCIP_CALL( addFixedVarsConss(scip, subscip, vars, conss, nitems) );
405
406  SCIPfreeBufferArray(subscip, &vals);
407
408  return SCIP_OKAY;
409 }
410
411 /**@} */
412
413 /**name Callback methods
414  *
415  * @{
416  */
417
418 /** destructor of variable pricer to free user data (called when SCIP is exiting) */
419 static
420 SCIP_DECL_PRICERFREE(pricerFreeBinpacking)
421 {
422  SCIP_PRICERDATA* pricerdata;
423
424  assert(scip != NULL);
425  assert(pricer != NULL);
426
427  pricerdata = SCIPpricerGetData(pricer);
428
429  if( pricerdata != NULL)
430  {
431  /* free memory */
432  SCIPfreeBlockMemoryArrayNull(scip, &pricerdata->conss, pricerdata->nitems);
433  SCIPfreeBlockMemoryArrayNull(scip, &pricerdata->weights, pricerdata->nitems);
434  SCIPfreeBlockMemoryArrayNull(scip, &pricerdata->ids, pricerdata->nitems);
435
436  SCIPfreeBlockMemory(scip, &pricerdata);
437  }
438
439  return SCIP_OKAY;
440 }
441
442
443 /** initialization method of variable pricer (called after problem was transformed) */
444 static
445 SCIP_DECL_PRICERINIT(pricerInitBinpacking)
446 { /*lint --e{715}*/
447  SCIP_PRICERDATA* pricerdata;
448  SCIP_CONS* cons;
449  int c;
450
451  assert(scip != NULL);
452  assert(pricer != NULL);
453
454  pricerdata = SCIPpricerGetData(pricer);
455  assert(pricerdata != NULL);
456
457  /* get transformed constraints */
458  for( c = 0; c < pricerdata->nitems; ++c )
459  {
460  cons = pricerdata->conss[c];
461
462  /* release original constraint */
463  SCIP_CALL( SCIPreleaseCons(scip, &pricerdata->conss[c]) );
464
465  /* get transformed constraint */
466  SCIP_CALL( SCIPgetTransformedCons(scip, cons, &pricerdata->conss[c]) );
467
468  /* capture transformed constraint */
469  SCIP_CALL( SCIPcaptureCons(scip, pricerdata->conss[c]) );
470  }
471
472  return SCIP_OKAY;
473 }
474
475
476 /** solving process deinitialization method of variable pricer (called before branch and bound process data is freed) */
477 static
478 SCIP_DECL_PRICEREXITSOL(pricerExitsolBinpacking)
479 {
480  SCIP_PRICERDATA* pricerdata;
481  int c;
482
483  assert(scip != NULL);
484  assert(pricer != NULL);
485
486  pricerdata = SCIPpricerGetData(pricer);
487  assert(pricerdata != NULL);
488
489  /* get release constraints */
490  for( c = 0; c < pricerdata->nitems; ++c )
491  {
492  /* release constraint */
493  SCIP_CALL( SCIPreleaseCons(scip, &(pricerdata->conss[c])) );
494  }
495
496  return SCIP_OKAY;
497 }
498
499
500 /** reduced cost pricing method of variable pricer for feasible LPs */
501 static
502 SCIP_DECL_PRICERREDCOST(pricerRedcostBinpacking)
503 { /*lint --e{715}*/
504  SCIP* subscip;
505  SCIP_PRICERDATA* pricerdata;
506  SCIP_CONS** conss;
507  SCIP_VAR** vars;
508  int* ids;
510
511  SCIP_SOL** sols;
512  int nsols;
513  int s;
514
515  int nitems;
516  SCIP_Longint capacity;
517
518  SCIP_Real timelimit;
519  SCIP_Real memorylimit;
520
521  assert(scip != NULL);
522  assert(pricer != NULL);
523
524  (*result) = SCIP_DIDNOTRUN;
525
526  /* get the pricer data */
527  pricerdata = SCIPpricerGetData(pricer);
528  assert(pricerdata != NULL);
529
530  capacity = pricerdata->capacity;
531  conss = pricerdata->conss;
532  ids = pricerdata->ids;
533  nitems = pricerdata->nitems;
534
535  /* get the remaining time and memory limit */
536  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
537  if( !SCIPisInfinity(scip, timelimit) )
538  timelimit -= SCIPgetSolvingTime(scip);
539  SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memorylimit) );
540  if( !SCIPisInfinity(scip, memorylimit) )
541  memorylimit -= SCIPgetMemUsed(scip)/1048576.0;
542
543  /* initialize SCIP */
544  SCIP_CALL( SCIPcreate(&subscip) );
546
547  /* create problem in sub SCIP */
548  SCIP_CALL( SCIPcreateProbBasic(subscip, "pricing") );
550
551  /* do not abort subproblem on CTRL-C */
552  SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
553
554  /* disable output to console */
555  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
556
557  /* set time and memory limit */
558  SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", timelimit) );
559  SCIP_CALL( SCIPsetRealParam(subscip, "limits/memory", memorylimit) );
560
561  /* allocate in orginal scip, since otherwise the buffer counts in subscip are not correct */
562  SCIP_CALL( SCIPallocBufferArray(scip, &vars, nitems) );
563
564  /* initialization local pricing problem */
565  SCIP_CALL( initPricing(scip, pricerdata, subscip, vars) );
566
567  SCIPdebugMsg(scip, "solve pricer problem\n");
568
569  /* solve sub SCIP */
570  SCIP_CALL( SCIPsolve(subscip) );
571
572  sols = SCIPgetSols(subscip);
573  nsols = SCIPgetNSols(subscip);
575
576  /* loop over all solutions and create the corresponding column to master if the reduced cost are negative for master,
577  * that is the objective value i greater than 1.0
578  */
579  for( s = 0; s < nsols; ++s )
580  {
581  SCIP_Bool feasible;
582  SCIP_SOL* sol;
583
584  /* the soultion should be sorted w.r.t. the objective function value */
585  assert(s == 0 || SCIPisFeasGE(subscip, SCIPgetSolOrigObj(subscip, sols[s-1]), SCIPgetSolOrigObj(subscip, sols[s])));
586
587  sol = sols[s];
588  assert(sol != NULL);
589
590  /* check if solution is feasible in original sub SCIP */
591  SCIP_CALL( SCIPcheckSolOrig(subscip, sol, &feasible, FALSE, FALSE ) );
592
593  if( !feasible )
594  {
595  SCIPwarningMessage(scip, "solution in pricing problem (capacity <%d>) is infeasible\n", capacity);
596  continue;
597  }
598
599  /* check if the solution has a value greater than 1.0 */
600  if( SCIPisFeasGT(subscip, SCIPgetSolOrigObj(subscip, sol), 1.0) )
601  {
602  SCIP_VAR* var;
603  SCIP_VARDATA* vardata;
604  int* consids;
605  char strtmp[SCIP_MAXSTRLEN];
606  char name[SCIP_MAXSTRLEN];
607  int nconss;
608  int o;
609  int v;
610
611  SCIPdebug( SCIP_CALL( SCIPprintSol(subscip, sol, NULL, FALSE) ) );
612
613  nconss = 0;
614  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "items");
615
616  SCIP_CALL( SCIPallocBufferArray(scip, &consids, nitems) );
617
618  /* check which variables are fixed -> which item belongs to this packing */
619  for( o = 0, v = 0; o < nitems; ++o )
620  {
621  if( !SCIPconsIsEnabled(conss[o]) )
622  continue;
623
624  assert(SCIPgetNFixedonesSetppc(scip, conss[o]) == 0);
625
626  if( SCIPgetSolVal(subscip, sol, vars[v]) > 0.5 )
627  {
628  (void) SCIPsnprintf(strtmp, SCIP_MAXSTRLEN, "_%d", ids[o]);
629  strcat(name, strtmp);
630
631  consids[nconss] = o;
632  nconss++;
633  }
634  else
635  assert( SCIPisFeasEQ(subscip, SCIPgetSolVal(subscip, sol, vars[v]), 0.0) );
636
637  v++;
638  }
639
640  SCIP_CALL( SCIPvardataCreateBinpacking(scip, &vardata, consids, nconss) );
641
642  /* create variable for a new column with objective function coefficient 0.0 */
643  SCIP_CALL( SCIPcreateVarBinpacking(scip, &var, name, 1.0, FALSE, TRUE, vardata) );
644
645  /* add the new variable to the pricer store */
646  SCIP_CALL( SCIPaddPricedVar(scip, var, 1.0) );
648
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
652  * a positive reduced cost
653  */
654  SCIP_CALL( SCIPchgVarUbLazy(scip, var, 1.0) );
655
656  /* check which variable are fixed -> which orders belong to this packing */
657  for( v = 0; v < nconss; ++v )
658  {
659  assert(SCIPconsIsEnabled(conss[consids[v]]));
660  SCIP_CALL( SCIPaddCoefSetppc(scip, conss[consids[v]], var) );
661  }
662
663  SCIPdebug(SCIPprintVar(scip, var, NULL) );
664  SCIP_CALL( SCIPreleaseVar(scip, &var) );
665
666  SCIPfreeBufferArray(scip, &consids);
667  }
668  else
669  break;
670  }
671
672  /* free pricer MIP */
673  SCIPfreeBufferArray(scip, &vars);
674
675  if( addvar || SCIPgetStatus(subscip) == SCIP_STATUS_OPTIMAL )
676  (*result) = SCIP_SUCCESS;
677
678  /* free sub SCIP */
679  SCIP_CALL( SCIPfree(&subscip) );
680
681  return SCIP_OKAY;
682 }
683
684 /** farkas pricing method of variable pricer for infeasible LPs */
685 static
686 SCIP_DECL_PRICERFARKAS(pricerFarkasBinpacking)
687 { /*lint --e{715}*/
688
689  /** @note In case of this binpacking example, the master LP should not get infeasible after branching, because of the
690  * way branching is performed. Therefore, the Farkas pricing is not implemented.
691  * 1. In case of Ryan/Foster branching, the two items are selected in a way such that the sum of the LP values
692  * of all columns/packings containing both items is fractional. Hence, it exists at least one
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
700  * to the covering constraints.
701  */
702  SCIPwarningMessage(scip, "Current master LP is infeasible, but Farkas pricing was not implemented\n");
703  SCIPABORT();
704
705  return SCIP_OKAY; /*lint !e527*/
706 }
707
708 /**@} */
709
710
711 /**@name Interface methods
712  *
713  * @{
714  */
715
716 /** creates the binpacking variable pricer and includes it in SCIP */
718  SCIP* scip /**< SCIP data structure */
719  )
720 {
721  SCIP_PRICERDATA* pricerdata;
722  SCIP_PRICER* pricer;
723
724  /* create binpacking variable pricer data */
725  SCIP_CALL( SCIPallocBlockMemory(scip, &pricerdata) );
726
727  pricerdata->conshdlr = SCIPfindConshdlr(scip, "samediff");
728  assert(pricerdata->conshdlr != NULL);
729
730  pricerdata->conss = NULL;
731  pricerdata->weights = NULL;
732  pricerdata->ids = NULL;
733  pricerdata->nitems = 0;
734  pricerdata->capacity = 0;
735
736  /* include variable pricer */
738  pricerRedcostBinpacking, pricerFarkasBinpacking, pricerdata) );
739
740  SCIP_CALL( SCIPsetPricerFree(scip, pricer, pricerFreeBinpacking) );
741  SCIP_CALL( SCIPsetPricerInit(scip, pricer, pricerInitBinpacking) );
742  SCIP_CALL( SCIPsetPricerExitsol(scip, pricer, pricerExitsolBinpacking) );
743
744  /* add binpacking variable pricer parameters */
745  /* TODO: (optional) add variable pricer specific parameters with SCIPaddTypeParam() here */
746
747  return SCIP_OKAY;
748 }
749
750
751 /** added problem specific data to pricer and activates pricer */
753  SCIP* scip, /**< SCIP data structure */
754  SCIP_CONS** conss, /**< set covering constraints for the items */
755  SCIP_Longint* weights, /**< weight of the items */
756  int* ids, /**< array of item ids */
757  int nitems, /**< number of items to be packed */
758  SCIP_Longint capacity /**< capacity of the bins */
759  )
760 {
761  SCIP_PRICER* pricer;
762  SCIP_PRICERDATA* pricerdata;
763  int c;
764
765  assert(scip != NULL);
766  assert(conss != NULL);
767  assert(weights != NULL);
768  assert(nitems > 0);
769
770  pricer = SCIPfindPricer(scip, PRICER_NAME);
771  assert(pricer != NULL);
772
773  pricerdata = SCIPpricerGetData(pricer);
774  assert(pricerdata != NULL);
775
776  /* copy arrays */
777  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &pricerdata->conss, conss, nitems) );
778  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &pricerdata->weights, weights, nitems) );
779  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &pricerdata->ids, ids, nitems) );
780
781  pricerdata->nitems = nitems;
782  pricerdata->capacity = capacity;
783
784  SCIPdebugMsg(scip, " nitems: %d capacity: %"SCIP_LONGINT_FORMAT" \n", nitems, capacity);
785  SCIPdebugMsg(scip, " # profits weights x \n"); /* capture constraints */
786
787  /* capture all constraints */
788  for( c = 0; c < nitems; ++c )
789  {
790  SCIP_CALL( SCIPcaptureCons(scip, conss[c]) );
791  SCIPdebugMsgPrint(scip, "%4d %3"SCIP_LONGINT_FORMAT"\n", c, weights[c]);
792  }
793
794  /* activate pricer */
795  SCIP_CALL( SCIPactivatePricer(scip, pricer) );
796
797  return SCIP_OKAY;
798 }
799
800 /**@} */
SCIP_RETCODE SCIPpricerBinpackingActivate(SCIP *scip, SCIP_CONS **conss, SCIP_Longint *weights, int *ids, int nitems, SCIP_Longint capacity)
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip.c:45137
static SCIP_RETCODE addFixedVarsConss(SCIP *scip, SCIP *subscip, SCIP_VAR **vars, SCIP_CONS **conss, int nitems)
SCIP_Bool SCIPconsIsEnabled(SCIP_CONS *cons)
Definition: cons.c:7978
static SCIP_DECL_PRICEREXITSOL(pricerExitsolBinpacking)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46086
SCIP_RETCODE SCIPaddCoefSetppc(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition: cons_setppc.c:9149
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip.c:814
Constraint handler for variable bound constraints .
int SCIPgetNFixedonesSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9305
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip.c:6541
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17166
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip.c:4426
#define SCIP_MAXSTRLEN
Definition: def.h:215
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17222
SCIP_RETCODE SCIPincludePricerBinpacking(SCIP *scip)
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip.c:18384
SCIP_RETCODE SCIPchgVarUbLazy(SCIP *scip, SCIP_VAR *var, SCIP_Real lazyub)
Definition: scip.c:22084
Constraint handler stores the local branching decision data.
CONSTYPE
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46138
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4485
Binpacking variable pricer.
SCIP_SOL ** SCIPgetSols(SCIP *scip)
Definition: scip.c:38881
#define FALSE
Definition: def.h:64
struct SCIP_VarData SCIP_VARDATA
Definition: type_var.h:98
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:45816
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:9340
SCIP_PRICER * SCIPfindPricer(SCIP *scip, const char *name)
Definition: scip.c:5618
#define TRUE
Definition: def.h:63
#define SCIPdebug(x)
Definition: pub_message.h:74
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.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.c:17317
SCIP_PRICERDATA * SCIPpricerGetData(SCIP_PRICER *pricer)
Definition: pricer.c:463
Variable data containing the ids of constraints in which the variable appears.
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:21907
SCIP_RETCODE SCIPsetPricerExitsol(SCIP *scip, SCIP_PRICER *pricer, SCIP_DECL_PRICEREXITSOL((*pricerexitsol)))
Definition: scip.c:5602
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:21937
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip.c:696
Constraint handler for the set partitioning / packing / covering constraints .
int * SCIPvardataGetConsids(SCIP_VARDATA *vardata)
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:21890
#define SCIPdebugPrintCons(x, y, z)
Definition: pub_message.h:83
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
Definition: scip.c:4741
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip.c:1260
#define SCIPdebugMsgPrint
Definition: scip.h:452
#define SCIPdebugMsg
Definition: scip.h:451
SCIP_Bool SCIPconsIsActive(SCIP_CONS *cons)
Definition: cons.c:7942
SCIP_RETCODE SCIPcreateProbBasic(SCIP *scip, const char *name)
Definition: scip.c:9839
static SCIP_DECL_PRICERINIT(pricerInitBinpacking)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17176
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip.h:21904
SCIP_RETCODE SCIPsetObjsense(SCIP *scip, SCIP_OBJSENSE objsense)
Definition: scip.c:10898
Constraint handler for knapsack constraints of the form , x binary and .
#define PRICER_PRIORITY
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip.c:15777
SCIP_RETCODE SCIPcreateVarBinpacking(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real obj, SCIP_Bool initial, SCIP_Bool removable, SCIP_VARDATA *vardata)
#define PRICER_DELAY
static SCIP_DECL_PRICERFARKAS(pricerFarkasBinpacking)
#define SCIPerrorMessage
Definition: pub_message.h:45
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4113
Definition: scip.c:12410
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.c:5434
SCIP_Real SCIPgetDualsolSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9234
SCIP_RETCODE SCIPdelConsLocal(SCIP *scip, SCIP_CONS *cons)
Definition: scip.c:13111
Constraint handler for logicor constraints (equivalent to set covering, but algorithms are suited fo...
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip.c:4567
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip.c:921
int SCIPgetItemid2Samediff(SCIP *scip, SCIP_CONS *cons)
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:7881
SCIP_RETCODE SCIPcheckSolOrig(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *feasible, SCIP_Bool printreason, SCIP_Bool completely)
Definition: scip.c:40086
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16552
static SCIP_DECL_PRICERFREE(pricerFreeBinpacking)
#define NULL
Definition: lpi_spx1.cpp:137
SCIP_RETCODE SCIPcreateConsBasicLogicor(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars)
#define SCIP_CALL(x)
Definition: def.h:306
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46125
SCIP_RETCODE SCIPsetPricerInit(SCIP *scip, SCIP_PRICER *pricer, SCIP_DECL_PRICERINIT((*pricerinit)))
Definition: scip.c:5530
SCIP_RETCODE SCIPgetTransformedCons(SCIP *scip, SCIP_CONS *cons, SCIP_CONS **transcons)
Definition: scip.c:27824
SCIP_RETCODE SCIPcreateConsBasicKnapsack(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Longint *weights, SCIP_Longint capacity)
SCIP_RETCODE SCIPcaptureCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip.c:27288
#define PRICER_DESC
int SCIPconshdlrGetNConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4515
SCIP_RETCODE SCIPvardataCreateBinpacking(SCIP *scip, SCIP_VARDATA **vardata, int *consids, int nconsids)
int * SCIPprobdataGetIds(SCIP_PROBDATA *probdata)
SCIP_RETCODE SCIPactivatePricer(SCIP *scip, SCIP_PRICER *pricer)
Definition: scip.c:5691
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:21925
#define SCIP_Bool
Definition: def.h:61
SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip)
Problem data for binpacking problem.
CONSTYPE SCIPgetTypeSamediff(SCIP *scip, SCIP_CONS *cons)
SCIP_VARDATA * SCIPvarGetData(SCIP_VAR *var)
Definition: var.c:16572
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition: cons.c:7901
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip.c:4625
SCIP_RETCODE SCIPsetPricerFree(SCIP *scip, SCIP_PRICER *pricer, SCIP_DECL_PRICERFREE((*pricerfree)))
Definition: scip.c:5506
int SCIPgetNSols(SCIP *scip)
Definition: scip.c:38832
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:38090
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)
int SCIPgetItemid1Samediff(SCIP *scip, SCIP_CONS *cons)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:45827
int SCIPgetNVars(SCIP *scip)
Definition: scip.c:11631
SCIP_RETCODE SCIPaddPricedVar(SCIP *scip, SCIP_VAR *var, SCIP_Real score)
Definition: scip.c:11376
static SCIP_RETCODE addBranchingDecisionConss(SCIP *scip, SCIP *subscip, SCIP_VAR **vars, SCIP_CONSHDLR *conshdlr)
SCIP_Longint SCIPgetMemUsed(SCIP *scip)
Definition: scip.c:45562
Definition: scip.c:11311
SCIP_PROBDATA * SCIPgetProbData(SCIP *scip)
Definition: scip.c:10621
static SCIP_DECL_PRICERREDCOST(pricerRedcostBinpacking)
#define PRICER_NAME
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip.c:27323
int SCIPvardataGetNConsids(SCIP_VARDATA *vardata)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip.c:11586
#define SCIP_Real
Definition: def.h:135
#define SCIP_Longint
Definition: def.h:120
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16717
struct SCIP_PricerData SCIP_PRICERDATA
Definition: type_pricer.h:36
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17232
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip.h:21910
static SCIP_RETCODE initPricing(SCIP *scip, SCIP_PRICERDATA *pricerdata, SCIP *subscip, SCIP_VAR **vars)
#define SCIPABORT()
Definition: def.h:278
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip.c:38007
default SCIP plugins
SCIP_RETCODE SCIPprintVar(SCIP *scip, SCIP_VAR *var, FILE *file)
Definition: scip.c:26664
SCIP_RETCODE SCIPgetNegatedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **negvar)
Definition: scip.c:18663
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip.c:774
SCIP_RETCODE SCIPsetConsInitial(SCIP *scip, SCIP_CONS *cons, SCIP_Bool initial)
Definition: scip.c:27421
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip.c:38421