Scippy

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 /* */
6 /* Copyright (C) 2002-2021 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
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 
204  SCIP_CALL( SCIPaddCons(subscip, cons) );
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 
316  SCIP_CALL( SCIPaddCons(subscip, cons) );
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) );
384  SCIP_CALL( SCIPaddVar(subscip, var) );
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 
397  SCIP_CALL( SCIPaddCons(subscip, cons) );
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;
509  SCIP_Bool addvar;
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);
574  addvar = FALSE;
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 <%" SCIP_LONGINT_FORMAT ">) 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) );
647  addvar = TRUE;
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  /** @note In case of this binpacking example, the master LP should not get infeasible after branching, because of the
689  * way branching is performed. Therefore, the Farkas pricing is not implemented.
690  * 1. In case of Ryan/Foster branching, the two items are selected in a way such that the sum of the LP values
691  * of all columns/packings containing both items is fractional. Hence, it exists at least one
692  * column/packing which contains both items and also at least one column/packing for each item containing
693  * this but not the other item. That means, branching in the "same" direction stays LP feasible since there
694  * exists at least one column/packing with both items and branching in the "differ" direction stays LP
695  * feasible since there exists at least one column/packing containing one item, but not the other.
696  * 2. In case of variable branching, we only branch on fractional variables. If a variable is fixed to one,
697  * there is no issue. If a variable is fixed to zero, then we know that for each item which is part of
698  * that column/packing, there exists at least one other column/packing containing this particular item due
699  * to the covering constraints.
700  */
701  SCIPwarningMessage(scip, "Current master LP is infeasible, but Farkas pricing was not implemented\n");
702  SCIPABORT();
703 
704  return SCIP_OKAY; /*lint !e527*/
705 }
706 
707 /**@} */
708 
709 
710 /**@name Interface methods
711  *
712  * @{
713  */
714 
715 /** creates the binpacking variable pricer and includes it in SCIP */
717  SCIP* scip /**< SCIP data structure */
718  )
719 {
720  SCIP_PRICERDATA* pricerdata;
721  SCIP_PRICER* pricer;
722 
723  /* create binpacking variable pricer data */
724  SCIP_CALL( SCIPallocBlockMemory(scip, &pricerdata) );
725 
726  pricerdata->conshdlr = SCIPfindConshdlr(scip, "samediff");
727  assert(pricerdata->conshdlr != NULL);
728 
729  pricerdata->conss = NULL;
730  pricerdata->weights = NULL;
731  pricerdata->ids = NULL;
732  pricerdata->nitems = 0;
733  pricerdata->capacity = 0;
734 
735  /* include variable pricer */
737  pricerRedcostBinpacking, pricerFarkasBinpacking, pricerdata) );
738 
739  SCIP_CALL( SCIPsetPricerFree(scip, pricer, pricerFreeBinpacking) );
740  SCIP_CALL( SCIPsetPricerInit(scip, pricer, pricerInitBinpacking) );
741  SCIP_CALL( SCIPsetPricerExitsol(scip, pricer, pricerExitsolBinpacking) );
742 
743  /* add binpacking variable pricer parameters */
744  /* TODO: (optional) add variable pricer specific parameters with SCIPaddTypeParam() here */
745 
746  return SCIP_OKAY;
747 }
748 
749 
750 /** added problem specific data to pricer and activates pricer */
752  SCIP* scip, /**< SCIP data structure */
753  SCIP_CONS** conss, /**< set covering constraints for the items */
754  SCIP_Longint* weights, /**< weight of the items */
755  int* ids, /**< array of item ids */
756  int nitems, /**< number of items to be packed */
757  SCIP_Longint capacity /**< capacity of the bins */
758  )
759 {
760  SCIP_PRICER* pricer;
761  SCIP_PRICERDATA* pricerdata;
762  int c;
763 
764  assert(scip != NULL);
765  assert(conss != NULL);
766  assert(weights != NULL);
767  assert(nitems > 0);
768 
769  pricer = SCIPfindPricer(scip, PRICER_NAME);
770  assert(pricer != NULL);
771 
772  pricerdata = SCIPpricerGetData(pricer);
773  assert(pricerdata != NULL);
774 
775  /* copy arrays */
776  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &pricerdata->conss, conss, nitems) );
777  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &pricerdata->weights, weights, nitems) );
778  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &pricerdata->ids, ids, nitems) );
779 
780  pricerdata->nitems = nitems;
781  pricerdata->capacity = capacity;
782 
783  SCIPdebugMsg(scip, " nitems: %d capacity: %"SCIP_LONGINT_FORMAT" \n", nitems, capacity);
784  SCIPdebugMsg(scip, " # profits weights x \n"); /* capture constraints */
785 
786  /* capture all constraints */
787  for( c = 0; c < nitems; ++c )
788  {
789  SCIP_CALL( SCIPcaptureCons(scip, conss[c]) );
790  SCIPdebugMsgPrint(scip, "%4d %3"SCIP_LONGINT_FORMAT"\n", c, weights[c]);
791  }
792 
793  /* activate pricer */
794  SCIP_CALL( SCIPactivatePricer(scip, pricer) );
795 
796  return SCIP_OKAY;
797 }
798 
799 /**@} */
SCIP_RETCODE SCIPpricerBinpackingActivate(SCIP *scip, SCIP_CONS **conss, SCIP_Longint *weights, int *ids, int nitems, SCIP_Longint capacity)
SCIP_RETCODE SCIPsetPricerInit(SCIP *scip, SCIP_PRICER *pricer, SCIP_DECL_PRICERINIT((*pricerinit)))
Definition: scip_pricer.c:214
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:8174
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:877
static SCIP_DECL_PRICEREXITSOL(pricerExitsolBinpacking)
Constraint handler for variable bound constraints .
SCIP_Real SCIPgetDualsolSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9318
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip_general.c:467
SCIP_RETCODE SCIPprintVar(SCIP *scip, SCIP_VAR *var, FILE *file)
Definition: scip_var.c:9813
#define SCIP_MAXSTRLEN
Definition: def.h:279
SCIP_RETCODE SCIPsetObjsense(SCIP *scip, SCIP_OBJSENSE objsense)
Definition: scip_prob.c:1240
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:123
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1353
SCIP_RETCODE SCIPaddCoefSetppc(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition: cons_setppc.c:9227
SCIP_RETCODE SCIPincludePricerBinpacking(SCIP *scip)
int SCIPconshdlrGetNConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4582
Constraint handler stores the local branching decision data.
CONSTYPE
Definition: reader_osil.c:60
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 SCIPsetPricerFree(SCIP *scip, SCIP_PRICER *pricer, SCIP_DECL_PRICERFREE((*pricerfree)))
Definition: scip_pricer.c:190
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1986
SCIP_Bool SCIPconsIsActive(SCIP_CONS *cons)
Definition: cons.c:8138
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip_timing.c:360
Binpacking variable pricer.
#define FALSE
Definition: def.h:73
struct SCIP_VarData SCIP_VARDATA
Definition: type_var.h:107
SCIP_PRICER * SCIPfindPricer(SCIP *scip, const char *name)
Definition: scip_pricer.c:302
SCIP_EXPORT SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17182
#define TRUE
Definition: def.h:72
#define SCIPdebug(x)
Definition: pub_message.h:84
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_RETCODE SCIPdelConsLocal(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:3468
SCIP_PROBDATA * SCIPgetProbData(SCIP *scip)
Definition: scip_prob.c:962
SCIP_RETCODE SCIPgetTransformedCons(SCIP *scip, SCIP_CONS *cons, SCIP_CONS **transcons)
Definition: scip_cons.c:1611
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2555
Variable data containing the ids of constraints in which the variable appears.
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:95
SCIP_Longint SCIPgetMemUsed(SCIP *scip)
Definition: scip_mem.c:91
SCIP_RETCODE SCIPchgVarUbLazy(SCIP *scip, SCIP_VAR *var, SCIP_Real lazyub)
Definition: scip_var.c:5143
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:123
Constraint handler for the set partitioning / packing / covering constraints .
int * SCIPvardataGetConsids(SCIP_VARDATA *vardata)
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:78
#define SCIPdebugPrintCons(x, y, z)
Definition: pub_message.h:93
#define SCIPdebugMsgPrint
Definition: scip_message.h:70
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIP_RETCODE SCIPaddPricedVar(SCIP *scip, SCIP_VAR *var, SCIP_Real score)
Definition: scip_prob.c:1731
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
static SCIP_DECL_PRICERINIT(pricerInitBinpacking)
int SCIPgetNSols(SCIP *scip)
Definition: scip_sol.c:2206
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
Definition: scip_param.c:619
SCIP_RETCODE SCIPgetNegatedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **negvar)
Definition: scip_var.c:1524
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:92
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip_general.c:283
Constraint handler for knapsack constraints of the form , x binary and .
#define PRICER_PRIORITY
SCIP_EXPORT const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17017
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:55
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Constraint handler for logicor constraints (equivalent to set covering, but algorithms are suited fo...
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1941
SCIP_RETCODE SCIPcreateConsBasicKnapsack(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Longint *weights, SCIP_Longint capacity)
int SCIPgetItemid2Samediff(SCIP *scip, SCIP_CONS *cons)
static SCIP_DECL_PRICERFREE(pricerFreeBinpacking)
#define NULL
Definition: lpi_spx1.cpp:155
SCIP_RETCODE SCIPsetPricerExitsol(SCIP *scip, SCIP_PRICER *pricer, SCIP_DECL_PRICEREXITSOL((*pricerexitsol)))
Definition: scip_pricer.c:286
#define SCIP_CALL(x)
Definition: def.h:370
#define PRICER_DESC
SCIP_RETCODE SCIPcaptureCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_cons.c:1075
SCIP_RETCODE SCIPvardataCreateBinpacking(SCIP *scip, SCIP_VARDATA **vardata, int *consids, int nconsids)
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:298
int SCIPgetNFixedonesSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9395
int * SCIPprobdataGetIds(SCIP_PROBDATA *probdata)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:111
SCIP_Real SCIPinfinity(SCIP *scip)
#define SCIP_Bool
Definition: def.h:70
SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip)
SCIP_RETCODE SCIPsetConsInitial(SCIP *scip, SCIP_CONS *cons, SCIP_Bool initial)
Definition: scip_cons.c:1208
Problem data for binpacking problem.
SCIP_EXPORT SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17677
CONSTYPE SCIPgetTypeSamediff(SCIP *scip, SCIP_CONS *cons)
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
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_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_prob.c:1666
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_EXPORT SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17723
SCIP_RETCODE SCIPcheckSolOrig(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *feasible, SCIP_Bool printreason, SCIP_Bool completely)
Definition: scip_sol.c:3498
static SCIP_RETCODE addBranchingDecisionConss(SCIP *scip, SCIP *subscip, SCIP_VAR **vars, SCIP_CONSHDLR *conshdlr)
SCIP_EXPORT SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17733
SCIP_PRICERDATA * SCIPpricerGetData(SCIP_PRICER *pricer)
Definition: pricer.c:501
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_SOL ** SCIPgetSols(SCIP *scip)
Definition: scip_sol.c:2255
static SCIP_DECL_PRICERREDCOST(pricerRedcostBinpacking)
SCIP_EXPORT SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17667
#define PRICER_NAME
int SCIPvardataGetNConsids(SCIP_VARDATA *vardata)
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4539
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10604
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip_sol.c:1767
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:8077
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1245
#define SCIP_Real
Definition: def.h:163
SCIP_RETCODE SCIPcreateConsBasicLogicor(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars)
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition: cons.c:8097
#define SCIP_Longint
Definition: def.h:148
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip_param.c:445
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4167
struct SCIP_PricerData SCIP_PRICERDATA
Definition: type_pricer.h:36
SCIP_RETCODE SCIPactivatePricer(SCIP *scip, SCIP_PRICER *pricer)
Definition: scip_pricer.c:375
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2764
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:98
SCIP_EXPORT SCIP_VARDATA * SCIPvarGetData(SCIP_VAR *var)
Definition: var.c:17037
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip_general.c:315
static SCIP_RETCODE initPricing(SCIP *scip, SCIP_PRICERDATA *pricerdata, SCIP *subscip, SCIP_VAR **vars)
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1110
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:356
#define SCIPABORT()
Definition: def.h:342
default SCIP plugins
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:503
SCIP_RETCODE SCIPcreateProbBasic(SCIP *scip, const char *name)
Definition: scip_prob.c:170
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1436