SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
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-2024 Zuse Institute Berlin (ZIB) */
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" */
111struct 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 */
129static
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 */
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 */
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 */
225static
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
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);
256
257 /* loop over all these variables and check if they are fixed to zero */
258 for( v = 0; v < norigvars; ++v )
259 {
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
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 {
323 SCIP_CALL( SCIPsetConsInitial(subscip, cons, FALSE) );
324
325 SCIP_CALL( SCIPaddCons(subscip, cons) );
326 SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
327 }
328
330 }
331 }
332
333 return SCIP_OKAY;
334}
335
336/** initializes the pricing problem for the given capacity */
337static
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
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 */
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) */
428static
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) */
453static
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) */
486static
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 */
510static
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 */
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 */
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;
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 */
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 */
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
674
675 SCIPfreeBufferArray(scip, &consids);
676 }
677 else
678 break;
679 }
680
681 /* free pricer MIP */
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 */
694static
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;
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 */
747
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{
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
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 */
804
805 return SCIP_OKAY;
806}
807
808/**@} */
Constraint handler for knapsack constraints of the form , x binary and .
Constraint handler for logicor constraints (equivalent to set covering, but algorithms are suited fo...
int SCIPgetItemid1Samediff(SCIP *scip, SCIP_CONS *cons)
CONSTYPE SCIPgetTypeSamediff(SCIP *scip, SCIP_CONS *cons)
int SCIPgetItemid2Samediff(SCIP *scip, SCIP_CONS *cons)
Constraint handler stores the local branching decision data.
enum ConsType CONSTYPE
@ SAME
@ DIFFER
Constraint handler for the set partitioning / packing / covering constraints .
Constraint handler for variable bound constraints .
#define NULL
Definition def.h:267
#define SCIP_MAXSTRLEN
Definition def.h:288
#define TRUE
Definition def.h:93
#define FALSE
Definition def.h:94
#define SCIP_LONGINT_FORMAT
Definition def.h:165
#define SCIPABORT()
Definition def.h:346
#define SCIP_CALL(x)
Definition def.h:374
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 SCIPcreateConsBasicKnapsack(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Longint *weights, SCIP_Longint capacity)
int SCIPgetNFixedonesSetppc(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPaddCoefSetppc(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
SCIP_RETCODE SCIPcreateConsBasicLogicor(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars)
SCIP_Real SCIPgetDualsolSetppc(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPfree(SCIP **scip)
SCIP_RETCODE SCIPcreate(SCIP **scip)
SCIP_STATUS SCIPgetStatus(SCIP *scip)
SCIP_STAGE SCIPgetStage(SCIP *scip)
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition scip_prob.c:1668
SCIP_RETCODE SCIPaddPricedVar(SCIP *scip, SCIP_VAR *var, SCIP_Real score)
Definition scip_prob.c:1733
int SCIPgetNVars(SCIP *scip)
Definition scip_prob.c:1992
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition scip_prob.c:2770
SCIP_PROBDATA * SCIPgetProbData(SCIP *scip)
Definition scip_prob.c:964
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition scip_prob.c:1947
SCIP_RETCODE SCIPsetObjsense(SCIP *scip, SCIP_OBJSENSE objsense)
Definition scip_prob.c:1242
SCIP_RETCODE SCIPcreateProbBasic(SCIP *scip, const char *name)
Definition scip_prob.c:180
SCIP_RETCODE SCIPdelConsLocal(SCIP *scip, SCIP_CONS *cons)
Definition scip_prob.c:3474
#define SCIPdebugMsgPrint
#define SCIPdebugMsg
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition scip_param.c:487
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition scip_param.c:307
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition scip_param.c:429
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
Definition scip_param.c:603
int SCIPconshdlrGetNConss(SCIP_CONSHDLR *conshdlr)
Definition cons.c:4636
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition cons.c:4197
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition scip_cons.c:941
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
Definition cons.c:4593
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition cons.c:8234
SCIP_RETCODE SCIPsetConsInitial(SCIP *scip, SCIP_CONS *cons, SCIP_Bool initial)
Definition scip_cons.c:1272
SCIP_Bool SCIPconsIsActive(SCIP_CONS *cons)
Definition cons.c:8275
SCIP_Bool SCIPconsIsEnabled(SCIP_CONS *cons)
Definition cons.c:8311
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition cons.c:8214
SCIP_RETCODE SCIPgetTransformedCons(SCIP *scip, SCIP_CONS *cons, SCIP_CONS **transcons)
Definition scip_cons.c:1675
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition scip_cons.c:1174
SCIP_RETCODE SCIPcaptureCons(SCIP *scip, SCIP_CONS *cons)
Definition scip_cons.c:1139
SCIP_Longint SCIPgetMemUsed(SCIP *scip)
Definition scip_mem.c:100
#define SCIPallocBufferArray(scip, ptr, num)
Definition scip_mem.h:124
#define SCIPfreeBufferArray(scip, ptr)
Definition scip_mem.h:136
#define SCIPfreeBlockMemory(scip, ptr)
Definition scip_mem.h:108
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition scip_mem.h:111
#define SCIPallocBlockMemory(scip, ptr)
Definition scip_mem.h:89
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition scip_mem.h:105
SCIP_RETCODE SCIPsetPricerFree(SCIP *scip, SCIP_PRICER *pricer,)
SCIP_RETCODE SCIPsetPricerInit(SCIP *scip, SCIP_PRICER *pricer,)
SCIP_PRICER * SCIPfindPricer(SCIP *scip, const char *name)
SCIP_PRICERDATA * SCIPpricerGetData(SCIP_PRICER *pricer)
Definition pricer.c:513
SCIP_RETCODE SCIPactivatePricer(SCIP *scip, SCIP_PRICER *pricer)
SCIP_RETCODE SCIPincludePricerBasic(SCIP *scip, SCIP_PRICER **pricerptr, const char *name, const char *desc, int priority, SCIP_Bool delay, SCIP_DECL_PRICERREDCOST((*pricerredcost)), SCIP_DECL_PRICERFARKAS((*pricerfarkas)), SCIP_PRICERDATA *pricerdata)
SCIP_RETCODE SCIPsetPricerExitsol(SCIP *scip, SCIP_PRICER *pricer,)
SCIP_RETCODE SCIPcheckSolOrig(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *feasible, SCIP_Bool printreason, SCIP_Bool completely)
Definition scip_sol.c:3309
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition scip_sol.c:1631
int SCIPgetNSols(SCIP *scip)
Definition scip_sol.c:2070
SCIP_SOL ** SCIPgetSols(SCIP *scip)
Definition scip_sol.c:2119
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition scip_sol.c:1300
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition scip_sol.c:1217
SCIP_RETCODE SCIPsolve(SCIP *scip)
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition var.c:18144
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition var.c:17584
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition var.c:18088
const char * SCIPvarGetName(SCIP_VAR *var)
Definition var.c:17419
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition scip_var.c:1250
SCIP_VARDATA * SCIPvarGetData(SCIP_VAR *var)
Definition var.c:17439
SCIP_RETCODE SCIPgetNegatedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **negvar)
Definition scip_var.c:1529
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition var.c:18134
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition var.c:18078
SCIP_RETCODE SCIPprintVar(SCIP *scip, SCIP_VAR *var, FILE *file)
Definition scip_var.c:9998
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_RETCODE SCIPchgVarUbLazy(SCIP *scip, SCIP_VAR *var, SCIP_Real lazyub)
Definition scip_var.c:5166
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition misc.c:10877
return SCIP_OKAY
int c
static SCIP_SOL * sol
assert(minobj< SCIPgetCutoffbound(scip))
int nvars
SCIP_VAR * var
static SCIP_VAR ** vars
static SCIP_RETCODE addFixedVarsConss(SCIP *scip, SCIP *subscip, SCIP_VAR **vars, SCIP_CONS **conss, int nitems)
SCIP_RETCODE SCIPincludePricerBinpacking(SCIP *scip)
SCIP_RETCODE SCIPpricerBinpackingActivate(SCIP *scip, SCIP_CONS **conss, SCIP_Longint *weights, int *ids, int nitems, SCIP_Longint capacity)
#define PRICER_PRIORITY
static SCIP_RETCODE initPricing(SCIP *scip, SCIP_PRICERDATA *pricerdata, SCIP *subscip, SCIP_VAR **vars)
#define PRICER_NAME
static SCIP_RETCODE addBranchingDecisionConss(SCIP *scip, SCIP *subscip, SCIP_VAR **vars, SCIP_CONSHDLR *conshdlr)
#define PRICER_DELAY
#define PRICER_DESC
Binpacking variable pricer.
int * SCIPprobdataGetIds(SCIP_PROBDATA *probdata)
Problem data for binpacking problem.
#define SCIPerrorMessage
Definition pub_message.h:64
#define SCIPdebug(x)
Definition pub_message.h:93
#define SCIPdebugPrintCons(x, y, z)
SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip)
default SCIP plugins
#define SCIP_DECL_PRICERFREE(x)
Definition type_pricer.h:63
#define SCIP_DECL_PRICERINIT(x)
Definition type_pricer.h:71
#define SCIP_DECL_PRICERREDCOST(x)
#define SCIP_DECL_PRICERFARKAS(x)
#define SCIP_DECL_PRICEREXITSOL(x)
struct SCIP_PricerData SCIP_PRICERDATA
Definition type_pricer.h:45
@ SCIP_OBJSENSE_MAXIMIZE
Definition type_prob.h:47
@ SCIP_DIDNOTRUN
Definition type_result.h:42
@ SCIP_SUCCESS
Definition type_result.h:58
@ SCIP_INVALIDDATA
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_STAGE_PROBLEM
Definition type_set.h:45
@ SCIP_STATUS_OPTIMAL
Definition type_stat.h:61
struct SCIP_VarData SCIP_VARDATA
Definition type_var.h:120
@ SCIP_VARTYPE_BINARY
Definition type_var.h:62
int * SCIPvardataGetConsids(SCIP_VARDATA *vardata)
SCIP_RETCODE SCIPcreateVarBinpacking(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real obj, SCIP_Bool initial, SCIP_Bool removable, SCIP_VARDATA *vardata)
SCIP_RETCODE SCIPvardataCreateBinpacking(SCIP *scip, SCIP_VARDATA **vardata, int *consids, int nconsids)
int SCIPvardataGetNConsids(SCIP_VARDATA *vardata)
Variable data containing the ids of constraints in which the variable appears.