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