Scippy

SCIP

Solving Constraint Integer Programs

cons_benders.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 cons_benders.c
26 * @ingroup DEFPLUGINS_CONS
27 * @brief constraint handler for Benders' decomposition
28 * @author Stephen J. Maher
29 *
30 * Two constraint handlers are implemented for the generation of Benders' decomposition cuts. When included in a
31 * problem, the Benders' decomposition constraint handlers generate cuts during the enforcement of LP and relaxation
32 * solutions. Additionally, Benders' decomposition cuts can be generated when checking the feasibility of solutions with
33 * respect to the subproblem constraints.
34 *
35 * This constraint handler has an enforcement priority that is less than the integer constraint handler. This means that
36 * only integer feasible solutions from the LP solver are enforced by this constraint handler. This is the traditional
37 * behaviour of the branch-and-check approach to Benders' decomposition. Additionally, the check priority is set low,
38 * such that this expensive constraint handler is only called as a final check on primal feasible solutions.
39 *
40 * This constraint handler in the standard constraint handler that should be added when using Benders' decomposition.
41 * Additionally, there is a flag in SCIPincludeConshdlrBenders that permits the addition of the LP constraint handler,
42 * cons_benderslp. The use of both cons_benders and cons_benderslp allows the user to perform a multiphase Benders'
43 * decomposition algorithm.
44 */
45
46/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
47
48#include <assert.h>
49#include <string.h>
50
51#include "scip/scip.h"
52#include "scip/cons_benders.h"
53#include "scip/heur_trysol.h"
54#include "scip/heuristics.h"
55
56
57/* fundamental constraint handler properties */
58#define CONSHDLR_NAME "benders"
59#define CONSHDLR_DESC "constraint handler to execute Benders' Decomposition"
60#define CONSHDLR_ENFOPRIORITY -100 /**< priority of the constraint handler for constraint enforcing */
61#define CONSHDLR_CHECKPRIORITY -5000000 /**< priority of the constraint handler for checking feasibility */
62#define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
63 * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
64#define CONSHDLR_MAXPREROUNDS 0 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
65#define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_FAST /**< presolving timing of the constraint handler (fast, medium, or exhaustive) */
66#define CONSHDLR_NEEDSCONS FALSE /**< should the constraint handler be skipped, if no constraints are available? */
67
68
69#define DEFAULT_CHECKEDSOLSSIZE 20 /**< initial size of the checked sols array */
70#define DEFAULT_ACTIVE FALSE /**< is the constraint handler active? */
71
72/*
73 * Data structures
74 */
75
76/** constraint handler data */
77struct SCIP_ConshdlrData
78{
79 int* checkedsols; /**< an array of solutions that this constraint has already checked */
80 int ncheckedsols; /**< the number of checked solutions */
81 int checkedsolssize; /**< the size of the checked solutions array */
82 SCIP_Bool active; /**< is the constraint handler active? */
83};
84
85/*
86 * Local methods
87 */
88
89/** constructs a new solution based upon the solutions to the Benders' decomposition subproblems */
90static
92 SCIP* scip, /**< the SCIP instance */
93 SCIP_CONSHDLR* conshdlr, /**< constraint handler */
94 SCIP_SOL* sol, /**< primal CIP solution */
95 SCIP_BENDERSENFOTYPE type /**< the type of solution being enforced */
96 )
97{
98 SCIP_CONSHDLRDATA* conshdlrdata;
99 SCIP_SOL* newsol;
100 SCIP_HEUR* heurtrysol;
101 SCIP_BENDERS** benders;
102 SCIP_VAR** auxiliaryvars;
103 int nactivebenders;
104 int nsubproblems;
105 int i;
106 int j;
107 SCIP_Bool success = TRUE;
108
109 /* don't propose new solutions if not in presolve or solving */
111 return SCIP_OKAY;
112
113 conshdlrdata = SCIPconshdlrGetData(conshdlr);
114 assert(conshdlrdata != NULL);
115
116 benders = SCIPgetBenders(scip);
117 nactivebenders = SCIPgetNActiveBenders(scip);
118
119 /* if the solution is NULL, then we create the solution from the LP sol */
120 if( sol != NULL )
121 {
122 assert(type == SCIP_BENDERSENFOTYPE_CHECK);
123 SCIP_CALL( SCIPcreateSolCopy(scip, &newsol, sol) );
124 }
125 else
126 {
127 switch( type )
128 {
130 SCIP_CALL( SCIPcreateLPSol(scip, &newsol, NULL) );
131 break;
134 break;
137 break;
138 default:
139 SCIP_CALL( SCIPcreateLPSol(scip, &newsol, NULL) );
140 break;
141 } /*lint !e788*/
142 }
143 SCIP_CALL( SCIPunlinkSol(scip, newsol) );
144
145 /* looping through all Benders' decompositions to construct the new solution */
146 for( i = 0; i < nactivebenders; i++ )
147 {
148 /* getting the auxiliary variables and the number of subproblems from the Benders' decomposition structure */
149 auxiliaryvars = SCIPbendersGetAuxiliaryVars(benders[i]);
150 nsubproblems = SCIPbendersGetNSubproblems(benders[i]);
151
152 /* setting the auxiliary variable in the new solution */
153 for( j = 0; j < nsubproblems; j++ )
154 {
155 SCIP_Real objval;
156
157 objval = SCIPbendersGetSubproblemObjval(benders[i], j);
158
159 if( SCIPvarGetStatus(auxiliaryvars[j]) == SCIP_VARSTATUS_FIXED
160 && !SCIPisEQ(scip, SCIPgetSolVal(scip, newsol, auxiliaryvars[j]), objval) )
161 {
162 success = FALSE;
163 break;
164 }
165 else if( SCIPisLT(scip, SCIPgetSolVal(scip, newsol, auxiliaryvars[j]), objval) )
166 {
167 SCIP_CALL( SCIPsetSolVal(scip, newsol, auxiliaryvars[j], objval) );
168 }
169 }
170
171 if( !success )
172 break;
173 }
174
175 /* if setting the variable values was successful, then we try to add the solution */
176 if( success ) /*lint !e774*/
177 {
178 /* checking the size of the checkedsols array and extending it is there is not enough memory */
179 assert(conshdlrdata->ncheckedsols <= conshdlrdata->checkedsolssize);
180 if( conshdlrdata->ncheckedsols + 1 > conshdlrdata->checkedsolssize )
181 {
182 int newsize;
183
184 newsize = SCIPcalcMemGrowSize(scip, conshdlrdata->ncheckedsols + 1);
185 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &conshdlrdata->checkedsols, conshdlrdata->checkedsolssize, newsize) );
186 conshdlrdata->checkedsolssize = newsize;
187 }
188 assert(conshdlrdata->ncheckedsols + 1 <= conshdlrdata->checkedsolssize);
189
190 /* recording the solution number to avoid checking the solution again */
191 conshdlrdata->checkedsols[conshdlrdata->ncheckedsols] = SCIPsolGetIndex(newsol);
192 conshdlrdata->ncheckedsols++;
193
194 /* getting the try solution heuristic */
195 heurtrysol = SCIPfindHeur(scip, "trysol");
196
197 /* passing the new solution to the trysol heuristic */
198 SCIP_CALL( SCIPcheckSol(scip, newsol, FALSE, FALSE, TRUE, TRUE, TRUE, &success) );
199 if ( success )
200 {
201 SCIP_CALL( SCIPheurPassSolAddSol(scip, heurtrysol, newsol) );
202 SCIPdebugMsg(scip, "Creating solution was successful.\n");
203 }
204 else
205 {
206 /* the solution might not be feasible, because of additional constraints */
207 SCIPdebugMsg(scip, "Creating solution was not successful.\n");
208 }
209 }
210
211 SCIP_CALL( SCIPfreeSol(scip, &newsol) );
212
213 return SCIP_OKAY;
214}
215
216/** checks the Benders' decomposition auxiliary variables for unboundedness. */
217static
219 SCIP* scip, /**< the SCIP data structure */
220 SCIP_BENDERS* benders, /**< the Benders' decomposition data structure */
221 SCIP_SOL* sol /**< the primal solution to enforce, or NULL for the current LP/pseudo sol */
222 )
223{
224 int nsubproblems;
225 SCIP_Bool unbounded = FALSE;
226 int i;
227
228 assert(scip != NULL);
229 assert(benders != NULL);
230
231 nsubproblems = SCIPbendersGetNSubproblems(benders);
232
233 /* checking the auxiliary variable values for unboundedness */
234 for( i = 0; i < nsubproblems; i++ )
235 {
237 || SCIPisInfinity(scip, -SCIPgetBendersAuxiliaryVarVal(scip, benders, sol, i)) )
238 {
239 unbounded = TRUE;
240 break;
241 }
242 }
243
244 return unbounded;
245}
246
247/** enforces Benders' constraints for given solution
248 *
249 * This method is called from cons_benderslp and cons_benders. If the method is called from cons_benderslp, then the
250 * solutions are not guaranteed to be integer feasible. This is because the default priority is set greater than the
251 * integer constraint handler. If this method is called from cons_benders, then, because the default enforcement
252 * priority is set less than that of the integer constraint handler, then it can be assumed that the solutions are
253 * integer feasible.
254 *
255 * The checkint flag indicates whether integer feasibility can be assumed. If it is not assumed, i.e. checkint ==
256 * FALSE, then only the convex relaxations of the subproblems are solved. If integer feasibility is assumed, i.e.
257 * checkint == TRUE, then the convex relaxations and the full CIP are solved to generate Benders' cuts and check
258 * solution feasibility.
259 */
261 SCIP* scip, /**< the SCIP instance */
262 SCIP_SOL* sol, /**< the primal solution to enforce, or NULL for the current LP/pseudo sol */
263 SCIP_CONSHDLR* conshdlr, /**< the constraint handler */
264 SCIP_RESULT* result, /**< the result of the enforcement */
265 SCIP_BENDERSENFOTYPE type, /**< the type of solution being enforced */
266 SCIP_Bool checkint /**< should integrality be considered when checking the subproblems */
267 )
268{
269 SCIP_BENDERS** benders;
270 SCIP_Bool infeasible;
271 SCIP_Bool auxviol;
272 int nactivebenders;
273 int i;
274
275 assert(scip != NULL);
276 assert(conshdlr != NULL);
277 assert(result != NULL);
278
279 (*result) = SCIP_FEASIBLE;
280 infeasible = FALSE;
281 auxviol = FALSE;
282
283 benders = SCIPgetBenders(scip);
284 nactivebenders = SCIPgetNActiveBenders(scip);
285
286 for( i = 0; i < nactivebenders; i++ )
287 {
288 switch( type )
289 {
291 if( SCIPbendersCutLP(benders[i]) )
292 {
293 SCIP_Bool unbounded = FALSE;
294
295 /* if the solution is unbounded, then it may not be possible to generate any Benders' decomposition
296 * cuts. If the unboundedness is from the auxiliary variables, then cuts are required. Otherwise, if
297 * the unboundedness comes from original variables, then the unboundedness needs to be handled by other
298 * constraint handlers or the problem is reported as unbounded
299 * */
301 {
302 if( !unboundedAuxiliaryVariables(scip, benders[i], NULL) )
303 {
304 (*result) = SCIP_FEASIBLE;
305 auxviol = FALSE;
306 unbounded = TRUE;
307 }
308 }
309
310 if( !unbounded )
311 {
312 SCIP_CALL( SCIPsolveBendersSubproblems(scip, benders[i], NULL, result, &infeasible, &auxviol, type, checkint) );
313 }
314 }
315 break;
317 if( SCIPbendersCutRelaxation(benders[i]) )
318 {
319 SCIP_CALL( SCIPsolveBendersSubproblems(scip, benders[i], sol, result, &infeasible, &auxviol, type, checkint) );
320 }
321 break;
323 if( SCIPbendersCutPseudo(benders[i]) )
324 {
325 SCIP_CALL( SCIPsolveBendersSubproblems(scip, benders[i], NULL, result, &infeasible, &auxviol, type, checkint) );
326 }
327 break;
329 SCIPwarningMessage(scip, "The conscheck callback is not supported\n");
330 break;
331 default:
332 break;
333 } /*lint !e788*/
334
335 /* The decompositions are checked until one is found that is not feasible. Not being feasible could mean that
336 * infeasibility of the original problem has been proven or a constraint has been added. If the result
337 * SCIP_DIDNOTRUN is returned, then the next decomposition is checked */
338 if( (*result) != SCIP_FEASIBLE && (*result) != SCIP_DIDNOTRUN )
339 break;
340 }
341
342 /* if the constraint handler was called with an integer feasible solution, then a feasible solution can be proposed */
343 if( checkint )
344 {
345 /* in the case that the problem is feasible, this means that all subproblems are feasible. The auxiliary variables
346 * still need to be updated. This is done by constructing a valid solution. */
347 if( (*result) == SCIP_FEASIBLE && auxviol )
348 {
349 SCIP_CALL( constructValidSolution(scip, conshdlr, sol, type) );
350
351 (*result) = SCIP_INFEASIBLE;
352 }
353 }
354
355 /* if no Benders' decomposition were run, then the result is returned as SCIP_FEASIBLE. The SCIP_DIDNOTRUN result
356 * indicates that no subproblems were checked or that cuts were disabled, so that it is not guaranteed that this
357 * solution is feasible.
358 */
359 if( (*result) == SCIP_DIDNOTRUN )
360 (*result) = SCIP_FEASIBLE;
361
362 return SCIP_OKAY;
363}
364
365/*
366 * Callback methods of constraint handler
367 */
368
369/** copy method for constraint handler plugins (called when SCIP copies plugins) */
370static
371SCIP_DECL_CONSHDLRCOPY(conshdlrCopyBenders)
372{ /*lint --e{715}*/
373 assert(scip != NULL);
374
376
377 *valid = TRUE;
378
379 return SCIP_OKAY;
380}
381
382/** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
383static
384SCIP_DECL_CONSFREE(consFreeBenders)
385{ /*lint --e{715}*/
386 SCIP_CONSHDLRDATA* conshdlrdata;
387
388 assert(scip != NULL);
389 assert(conshdlr != NULL);
390
391 conshdlrdata = SCIPconshdlrGetData(conshdlr);
392 assert(conshdlrdata != NULL);
393
394 /* freeing the constraint handler data */
395 SCIPfreeMemory(scip, &conshdlrdata);
396
397 return SCIP_OKAY;
398}
399
400
401/** initialization method of constraint handler (called after problem was transformed) */
402static
403SCIP_DECL_CONSINIT(consInitBenders)
404{ /*lint --e{715}*/
405 SCIP_CONSHDLRDATA* conshdlrdata;
406
407 assert(scip != NULL);
408 assert(conshdlr != NULL);
409
410 conshdlrdata = SCIPconshdlrGetData(conshdlr);
411
412 conshdlrdata->checkedsolssize = DEFAULT_CHECKEDSOLSSIZE;
413 conshdlrdata->ncheckedsols = 0;
414
415 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &conshdlrdata->checkedsols, conshdlrdata->checkedsolssize) );
416
417 return SCIP_OKAY;
418}
419
420
421/** deinitialization method of constraint handler (called before transformed problem is freed) */
422static
423SCIP_DECL_CONSEXIT(consExitBenders)
424{ /*lint --e{715}*/
425 SCIP_CONSHDLRDATA* conshdlrdata;
426
427 assert(scip != NULL);
428 assert(conshdlr != NULL);
429
430 conshdlrdata = SCIPconshdlrGetData(conshdlr);
431 assert(conshdlrdata != NULL);
432
433 /* freeing the checked sols array */
434 SCIPfreeBlockMemoryArray(scip, &conshdlrdata->checkedsols, conshdlrdata->checkedsolssize);
435
436 return SCIP_OKAY;
437}
438
439
440
441/** constraint enforcing method of constraint handler for LP solutions */
442static
443SCIP_DECL_CONSENFOLP(consEnfolpBenders)
444{ /*lint --e{715}*/
445 SCIP_CONSHDLRDATA* conshdlrdata;
446
447 assert(scip != NULL);
448 assert(conshdlr != NULL);
449
450 conshdlrdata = SCIPconshdlrGetData(conshdlr);
451 assert(conshdlrdata != NULL);
452
453 if( conshdlrdata->active )
454 {
456 }
457 else
458 (*result) = SCIP_FEASIBLE;
459
460 return SCIP_OKAY;
461}
462
463
464/** constraint enforcing method of constraint handler for relaxation solutions */
465static
466SCIP_DECL_CONSENFORELAX(consEnforelaxBenders)
467{ /*lint --e{715}*/
468 SCIP_CONSHDLRDATA* conshdlrdata;
469
470 assert(scip != NULL);
471 assert(conshdlr != NULL);
472
473 conshdlrdata = SCIPconshdlrGetData(conshdlr);
474 assert(conshdlrdata != NULL);
475
476 if( conshdlrdata->active )
477 {
479 }
480 else
481 (*result) = SCIP_FEASIBLE;
482
483 return SCIP_OKAY;
484}
485
486
487/** constraint enforcing method of constraint handler for pseudo solutions */
488static
489SCIP_DECL_CONSENFOPS(consEnfopsBenders)
490{ /*lint --e{715}*/
491 SCIP_CONSHDLRDATA* conshdlrdata;
492
493 assert(scip != NULL);
494 assert(conshdlr != NULL);
495
496 conshdlrdata = SCIPconshdlrGetData(conshdlr);
497 assert(conshdlrdata != NULL);
498
499 if( conshdlrdata->active )
500 {
502 }
503 else
504 (*result) = SCIP_FEASIBLE;
505
506 return SCIP_OKAY;
507}
508
509
510/** feasibility check method of constraint handler for integral solutions
511 *
512 * This function checks the feasibility of the Benders' decomposition master problem. In the case that the problem is
513 * feasible, then the auxiliary variables must be updated with the subproblem objective function values. It is not
514 * possible to simply update the auxiliary variable values, so a new solution is created.
515 */
516static
517SCIP_DECL_CONSCHECK(consCheckBenders)
518{ /*lint --e{715}*/
519 SCIP_CONSHDLRDATA* conshdlrdata;
520 SCIP_BENDERS** benders;
521 int nactivebenders;
522 int solindex;
523 int i;
524 SCIP_Bool performcheck;
525 SCIP_Bool infeasible;
526 SCIP_Bool auxviol;
527
528 assert(scip != NULL);
529 assert(conshdlr != NULL);
530 assert(result != NULL);
531
532 (*result) = SCIP_FEASIBLE;
533 performcheck = TRUE;
534 infeasible = FALSE;
535 auxviol = FALSE;
536
537 conshdlrdata = SCIPconshdlrGetData(conshdlr);
538
539 /* if the constraint handler is active, then the check must be performed. */
540 if( conshdlrdata->active )
541 {
542 benders = SCIPgetBenders(scip);
543 nactivebenders = SCIPgetNActiveBenders(scip);
544
545 /* checking if the solution was constructed by this constraint handler */
546 solindex = SCIPsolGetIndex(sol);
547 for( i = 0; i < conshdlrdata->ncheckedsols; i++ )
548 {
549 if( conshdlrdata->checkedsols[i] == solindex )
550 {
551 conshdlrdata->checkedsols[0] = conshdlrdata->checkedsols[conshdlrdata->ncheckedsols - 1];
552 conshdlrdata->ncheckedsols--;
553
554 performcheck = FALSE;
555 break;
556 }
557 }
558
559 /* if the solution has not been checked before, then we must perform the check */
560 if( performcheck && nactivebenders > 0 )
561 {
562 for( i = 0; i < nactivebenders; i++ )
563 {
564 SCIP_CALL( SCIPsolveBendersSubproblems(scip, benders[i], sol, result, &infeasible, &auxviol,
566
567 /* in the case of multiple Benders' decompositions, the subproblems are solved until a constriant is added or
568 * infeasibility is proven. So if the result is not SCIP_FEASIBLE, then the loop is exited */
569 if( (*result) != SCIP_FEASIBLE )
570 break;
571 }
572
573 /* in the case that the problem is feasible, this means that all subproblems are feasible. The auxiliary variables
574 * still need to be updated. This is done by constructing a valid solution. */
575 if( (*result) == SCIP_FEASIBLE )
576 {
577 if( auxviol )
578 {
579 if( !SCIPsolIsOriginal(sol) )
580 {
582 }
583
584 if( printreason )
585 SCIPmessagePrintInfo(SCIPgetMessagehdlr(scip), "all subproblems are feasible but there is a violation in the auxiliary variables\n");
586
587 (*result) = SCIP_INFEASIBLE;
588 }
589 }
590
591 /* if no Benders' decomposition were run, then the result is returned as SCIP_FEASIBLE. The SCIP_DIDNOTRUN result
592 * indicates that no subproblems were checked or that cuts were disabled, so that it is not guaranteed that this
593 * solution is feasible.
594 */
595 if( (*result) == SCIP_DIDNOTRUN )
596 (*result) = SCIP_FEASIBLE;
597 }
598 }
599
600 return SCIP_OKAY;
601}
602
603
604/** the presolving method for the Benders' decomposition constraint handler
605 *
606 * This method is used to update the lower bounds of the auxiliary problem and to identify infeasibility before the
607 * subproblems are solved. When SCIP is copied, the Benders' decomposition subproblems from the source SCIP are
608 * transferred to the target SCIP. So there is no need to perform this presolving step in the copied SCIP, since the
609 * computed bounds would be identical.
610 */
611static
612SCIP_DECL_CONSPRESOL(consPresolBenders)
613{ /*lint --e{715}*/
614 SCIP_CONSHDLRDATA* conshdlrdata;
615 SCIP_BENDERS** benders;
616 int nactivebenders;
617 int nsubproblems;
618 int i;
619 int j;
620
621 assert(scip != NULL);
622 assert(conshdlr != NULL);
623
624 (*result) = SCIP_DIDNOTFIND;
625
626 /* this presolving step is only valid for the main SCIP instance. If the SCIP instance is copied, then the presolving
627 * step is not performed.
628 */
629 if( SCIPgetSubscipDepth(scip) > 0 )
630 {
631 (*result) = SCIP_DIDNOTRUN;
632 return SCIP_OKAY;
633 }
634
635 conshdlrdata = SCIPconshdlrGetData(conshdlr);
636 assert(conshdlrdata != NULL);
637
638 /* it is only possible to compute the lower bound of the subproblems if the constraint handler is active */
639 if( conshdlrdata->active )
640 {
641 benders = SCIPgetBenders(scip);
642 nactivebenders = SCIPgetNActiveBenders(scip);
643
644 /* need to compute the lower bound for all active Benders' decompositions */
645 for( i = 0; i < nactivebenders; i++ )
646 {
647 nsubproblems = SCIPbendersGetNSubproblems(benders[i]);
648
649 for( j = 0; j < nsubproblems; j++ )
650 {
651 SCIP_VAR* auxiliaryvar;
652 SCIP_Real lowerbound;
653 SCIP_Bool infeasible;
654
655 infeasible = FALSE;
656
657 /* computing the lower bound of the subproblem by solving it without any variable fixings */
658 SCIP_CALL( SCIPcomputeBendersSubproblemLowerbound(scip, benders[i], j, &lowerbound, &infeasible) );
659
660 if( infeasible )
661 {
662 (*result) = SCIP_CUTOFF;
663 break;
664 }
665
666 /* retrieving the auxiliary variable */
667 auxiliaryvar = SCIPbendersGetAuxiliaryVar(benders[i], j);
668
669 /* only update the lower bound if it is greater than the current lower bound */
670 if( SCIPisGT(scip, lowerbound, SCIPvarGetLbLocal(auxiliaryvar)) )
671 {
672 SCIPdebugMsg(scip, "Tightened lower bound of <%s> to %g\n", SCIPvarGetName(auxiliaryvar), lowerbound);
673 /* updating the lower bound of the auxiliary variable */
674 SCIP_CALL( SCIPchgVarLb(scip, auxiliaryvar, lowerbound) );
675
676 (*nchgbds)++;
677 (*result) = SCIP_SUCCESS;
678 }
679
680 /* stores the lower bound for the subproblem */
681 SCIPbendersUpdateSubproblemLowerbound(benders[i], j, lowerbound);
682 }
683
684 if( (*result) == SCIP_CUTOFF )
685 break;
686 }
687 }
688
689 return SCIP_OKAY;
690}
691
692/** variable rounding lock method of constraint handler
693 * The auxiliary variables and the master problem variables need to lock added by the Benders' decomposition
694 * constraint. The auxiliary variables require a down lock. The master problem variable need both up and down lock.
695 * The master problem variables require locks in both directions because the coefficients in all potential Benders'
696 * cuts are not known in general.
697 */
698static
699SCIP_DECL_CONSLOCK(consLockBenders)
700{ /*lint --e{715}*/
701 SCIP_CONSHDLRDATA* conshdlrdata;
702 SCIP_BENDERS** benders;
703 SCIP_VAR** vars;
704 int nactivebenders;
705 int nsubproblems;
706 int nvars;
707 int i;
708 int j;
709
710 assert(scip != NULL);
711 assert(conshdlr != NULL);
712 assert(locktype == SCIP_LOCKTYPE_MODEL);
713
714 conshdlrdata = SCIPconshdlrGetData(conshdlr);
715 assert(conshdlrdata != NULL);
716
717 /* the locks should only be added if the Benders' decomposition constraint handler has been activated */
718 if( conshdlrdata->active )
719 {
720 benders = SCIPgetBenders(scip);
721 nactivebenders = SCIPgetNActiveBenders(scip);
722
723 /* retrieving the master problem variables */
724 SCIP_CALL( SCIPgetOrigVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
725
726 /* need to compute the lower bound for all active Benders' decompositions */
727 for( i = 0; i < nactivebenders; i++ )
728 {
729 nsubproblems = SCIPbendersGetNSubproblems(benders[i]);
730
731 /* if the auxiliary variable exists, then we need to add a down lock. Initially, a down lock is added to all
732 * auxiliary variables during creating. This is because the creation of auxiliary variable occurs after
733 * CONS_LOCK is called. The inclusion of the auxiliary variables in this function is to cover the case if locks
734 * are added or removed after presolving.
735 */
736 for( j = 0; j < nsubproblems; j++ )
737 {
738 SCIP_VAR* auxvar;
739
740 auxvar = SCIPbendersGetAuxiliaryVar(benders[i], j);
741
742 if( auxvar != NULL )
743 {
744 SCIP_CALL( SCIPaddVarLocksType(scip, auxvar, locktype, nlockspos, nlocksneg) );
745 }
746 }
747
748 /* adding up and down locks for all master problem variables. Since the locks for all constraint handlers
749 * without constraints, no auxiliary variables have been added. As such, all variables are master variables.
750 */
751 for( j = 0; j < nvars; j++ )
752 {
753 SCIP_CALL( SCIPaddVarLocksType(scip, vars[j], locktype, (nlockspos + nlocksneg)*nsubproblems,
754 (nlockspos + nlocksneg)*nsubproblems) );
755 }
756 }
757 }
758
759 return SCIP_OKAY;
760}
761
762
763/*
764 * constraint specific interface methods
765 */
766
767/** creates the handler for Benders' decomposition and includes it in SCIP */
769 SCIP* scip /**< SCIP data structure */
770 )
771{
772 SCIP_CONSHDLRDATA* conshdlrdata;
773 SCIP_CONSHDLR* conshdlr;
774
775 /* create benders constraint handler data */
776 conshdlrdata = NULL;
777
778 SCIP_CALL( SCIPallocMemory(scip, &conshdlrdata) );
779
780 conshdlr = NULL;
781
782 /* include constraint handler */
785 consEnfolpBenders, consEnfopsBenders, consCheckBenders, consLockBenders,
786 conshdlrdata) );
787 assert(conshdlr != NULL);
788
789 /* set non-fundamental callbacks via specific setter functions */
790 SCIP_CALL( SCIPsetConshdlrInit(scip, conshdlr, consInitBenders) );
791 SCIP_CALL( SCIPsetConshdlrExit(scip, conshdlr, consExitBenders) );
792 SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyBenders, NULL) );
793 SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeBenders) );
794 SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxBenders) );
796
797 /* add Benders' decomposition constraint handler parameters */
799 "constraints/" CONSHDLR_NAME "/active", "is the Benders' decomposition constraint handler active?",
800 &conshdlrdata->active, FALSE, DEFAULT_ACTIVE, NULL, NULL));
801
802 return SCIP_OKAY;
803}
static GRAPHNODE ** active
static SCIP_RETCODE constructValidSolution(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, SCIP_BENDERSENFOTYPE type)
Definition: cons_benders.c:91
#define CONSHDLR_NEEDSCONS
Definition: cons_benders.c:66
static SCIP_DECL_CONSINIT(consInitBenders)
Definition: cons_benders.c:403
#define CONSHDLR_CHECKPRIORITY
Definition: cons_benders.c:61
#define CONSHDLR_DESC
Definition: cons_benders.c:59
static SCIP_DECL_CONSEXIT(consExitBenders)
Definition: cons_benders.c:423
static SCIP_DECL_CONSLOCK(consLockBenders)
Definition: cons_benders.c:699
#define CONSHDLR_MAXPREROUNDS
Definition: cons_benders.c:64
static SCIP_DECL_CONSCHECK(consCheckBenders)
Definition: cons_benders.c:517
static SCIP_DECL_CONSFREE(consFreeBenders)
Definition: cons_benders.c:384
static SCIP_DECL_CONSENFOLP(consEnfolpBenders)
Definition: cons_benders.c:443
static SCIP_DECL_CONSPRESOL(consPresolBenders)
Definition: cons_benders.c:612
static SCIP_DECL_CONSHDLRCOPY(conshdlrCopyBenders)
Definition: cons_benders.c:371
#define DEFAULT_CHECKEDSOLSSIZE
Definition: cons_benders.c:69
static SCIP_DECL_CONSENFORELAX(consEnforelaxBenders)
Definition: cons_benders.c:466
#define CONSHDLR_PRESOLTIMING
Definition: cons_benders.c:65
static SCIP_DECL_CONSENFOPS(consEnfopsBenders)
Definition: cons_benders.c:489
#define CONSHDLR_EAGERFREQ
Definition: cons_benders.c:62
#define CONSHDLR_ENFOPRIORITY
Definition: cons_benders.c:60
static SCIP_Bool unboundedAuxiliaryVariables(SCIP *scip, SCIP_BENDERS *benders, SCIP_SOL *sol)
Definition: cons_benders.c:218
#define CONSHDLR_NAME
Definition: cons_benders.c:58
#define DEFAULT_ACTIVE
Definition: cons_benders.c:70
constraint handler for Benders' decomposition
#define NULL
Definition: def.h:267
#define SCIP_Bool
Definition: def.h:91
#define SCIP_Real
Definition: def.h:173
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define SCIP_CALL(x)
Definition: def.h:374
SCIP_RETCODE SCIPconsBendersEnforceSolution(SCIP *scip, SCIP_SOL *sol, SCIP_CONSHDLR *conshdlr, SCIP_RESULT *result, SCIP_BENDERSENFOTYPE type, SCIP_Bool checkint)
Definition: cons_benders.c:260
SCIP_RETCODE SCIPincludeConshdlrBenders(SCIP *scip)
Definition: cons_benders.c:768
int SCIPgetSubscipDepth(SCIP *scip)
Definition: scip_copy.c:2605
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:380
SCIP_RETCODE SCIPgetOrigVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:2357
SCIP_MESSAGEHDLR * SCIPgetMessagehdlr(SCIP *scip)
Definition: scip_message.c:88
#define SCIPdebugMsg
Definition: scip_message.h:78
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:120
SCIP_RETCODE SCIPheurPassSolAddSol(SCIP *scip, SCIP_HEUR *heur, SCIP_SOL *sol)
Definition: heur_trysol.c:293
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:57
int SCIPgetNActiveBenders(SCIP *scip)
Definition: scip_benders.c:532
SCIP_Bool SCIPbendersCutRelaxation(SCIP_BENDERS *benders)
Definition: benders.c:6102
SCIP_BENDERS ** SCIPgetBenders(SCIP *scip)
Definition: scip_benders.c:508
SCIP_RETCODE SCIPcomputeBendersSubproblemLowerbound(SCIP *scip, SCIP_BENDERS *benders, int probnumber, SCIP_Real *lowerbound, SCIP_Bool *infeasible)
Definition: scip_benders.c:959
SCIP_VAR * SCIPbendersGetAuxiliaryVar(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:6160
SCIP_Real SCIPgetBendersAuxiliaryVarVal(SCIP *scip, SCIP_BENDERS *benders, SCIP_SOL *sol, int probnumber)
Definition: scip_benders.c:931
SCIP_Bool SCIPbendersCutPseudo(SCIP_BENDERS *benders)
Definition: benders.c:6092
SCIP_VAR ** SCIPbendersGetAuxiliaryVars(SCIP_BENDERS *benders)
Definition: benders.c:6172
int SCIPbendersGetNSubproblems(SCIP_BENDERS *benders)
Definition: benders.c:5968
void SCIPbendersUpdateSubproblemLowerbound(SCIP_BENDERS *benders, int probnumber, SCIP_Real lowerbound)
Definition: benders.c:6713
SCIP_Bool SCIPbendersCutLP(SCIP_BENDERS *benders)
Definition: benders.c:6082
SCIP_RETCODE SCIPsolveBendersSubproblems(SCIP *scip, SCIP_BENDERS *benders, SCIP_SOL *sol, SCIP_RESULT *result, SCIP_Bool *infeasible, SCIP_Bool *auxviol, SCIP_BENDERSENFOTYPE type, SCIP_Bool checkint)
Definition: scip_benders.c:622
SCIP_Real SCIPbendersGetSubproblemObjval(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:6199
SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip_cons.c:540
SCIP_RETCODE SCIPsetConshdlrInit(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINIT((*consinit)))
Definition: scip_cons.c:396
SCIP_RETCODE SCIPincludeConshdlrBasic(SCIP *scip, SCIP_CONSHDLR **conshdlrptr, const char *name, const char *desc, int enfopriority, int chckpriority, int eagerfreq, SCIP_Bool needscons, SCIP_DECL_CONSENFOLP((*consenfolp)), SCIP_DECL_CONSENFOPS((*consenfops)), SCIP_DECL_CONSCHECK((*conscheck)), SCIP_DECL_CONSLOCK((*conslock)), SCIP_CONSHDLRDATA *conshdlrdata)
Definition: scip_cons.c:181
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip_cons.c:372
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENFORELAX((*consenforelax)))
Definition: scip_cons.c:323
SCIP_RETCODE SCIPsetConshdlrExit(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXIT((*consexit)))
Definition: scip_cons.c:420
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy)))
Definition: scip_cons.c:347
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4217
SCIP_HEUR * SCIPfindHeur(SCIP *scip, const char *name)
Definition: scip_heur.c:258
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:168
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:110
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:139
#define SCIPallocMemory(scip, ptr)
Definition: scip_mem.h:60
#define SCIPfreeMemory(scip, ptr)
Definition: scip_mem.h:78
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:99
SCIP_RETCODE SCIPcreateSolCopy(SCIP *scip, SCIP_SOL **sol, SCIP_SOL *sourcesol)
Definition: scip_sol.c:474
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:841
SCIP_RETCODE SCIPcreateLPSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:226
SCIP_RETCODE SCIPunlinkSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1046
SCIP_Bool SCIPsolIsOriginal(SCIP_SOL *sol)
Definition: sol.c:2721
SCIP_RETCODE SCIPcreateRelaxSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:289
int SCIPsolGetIndex(SCIP_SOL *sol)
Definition: sol.c:2835
SCIP_RETCODE SCIPcheckSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *feasible)
Definition: scip_sol.c:3251
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1077
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1217
SCIP_RETCODE SCIPcreatePseudoSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:316
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPchgVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4676
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17538
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
Definition: scip_var.c:4259
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17419
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18134
primal heuristic that tries a given solution
methods commonly used by primal heuristics
void SCIPmessagePrintInfo(SCIP_MESSAGEHDLR *messagehdlr, const char *formatstr,...)
Definition: message.c:594
SCIP callable library.
@ SCIP_BENDERSENFOTYPE_RELAX
Definition: type_benders.h:47
@ SCIP_BENDERSENFOTYPE_LP
Definition: type_benders.h:46
@ SCIP_BENDERSENFOTYPE_CHECK
Definition: type_benders.h:49
@ SCIP_BENDERSENFOTYPE_PSEUDO
Definition: type_benders.h:48
enum SCIP_BendersEnfoType SCIP_BENDERSENFOTYPE
Definition: type_benders.h:51
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
Definition: type_cons.h:64
@ SCIP_LPSOLSTAT_UNBOUNDEDRAY
Definition: type_lp.h:45
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_CUTOFF
Definition: type_result.h:48
@ SCIP_FEASIBLE
Definition: type_result.h:45
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
@ SCIP_SUCCESS
Definition: type_result.h:58
@ SCIP_INFEASIBLE
Definition: type_result.h:46
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ SCIP_STAGE_INITPRESOLVE
Definition: type_set.h:48
@ SCIP_STAGE_SOLVED
Definition: type_set.h:54
@ SCIP_VARSTATUS_FIXED
Definition: type_var.h:52
@ SCIP_LOCKTYPE_MODEL
Definition: type_var.h:97