Scippy

SCIP

Solving Constraint Integer Programs

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-2025 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 benders.c
26 * @ingroup OTHER_CFILES
27 * @brief methods for Benders' decomposition
28 * @author Stephen J. Maher
29 */
30
31/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32
33#include <assert.h>
34#include <string.h>
35
36#include "scip/def.h"
37#include "scip/set.h"
38#include "scip/clock.h"
39#include "scip/dcmp.h"
40#include "scip/paramset.h"
41#include "scip/lp.h"
42#include "scip/prob.h"
43#include "scip/pricestore.h"
44#include "scip/scip.h"
45#include "scip/scipdefplugins.h"
46#include "scip/benders.h"
47#include "scip/pub_message.h"
48#include "scip/pub_misc.h"
49#include "scip/cons_linear.h"
50#include "scip/cons_nonlinear.h"
51
52#include "scip/struct_benders.h"
54
55#include "scip/benderscut.h"
56
57/* Defaults for parameters */
58#define SCIP_DEFAULT_TRANSFERCUTS FALSE /** should Benders' cuts generated in LNS heuristics be transferred to the main SCIP instance? */
59#define SCIP_DEFAULT_CUTSASCONSS TRUE /** should the transferred cuts be added as constraints? */
60#define SCIP_DEFAULT_LNSCHECK TRUE /** should the Benders' decomposition be used in LNS heuristics */
61#define SCIP_DEFAULT_LNSMAXDEPTH -1 /** maximum depth at which the LNS check is performed */
62#define SCIP_DEFAULT_LNSMAXCALLS 10 /** the maximum number of Benders' decomposition calls in LNS heuristics */
63#define SCIP_DEFAULT_LNSMAXCALLSROOT 0 /** the maximum number of root node Benders' decomposition calls in LNS heuristics */
64#define SCIP_DEFAULT_SUBPROBFRAC 1.0 /** fraction of subproblems that are solved in each iteration */
65#define SCIP_DEFAULT_UPDATEAUXVARBOUND FALSE /** should the auxiliary variable lower bound be updated by solving the subproblem */
66#define SCIP_DEFAULT_AUXVARSIMPLINT FALSE /** set the auxiliary variables as implint if the subproblem objective is integer */
67#define SCIP_DEFAULT_CUTCHECK TRUE /** should cuts be generated during the checking of solutions? */
68#define SCIP_DEFAULT_STRENGTHENMULT 0.5 /** the convex combination multiplier for the cut strengthening */
69#define SCIP_DEFAULT_NOIMPROVELIMIT 5 /** the maximum number of cut strengthening without improvement */
70#define SCIP_DEFAULT_STRENGTHENPERTURB 1e-06 /** the amount by which the cut strengthening solution is perturbed */
71#define SCIP_DEFAULT_STRENGTHENENABLED FALSE /** enable the core point cut strengthening approach */
72#define SCIP_DEFAULT_STRENGTHENINTPOINT 'r' /** where should the strengthening interior point be sourced from ('l'p relaxation, 'f'irst solution, 'i'ncumbent solution, 'r'elative interior point, vector of 'o'nes, vector of 'z'eros) */
73#define SCIP_DEFAULT_NUMTHREADS 1 /** the number of parallel threads to use when solving the subproblems */
74#define SCIP_DEFAULT_EXECFEASPHASE FALSE /** should a feasibility phase be executed during the root node processing */
75#define SCIP_DEFAULT_SLACKVARCOEF 1e+6 /** the initial objective coefficient of the slack variables in the subproblem */
76#define SCIP_DEFAULT_MAXSLACKVARCOEF 1e+9 /** the maximal objective coefficient of the slack variables in the subproblem */
77#define SCIP_DEFAULT_CHECKCONSCONVEXITY TRUE /** should the constraints of the subproblem be checked for convexity? */
78#define SCIP_DEFAULT_NLPITERLIMIT 10000 /** iteration limit for NLP solver */
79
80#define BENDERS_MAXPSEUDOSOLS 5 /** the maximum number of pseudo solutions checked before suggesting
81 * merge candidates */
83#define BENDERS_ARRAYSIZE 1000 /**< the initial size of the added constraints/cuts arrays */
85#define AUXILIARYVAR_NAME "##bendersauxiliaryvar" /** the name for the Benders' auxiliary variables in the master problem */
86#define SLACKVAR_NAME "##bendersslackvar" /** the name for the Benders' slack variables added to each
87 * constraints in the subproblems */
88#define NLINEARCONSHDLRS 5
90/* event handler properties */
91#define NODEFOCUS_EVENTHDLR_NAME "bendersnodefocus"
92#define NODEFOCUS_EVENTHDLR_DESC "node focus event handler for Benders' decomposition"
94#define MIPNODEFOCUS_EVENTHDLR_NAME "bendersmipsolvenodefocus"
95#define MIPNODEFOCUS_EVENTHDLR_DESC "node focus event handler for the MIP solve method for Benders' decomposition"
97#define UPPERBOUND_EVENTHDLR_NAME "bendersupperbound"
98#define UPPERBOUND_EVENTHDLR_DESC "found solution event handler to terminate subproblem solve for a given upper bound"
100#define NODESOLVED_EVENTHDLR_NAME "bendersnodesolved"
101#define NODESOLVED_EVENTHDLR_DESC "node solved event handler for the Benders' integer cuts"
102
103
104/** event handler data */
105struct SCIP_EventhdlrData
106{
107 int filterpos; /**< the event filter entry */
108 int numruns; /**< the number of times that the problem has been solved */
109 SCIP_Real upperbound; /**< an upper bound for the problem */
110 SCIP_Bool solvecip; /**< is the event called from a MIP subproblem solve*/
111};
112
113
114/* ---------------- Local methods for event handlers ---------------- */
115
116/** initialises the members of the eventhandler data */
117static
119 SCIP* scip, /**< the SCIP data structure */
120 SCIP_EVENTHDLRDATA* eventhdlrdata /**< the event handler data */
121 )
122{
123 assert(scip != NULL);
124 assert(eventhdlrdata != NULL);
125
126 eventhdlrdata->filterpos = -1;
127 eventhdlrdata->numruns = 0;
128 eventhdlrdata->upperbound = -SCIPinfinity(scip);
129 eventhdlrdata->solvecip = FALSE;
130
131 return SCIP_OKAY;
132}
133
134/** initsol method for the event handlers */
135static
137 SCIP* scip, /**< the SCIP data structure */
138 SCIP_EVENTHDLR* eventhdlr, /**< the event handlers data structure */
139 SCIP_EVENTTYPE eventtype /**< event type mask to select events to catch */
140 )
141{
142 SCIP_EVENTHDLRDATA* eventhdlrdata;
143
144 assert(scip != NULL);
145 assert(eventhdlr != NULL);
146
147 eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
148
149 SCIP_CALL(SCIPcatchEvent(scip, eventtype, eventhdlr, NULL, &eventhdlrdata->filterpos));
150
151 return SCIP_OKAY;
152}
153
154/** the exit sol method for the event handlers */
155static
157 SCIP* scip, /**< the SCIP data structure */
158 SCIP_EVENTHDLR* eventhdlr, /**< the event handlers data structure */
159 SCIP_EVENTTYPE eventtype /**< event type mask to select events to catch */
160 )
161{
162 SCIP_EVENTHDLRDATA* eventhdlrdata;
163
164 assert(scip != NULL);
165 assert(eventhdlr != NULL);
166
167 eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
168
169 if( eventhdlrdata->filterpos >= 0 )
170 {
171 SCIP_CALL(SCIPdropEvent(scip, eventtype, eventhdlr, NULL, eventhdlrdata->filterpos));
172 eventhdlrdata->filterpos = -1;
173 }
174
175 return SCIP_OKAY;
176}
177
178/** the exit method for the event handlers */
179static
181 SCIP* scip, /**< the SCIP data structure */
182 SCIP_EVENTHDLR* eventhdlr /**< the event handlers data structure */
183 )
184{
185 SCIP_EVENTHDLRDATA* eventhdlrdata;
186
187 assert(scip != NULL);
188 assert(eventhdlr != NULL);
189
190 eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
191
192 /* reinitialise the event handler data */
193 SCIP_CALL( initEventhandlerData(scip, eventhdlrdata) );
194
195 return SCIP_OKAY;
196}
197
198/** free method for the event handler */
199static
201 SCIP* scip, /**< the SCIP data structure */
202 SCIP_EVENTHDLR* eventhdlr /**< the event handlers data structure */
203 )
204{
205 SCIP_EVENTHDLRDATA* eventhdlrdata;
206
207 assert(scip != NULL);
208 assert(eventhdlr != NULL);
209
210 eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
211 assert(eventhdlrdata != NULL);
212
213 SCIPfreeBlockMemory(scip, &eventhdlrdata);
214
215 SCIPeventhdlrSetData(eventhdlr, NULL);
216
217 return SCIP_OKAY;
218}
219
220
221
222/* ---------------- Callback methods of node focus event handler ---------------- */
223
224/** exec the event handler */
225static
226SCIP_DECL_EVENTEXEC(eventExecBendersNodefocus)
227{ /*lint --e{715}*/
228 SCIP_EVENTHDLRDATA* eventhdlrdata;
229
230 assert(scip != NULL);
231 assert(eventhdlr != NULL);
232 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), NODEFOCUS_EVENTHDLR_NAME) == 0);
233
234 eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
235
236 /* sending an interrupt solve signal to return the control back to the Benders' decomposition plugin.
237 * This will ensure the SCIP stage is SCIP_STAGE_SOLVING, allowing the use of probing mode. */
239
240 SCIP_CALL(SCIPdropEvent(scip, SCIP_EVENTTYPE_NODEFOCUSED, eventhdlr, NULL, eventhdlrdata->filterpos));
241 eventhdlrdata->filterpos = -1;
242
243 return SCIP_OKAY;
244}
245
246/** solving process initialization method of event handler (called when branch and bound process is about to begin) */
247static
248SCIP_DECL_EVENTINITSOL(eventInitsolBendersNodefocus)
249{
250 assert(scip != NULL);
251 assert(eventhdlr != NULL);
252 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), NODEFOCUS_EVENTHDLR_NAME) == 0);
253
255
256 return SCIP_OKAY;
257}
258
259/** solving process deinitialization method of event handler (called before branch and bound process data is freed) */
260static
261SCIP_DECL_EVENTEXITSOL(eventExitsolBendersNodefocus)
262{
263 assert(scip != NULL);
264 assert(eventhdlr != NULL);
265 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), NODEFOCUS_EVENTHDLR_NAME) == 0);
266
268
269 return SCIP_OKAY;
270}
271
272/** deinitialization method of event handler (called before transformed problem is freed) */
273static
274SCIP_DECL_EVENTEXIT(eventExitBendersNodefocus)
275{
276 assert(scip != NULL);
277 assert(eventhdlr != NULL);
278 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), NODEFOCUS_EVENTHDLR_NAME) == 0);
279
280 SCIP_CALL( exitEventhandler(scip, eventhdlr) );
281
282 return SCIP_OKAY;
283}
284
285/** deinitialization method of event handler (called before transformed problem is freed) */
286static
287SCIP_DECL_EVENTFREE(eventFreeBendersNodefocus)
288{
289 assert(scip != NULL);
290 assert(eventhdlr != NULL);
291 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), NODEFOCUS_EVENTHDLR_NAME) == 0);
292
293 SCIP_CALL( freeEventhandler(scip, eventhdlr) );
294
295 return SCIP_OKAY;
296}
297
298
299/* ---------------- Callback methods of MIP solve node focus event handler ---------------- */
300
301/** exec the event handler */
302static
303SCIP_DECL_EVENTEXEC(eventExecBendersMipnodefocus)
304{ /*lint --e{715}*/
305 SCIP_EVENTHDLRDATA* eventhdlrdata;
306
307 assert(scip != NULL);
308 assert(eventhdlr != NULL);
309 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), MIPNODEFOCUS_EVENTHDLR_NAME) == 0);
310
311 eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
312
313 /* interrupting the solve so that the control is returned back to the Benders' core. */
314 if( eventhdlrdata->numruns == 0 && !eventhdlrdata->solvecip )
315 {
317 }
318
319 SCIP_CALL(SCIPdropEvent(scip, SCIP_EVENTTYPE_NODEFOCUSED, eventhdlr, NULL, eventhdlrdata->filterpos));
320 eventhdlrdata->filterpos = -1;
321
322 eventhdlrdata->numruns++;
323
324 return SCIP_OKAY;
325}
326
327/** solving process initialization method of event handler (called when branch and bound process is about to begin) */
328static
329SCIP_DECL_EVENTINITSOL(eventInitsolBendersMipnodefocus)
330{
331 assert(scip != NULL);
332 assert(eventhdlr != NULL);
333 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), MIPNODEFOCUS_EVENTHDLR_NAME) == 0);
334
336
337 return SCIP_OKAY;
338}
339
340/** solving process deinitialization method of event handler (called before branch and bound process data is freed) */
341static
342SCIP_DECL_EVENTEXITSOL(eventExitsolBendersMipnodefocus)
343{
344 assert(scip != NULL);
345 assert(eventhdlr != NULL);
346 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), MIPNODEFOCUS_EVENTHDLR_NAME) == 0);
347
349
350 return SCIP_OKAY;
351}
352
353/** deinitialization method of event handler (called before transformed problem is freed) */
354static
355SCIP_DECL_EVENTEXIT(eventExitBendersMipnodefocus)
356{
357 assert(scip != NULL);
358 assert(eventhdlr != NULL);
359 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), MIPNODEFOCUS_EVENTHDLR_NAME) == 0);
360
361 SCIP_CALL( exitEventhandler(scip, eventhdlr) );
362
363 return SCIP_OKAY;
364}
365
366/** deinitialization method of event handler (called before transformed problem is freed) */
367static
368SCIP_DECL_EVENTFREE(eventFreeBendersMipnodefocus)
369{
370 assert(scip != NULL);
371 assert(eventhdlr != NULL);
372 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), MIPNODEFOCUS_EVENTHDLR_NAME) == 0);
373
374 SCIP_CALL( freeEventhandler(scip, eventhdlr) );
375
376 return SCIP_OKAY;
377}
378
379/* ---------------- Callback methods of solution found event handler ---------------- */
380
381/** exec the event handler */
382static
383SCIP_DECL_EVENTEXEC(eventExecBendersUpperbound)
384{ /*lint --e{715}*/
385 SCIP_EVENTHDLRDATA* eventhdlrdata;
386 SCIP_SOL* bestsol;
387
388 assert(scip != NULL);
389 assert(eventhdlr != NULL);
390 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), UPPERBOUND_EVENTHDLR_NAME) == 0);
391
392 eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
393 assert(eventhdlrdata != NULL);
394
395 bestsol = SCIPgetBestSol(scip);
396
397 if( SCIPisLT(scip, SCIPgetSolOrigObj(scip, bestsol)*(int)SCIPgetObjsense(scip), eventhdlrdata->upperbound) )
398 {
400 }
401
402 return SCIP_OKAY;
403}
404
405/** solving process initialization method of event handler (called when branch and bound process is about to begin) */
406static
407SCIP_DECL_EVENTINITSOL(eventInitsolBendersUpperbound)
408{
409 assert(scip != NULL);
410 assert(eventhdlr != NULL);
411 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), UPPERBOUND_EVENTHDLR_NAME) == 0);
412
414
415 return SCIP_OKAY;
416}
417
418/** solving process deinitialization method of event handler (called before branch and bound process data is freed) */
419static
420SCIP_DECL_EVENTEXITSOL(eventExitsolBendersUpperbound)
421{
422 assert(scip != NULL);
423 assert(eventhdlr != NULL);
424 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), UPPERBOUND_EVENTHDLR_NAME) == 0);
425
427
428 return SCIP_OKAY;
429}
430
431/** deinitialization method of event handler (called before transformed problem is freed) */
432static
433SCIP_DECL_EVENTEXIT(eventExitBendersUpperbound)
434{
435 assert(scip != NULL);
436 assert(eventhdlr != NULL);
437 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), UPPERBOUND_EVENTHDLR_NAME) == 0);
438
439 SCIP_CALL( exitEventhandler(scip, eventhdlr) );
440
441 return SCIP_OKAY;
442}
443
444/** deinitialization method of event handler (called before transformed problem is freed) */
445static
446SCIP_DECL_EVENTFREE(eventFreeBendersUpperbound)
447{
448 assert(scip != NULL);
449 assert(eventhdlr != NULL);
450 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), UPPERBOUND_EVENTHDLR_NAME) == 0);
451
452 SCIP_CALL( freeEventhandler(scip, eventhdlr) );
453
454 return SCIP_OKAY;
455}
456
457/** updates the upper bound in the event handler data */
458static
460 SCIP_BENDERS* benders, /**< Benders' decomposition */
461 int probnumber, /**< the subproblem number */
462 SCIP_Real upperbound /**< the upper bound value */
463 )
464{
465 SCIP_EVENTHDLR* eventhdlr;
466 SCIP_EVENTHDLRDATA* eventhdlrdata;
467
468 assert(benders != NULL);
469 assert(probnumber >= 0 && probnumber < benders->nsubproblems);
470
471 eventhdlr = SCIPfindEventhdlr(SCIPbendersSubproblem(benders, probnumber), UPPERBOUND_EVENTHDLR_NAME);
472 assert(eventhdlr != NULL);
473
474 eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
475 assert(eventhdlrdata != NULL);
476
477 eventhdlrdata->upperbound = upperbound;
478
479 return SCIP_OKAY;
480}
481
482/* ---------------- Callback methods of the node solved event handler ---------------- */
483
484/** Updates the cut constant of the Benders' cuts data.
485 * This function solves the master problem with only the auxiliary variables in the objective function.
486 */
487static
489 SCIP* masterprob, /**< the SCIP instance of the master problem */
490 SCIP_BENDERS* benders /**< Benders' decomposition */
491 )
492{
493 SCIP_VAR** vars;
494 int nvars;
495 int nsubproblems;
496 int i;
497 SCIP_Bool lperror;
498 SCIP_Bool cutoff;
499
500 assert(masterprob != NULL);
501 assert(benders != NULL);
502
503 /* don't run in probing or in repropagation */
504 if( SCIPinProbing(masterprob) || SCIPinRepropagation(masterprob) || SCIPinDive(masterprob) )
505 return SCIP_OKAY;
506
507 nsubproblems = SCIPbendersGetNSubproblems(benders);
508
509 SCIP_CALL( SCIPstartProbing(masterprob) );
510
511 /* change the master problem variables to 0 */
512 nvars = SCIPgetNVars(masterprob);
513 vars = SCIPgetVars(masterprob);
514
515 /* setting the objective function coefficient to 0 for all variables */
516 for( i = 0; i < nvars; i++ )
517 {
519 {
520 SCIP_CALL( SCIPchgVarObjProbing(masterprob, vars[i], 0.0) );
521 }
522 }
523
524 /* solving an LP for all subproblems to find the lower bound */
525 for( i = 0; i < nsubproblems; i++)
526 {
527 SCIP_VAR* auxiliaryvar;
528
529 auxiliaryvar = SCIPbendersGetAuxiliaryVar(benders, i);
530
531 if( SCIPvarGetStatus(auxiliaryvar) != SCIP_VARSTATUS_COLUMN )
532 continue;
533
534 SCIP_CALL( SCIPchgVarObjProbing(masterprob, auxiliaryvar, 1.0) );
535
536 /* solving the probing LP to get a lower bound on the auxiliary variables */
537 SCIP_CALL( SCIPsolveProbingLP(masterprob, -1, &lperror, &cutoff) );
538
539 if( !SCIPisInfinity(masterprob, -SCIPgetSolTransObj(masterprob, NULL)) )
541
542 SCIPdebugMsg(masterprob, "Cut constant for subproblem %d: %g\n", i,
544
545 SCIP_CALL( SCIPchgVarObjProbing(masterprob, auxiliaryvar, 0.0) );
546 }
547
548 SCIP_CALL( SCIPendProbing(masterprob) );
549
550 return SCIP_OKAY;
551}
552
553/** exec the event handler */
554static
555SCIP_DECL_EVENTEXEC(eventExecBendersNodesolved)
556{ /*lint --e{715}*/
557 SCIP_BENDERS* benders;
558
559 assert(scip != NULL);
560 assert(eventhdlr != NULL);
561 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), NODESOLVED_EVENTHDLR_NAME) == 0);
562
563 benders = (SCIP_BENDERS*)SCIPeventhdlrGetData(eventhdlr); /*lint !e826*/
564
565 if( SCIPbendersGetNSubproblems(benders) > 0
567 {
569 }
570
572
573 return SCIP_OKAY;
574}
575
576/** solving process initialization method of event handler (called when branch and bound process is about to begin) */
577static
578SCIP_DECL_EVENTINITSOL(eventInitsolBendersNodesolved)
579{
580 SCIP_BENDERS* benders;
581
582 assert(scip != NULL);
583 assert(eventhdlr != NULL);
584 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), NODESOLVED_EVENTHDLR_NAME) == 0);
585
586 /* getting the Benders' decomposition data structure */
587 benders = (SCIP_BENDERS*)SCIPeventhdlrGetData(eventhdlr); /*lint !e826*/
588
589 /* The event is only caught if there is an active Benders' decomposition, the integer subproblem are solved and
590 * the Benders' decomposition has not been copied in thread safe mode
591 */
593 && !benders->threadsafe )
594 {
596 }
597
598 return SCIP_OKAY;
599}
600
601
602/* ---------------- Methods for the parallelisation of Benders' decomposition ---------------- */
603
604/** comparison method for sorting the subproblems.
605 * The subproblem that has been called the least is prioritised
606 */
607static
608SCIP_DECL_SORTPTRCOMP(benderssubcompdefault)
609{
610 SCIP_SUBPROBLEMSOLVESTAT* solvestat1;
611 SCIP_SUBPROBLEMSOLVESTAT* solvestat2;
612
613 assert(elem1 != NULL);
614 assert(elem2 != NULL);
615
616 solvestat1 = (SCIP_SUBPROBLEMSOLVESTAT*)elem1;
617 solvestat2 = (SCIP_SUBPROBLEMSOLVESTAT*)elem2;
618
619 /* prefer subproblems with fewer calls, using the index as tie breaker */
620 if( MAX(solvestat1->ncalls, solvestat2->ncalls) == 0 )
621 return solvestat1->idx - solvestat2->idx;
622 else if( solvestat1->ncalls != solvestat2->ncalls )
623 return solvestat1->ncalls - solvestat2->ncalls;
624 else
625 {
626 /* prefer the harder problem (with more average iterations) */
627 int avgiterdiff = (int)solvestat2->avgiter - (int)solvestat1->avgiter;
628
629 if( avgiterdiff != 0 )
630 return avgiterdiff;
631
632 return solvestat1->idx - solvestat2->idx;
633 }
634
635/* the code below does not give a total order of the elements */
636#ifdef SCIP_DISABLED_CODE
637 if( solvestat1->ncalls == 0 )
638 if( solvestat2->ncalls == 0 )
639 if( solvestat1->idx < solvestat2->idx )
640 return -1;
641 else
642 return 1;
643 else
644 return -1;
645 else if( solvestat2->ncalls == 0 )
646 return 1;
647 else
648 {
649 if( solvestat1->ncalls < solvestat2->ncalls )
650 return -1;
651 else if( solvestat2->ncalls < solvestat1->ncalls )
652 return 1;
653 else
654 {
655 /* we want to execute the hard subproblems first */
656 if( solvestat1->avgiter > solvestat2->avgiter )
657 return 1;
658 else
659 return -1;
660 }
661 }
662#endif
663}
664
665/* Local methods */
666
667/** A workaround for GCG. This is a temp vardata that is set for the auxiliary variables */
668struct SCIP_VarData
669{
670 int vartype; /**< the variable type. In GCG this indicates whether the variable is a
671 * master problem or subproblem variable. */
672};
673
674/** adds the auxiliary variables to the Benders' decomposition master problem */
675static
677 SCIP* scip, /**< SCIP data structure */
678 SCIP_BENDERS* benders /**< Benders' decomposition structure */
679 )
680{
681 SCIP_BENDERS* topbenders; /* the highest priority Benders' decomposition */
682 SCIP_VAR* auxiliaryvar;
683 SCIP_VARDATA* vardata;
684 char varname[SCIP_MAXSTRLEN]; /* the name of the auxiliary variable */
685 SCIP_Bool shareauxvars;
686 int i;
687
688 /* this is a workaround for GCG. GCG expects that the variable has vardata when added. So a dummy vardata is created */
689 SCIP_CALL( SCIPallocBlockMemory(scip, &vardata) );
690 vardata->vartype = -1;
691
692 /* getting the highest priority Benders' decomposition */
693 topbenders = SCIPgetBenders(scip)[0];
694
695 /* if the current Benders is the highest priority Benders, then we need to create the auxiliary variables.
696 * Otherwise, if the shareauxvars flag is set, then the auxiliary variables from the highest priority Benders' are
697 * stored with this Benders. */
698 shareauxvars = FALSE;
699 if( topbenders != benders && SCIPbendersShareAuxVars(benders) )
700 shareauxvars = TRUE;
701
702 for( i = 0; i < SCIPbendersGetNSubproblems(benders); i++ )
703 {
704 /* if the auxiliary variables are shared, then a pointer to the variable is retrieved from topbenders,
705 * otherwise the auxiliaryvariable is created. */
706 if( shareauxvars )
707 {
708 auxiliaryvar = SCIPbendersGetAuxiliaryVar(topbenders, i);
709
710 SCIP_CALL( SCIPcaptureVar(scip, auxiliaryvar) );
711 }
712 else
713 {
714 SCIP_VARTYPE vartype;
715
716 /* set the variable type of the auxiliary variables to implicit integer if the objective function of the
717 * subproblem is guaranteed to be integer. This behaviour is controlled through a user parameter.
718 * NOTE: It is only possible to determine if the objective function is integral if the subproblem is defined as
719 * a SCIP instance, i.e. not NULL.
720 */
721 if( benders->auxvarsimplint && SCIPbendersSubproblem(benders, i) != NULL
723 vartype = SCIP_VARTYPE_IMPLINT;
724 else
725 vartype = SCIP_VARTYPE_CONTINUOUS;
726
727 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "%s_%d_%s", AUXILIARYVAR_NAME, i, SCIPbendersGetName(benders) );
728 SCIP_CALL( SCIPcreateVarBasic(scip, &auxiliaryvar, varname, benders->subproblowerbound[i], SCIPinfinity(scip),
729 1.0, vartype) );
730
731 SCIPvarSetData(auxiliaryvar, vardata);
732
733 SCIP_CALL( SCIPaddVar(scip, auxiliaryvar) );
734
735 /* adding the down lock for the Benders' decomposition constraint handler */
736 SCIP_CALL( SCIPaddVarLocksType(scip, auxiliaryvar, SCIP_LOCKTYPE_MODEL, 1, 0) );
737 }
738
739 benders->auxiliaryvars[i] = auxiliaryvar;
740 }
741
742 SCIPfreeBlockMemory(scip, &vardata);
743
744 return SCIP_OKAY;
745}
746
747/** assigns the copied auxiliary variables in the target SCIP to the target Benders' decomposition data */
748static
750 SCIP* scip, /**< SCIP data structure, the target scip */
751 SCIP_BENDERS* benders /**< Benders' decomposition */
752 )
753{
754 SCIP_BENDERS* topbenders; /* the highest priority Benders' decomposition */
755 SCIP_VAR* targetvar;
756 SCIP_VARDATA* vardata;
757 char varname[SCIP_MAXSTRLEN]; /* the name of the auxiliary variable */
758 SCIP_Bool shareauxvars;
759 int subscipdepth;
760 int i;
761 int j;
762
763 assert(scip != NULL);
764 assert(benders != NULL);
765
766 /* this is a workaround for GCG. GCG expects that the variable has vardata when added. So a dummy vardata is created */
767 SCIP_CALL( SCIPallocBlockMemory(scip, &vardata) );
768 vardata->vartype = -1;
769
770 /* getting the highest priority Benders' decomposition */
771 topbenders = SCIPgetBenders(scip)[0];
772
773 /* if the auxiliary variable are shared, then the variable name will have a suffix of the highest priority Benders'
774 * name. So the shareauxvars flag indicates how to search for the auxiliary variables */
775 shareauxvars = FALSE;
776 if( topbenders != benders && SCIPbendersShareAuxVars(benders) )
777 shareauxvars = TRUE;
778
779 subscipdepth = SCIPgetSubscipDepth(scip);
780
781 for( i = 0; i < SCIPbendersGetNSubproblems(benders); i++ )
782 {
783 char prefix[SCIP_MAXSTRLEN];
784 char tmpprefix[SCIP_MAXSTRLEN];
785 int len = 1;
786
787 j = 0;
788 targetvar = NULL;
789
790 /* the prefix for the variable names is required for UG, since we don't know how many copies have been made. To
791 * find the target variable, we start with an empty prefix. Then t_ is prepended until the target variable is
792 * found
793 */
794 prefix[0] = '\0';
795 while( targetvar == NULL && j <= subscipdepth )
796 {
797 if( shareauxvars )
798 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "%s%s_%d_%s", prefix, AUXILIARYVAR_NAME, i, SCIPbendersGetName(topbenders));
799 else
800 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "%s%s_%d_%s", prefix, AUXILIARYVAR_NAME, i, SCIPbendersGetName(benders));
801
802 /* finding the variable in the copied problem that has the same name as the auxiliary variable */
803 targetvar = SCIPfindVar(scip, varname);
804
805 (void) SCIPsnprintf(tmpprefix, len, "t_%s", prefix);
806 len += 2;
807 (void) strncpy(prefix, tmpprefix, len); /*lint !e732*/
808
809 j++;
810 }
811
812 if( targetvar != NULL )
813 {
814 SCIPvarSetData(targetvar, vardata);
815
816 benders->auxiliaryvars[i] = SCIPvarGetTransVar(targetvar);
817
819 }
820 else
821 {
822 SCIPABORT();
823 }
824 }
825
826 SCIPfreeBlockMemory(scip, &vardata);
827
828 return SCIP_OKAY;
829}
830
831/** sets the subproblem objective value array to -infinity */
832static
834 SCIP_BENDERS* benders, /**< the Benders' decomposition structure */
835 SCIP_SET* set /**< global SCIP settings */
836 )
837{
838 SCIP* subproblem;
839 SCIP_Real inf;
840 int nsubproblems;
841 int i;
842
843 assert(benders != NULL);
844
845 nsubproblems = SCIPbendersGetNSubproblems(benders);
846
847 for( i = 0; i < nsubproblems; i++ )
848 {
849 subproblem = SCIPbendersSubproblem(benders, i);
850 if( subproblem != NULL )
851 inf = SCIPinfinity(subproblem);
852 else
853 inf = SCIPsetInfinity(set);
854
855 SCIPbendersSetSubproblemObjval(benders, i, inf);
856 }
857}
859/** compares two Benders' decompositions w. r. to their priority */
860SCIP_DECL_SORTPTRCOMP(SCIPbendersComp)
861{ /*lint --e{715}*/
862 return ((SCIP_BENDERS*)elem2)->priority - ((SCIP_BENDERS*)elem1)->priority;
863}
865/** comparison method for sorting Benders' decompositions w.r.t. to their name */
866SCIP_DECL_SORTPTRCOMP(SCIPbendersCompName)
867{
868 return strcmp(SCIPbendersGetName((SCIP_BENDERS*)elem1), SCIPbendersGetName((SCIP_BENDERS*)elem2));
869}
870
871/** method to call, when the priority of a Benders' decomposition was changed */
872static
873SCIP_DECL_PARAMCHGD(paramChgdBendersPriority)
874{ /*lint --e{715}*/
875 SCIP_PARAMDATA* paramdata;
876
877 paramdata = SCIPparamGetData(param);
878 assert(paramdata != NULL);
879
880 /* use SCIPsetBendersPriority() to mark the Benders' decompositions as unsorted */
881 SCIPsetBendersPriority(scip, (SCIP_BENDERS*)paramdata, SCIPparamGetInt(param)); /*lint !e740*/
882
883 return SCIP_OKAY;
884}
885
886/** creates a variable mapping between the master problem variables of the source scip and the sub scip */
887static
889 SCIP_BENDERS* benders, /**< Benders' decomposition of the target SCIP instance */
890 SCIP_SET* sourceset, /**< global SCIP settings from the source SCIP */
891 SCIP_HASHMAP* varmap /**< a hashmap to store the mapping of source variables corresponding
892 * target variables; must not be NULL */
893 )
894{
895 SCIP_VAR** vars;
896 SCIP_VAR* targetvar;
897 int nvars;
898 int i;
899
900 assert(benders != NULL);
901 assert(sourceset != NULL);
902 assert(benders->iscopy);
903 assert(benders->mastervarsmap == NULL);
904
905 /* getting the master problem variable data */
906 vars = SCIPgetVars(sourceset->scip);
907 nvars = SCIPgetNVars(sourceset->scip);
908
909 /* creating the hashmap for the mapping between the master variable of the target and source scip */
910 SCIP_CALL( SCIPhashmapCreate(&benders->mastervarsmap, SCIPblkmem(sourceset->scip), nvars) );
911
912 for( i = 0; i < nvars; i++ )
913 {
914 /* getting the variable pointer for the target SCIP variables. The variable mapping returns the target SCIP
915 * varibale for a given source SCIP variable. */
916 targetvar = (SCIP_VAR*) SCIPhashmapGetImage(varmap, vars[i]);
917 if( targetvar != NULL )
918 {
919 SCIP_CALL( SCIPhashmapInsert(benders->mastervarsmap, targetvar, vars[i]) );
920 SCIP_CALL( SCIPcaptureVar(sourceset->scip, vars[i]) );
921 }
922 }
923
924 return SCIP_OKAY;
925}
927/** copies the given Benders' decomposition to a new SCIP */
929 SCIP_BENDERS* benders, /**< Benders' decomposition */
930 SCIP_SET* sourceset, /**< SCIP_SET of SCIP to copy from */
931 SCIP_SET* targetset, /**< SCIP_SET of SCIP to copy to */
932 SCIP_HASHMAP* varmap, /**< a hashmap to store the mapping of source variables corresponding
933 * target variables; if NULL, then the transfer of cuts is not possible */
934 SCIP_Bool threadsafe, /**< must the Benders' decomposition copy be thread safe */
935 SCIP_Bool* valid /**< was the copying process valid? */
936 )
937{
938 SCIP_BENDERS* targetbenders; /* the copy of the Benders' decomposition struct in the target set */
939 int i;
940
941 assert(benders != NULL);
942 assert(targetset != NULL);
943 assert(valid != NULL);
944 assert(targetset->scip != NULL);
945
946 (*valid) = FALSE;
947
948 if( benders->benderscopy != NULL && targetset->benders_copybenders && SCIPbendersIsActive(benders) )
949 {
950 SCIPsetDebugMsg(targetset, "including Benders' decomposition %s in subscip %p\n", SCIPbendersGetName(benders), (void*)targetset->scip);
951 SCIP_CALL( benders->benderscopy(targetset->scip, benders, threadsafe) );
952
953 /* copying the Benders' cuts */
954 targetbenders = SCIPsetFindBenders(targetset, SCIPbendersGetName(benders));
955
956 /* storing the pointer to the source scip instance */
957 targetbenders->sourcescip = sourceset->scip;
958
959 /* the flag is set to indicate that the Benders' decomposition is a copy */
960 targetbenders->iscopy = TRUE;
961
962 /* storing whether the lnscheck should be performed */
963 targetbenders->lnscheck = benders->lnscheck;
964 targetbenders->lnsmaxdepth = benders->lnsmaxdepth;
965 targetbenders->lnsmaxcalls = benders->lnsmaxcalls;
966 targetbenders->lnsmaxcallsroot = benders->lnsmaxcallsroot;
967
968 /* storing whether the Benders' copy required thread safety */
969 targetbenders->threadsafe = threadsafe;
970
971 /* calling the copy method for the Benders' cuts */
973 for( i = 0; i < benders->nbenderscuts; i++ )
974 {
975 SCIP_CALL( SCIPbenderscutCopyInclude(targetbenders, benders->benderscuts[i], targetset) );
976 }
977
978 /* When the Benders' decomposition is copied then a variable mapping between the master problem variables is
979 * required. This variable mapping is used to transfer the cuts generated in the target SCIP to the source SCIP.
980 * The variable map is stored in the target Benders' decomposition. This will be freed when the sub-SCIP is freed.
981 */
982 if( varmap != NULL )
983 {
984 SCIP_CALL( createMasterVarMapping(targetbenders, sourceset, varmap) );
985 }
986
987 assert((varmap != NULL && targetbenders->mastervarsmap != NULL)
988 || (varmap == NULL && targetbenders->mastervarsmap == NULL));
989 }
990
991 /* if the Benders' decomposition is active, then copy is not valid. */
992 (*valid) = !SCIPbendersIsActive(benders);
993
994 return SCIP_OKAY;
995}
996
997/** internal method for creating a Benders' decomposition structure */
998static
1000 SCIP_BENDERS** benders, /**< pointer to Benders' decomposition data structure */
1001 SCIP_SET* set, /**< global SCIP settings */
1002 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
1003 BMS_BLKMEM* blkmem, /**< block memory for parameter settings */
1004 const char* name, /**< name of Benders' decomposition */
1005 const char* desc, /**< description of Benders' decomposition */
1006 int priority, /**< priority of the Benders' decomposition */
1007 SCIP_Bool cutlp, /**< should Benders' cuts be generated for LP solutions */
1008 SCIP_Bool cutpseudo, /**< should Benders' cuts be generated for pseudo solutions */
1009 SCIP_Bool cutrelax, /**< should Benders' cuts be generated for relaxation solutions */
1010 SCIP_Bool shareauxvars, /**< should this Benders' use the highest priority Benders aux vars */
1011 SCIP_DECL_BENDERSCOPY ((*benderscopy)), /**< copy method of Benders' decomposition or NULL if you don't want to copy your plugin into sub-SCIPs */
1012 SCIP_DECL_BENDERSFREE ((*bendersfree)), /**< destructor of Benders' decomposition */
1013 SCIP_DECL_BENDERSINIT ((*bendersinit)), /**< initialize Benders' decomposition */
1014 SCIP_DECL_BENDERSEXIT ((*bendersexit)), /**< deinitialize Benders' decomposition */
1015 SCIP_DECL_BENDERSINITPRE((*bendersinitpre)),/**< presolving initialization method for Benders' decomposition */
1016 SCIP_DECL_BENDERSEXITPRE((*bendersexitpre)),/**< presolving deinitialization method for Benders' decomposition */
1017 SCIP_DECL_BENDERSINITSOL((*bendersinitsol)),/**< solving process initialization method of Benders' decomposition */
1018 SCIP_DECL_BENDERSEXITSOL((*bendersexitsol)),/**< solving process deinitialization method of Benders' decomposition */
1019 SCIP_DECL_BENDERSGETVAR((*bendersgetvar)),/**< returns the master variable for a given subproblem variable */
1020 SCIP_DECL_BENDERSCREATESUB((*benderscreatesub)),/**< creates a Benders' decomposition subproblem */
1021 SCIP_DECL_BENDERSPRESUBSOLVE((*benderspresubsolve)),/**< called prior to the subproblem solving loop */
1022 SCIP_DECL_BENDERSSOLVESUBCONVEX((*benderssolvesubconvex)),/**< the solving method for convex Benders' decomposition subproblems */
1023 SCIP_DECL_BENDERSSOLVESUB((*benderssolvesub)),/**< the solving method for the Benders' decomposition subproblems */
1024 SCIP_DECL_BENDERSPOSTSOLVE((*benderspostsolve)),/**< called after the subproblems are solved. */
1025 SCIP_DECL_BENDERSFREESUB((*bendersfreesub)),/**< the freeing method for the Benders' decomposition subproblems */
1026 SCIP_BENDERSDATA* bendersdata /**< Benders' decomposition data */
1027 )
1028{
1030 char paramdesc[SCIP_MAXSTRLEN];
1031
1032 assert(benders != NULL);
1033 assert(name != NULL);
1034 assert(desc != NULL);
1035
1036 /* Checking whether the benderssolvesub and the bendersfreesub are both implemented or both are not implemented */
1037 if( (benderssolvesubconvex == NULL && benderssolvesub == NULL && bendersfreesub != NULL)
1038 || ((benderssolvesubconvex != NULL || benderssolvesub != NULL) && bendersfreesub == NULL) )
1039 {
1040 SCIPerrorMessage("Benders' decomposition <%s> requires that if bendersFreesub%s is implemented, then at least "
1041 "one of bendersSolvesubconvex%s or bendersSolvesub%s are implemented.\n", name, name, name, name);
1042 return SCIP_INVALIDCALL;
1043 }
1044
1045 SCIP_ALLOC( BMSallocMemory(benders) );
1046 BMSclearMemory(*benders);
1047 SCIP_ALLOC( BMSduplicateMemoryArray(&(*benders)->name, name, strlen(name)+1) );
1048 SCIP_ALLOC( BMSduplicateMemoryArray(&(*benders)->desc, desc, strlen(desc)+1) );
1049 (*benders)->priority = priority;
1050 (*benders)->cutlp = cutlp;
1051 (*benders)->cutpseudo = cutpseudo;
1052 (*benders)->cutrelax = cutrelax;
1053 (*benders)->shareauxvars = shareauxvars;
1054 (*benders)->benderscopy = benderscopy;
1055 (*benders)->bendersfree = bendersfree;
1056 (*benders)->bendersinit = bendersinit;
1057 (*benders)->bendersexit = bendersexit;
1058 (*benders)->bendersinitpre = bendersinitpre;
1059 (*benders)->bendersexitpre = bendersexitpre;
1060 (*benders)->bendersinitsol = bendersinitsol;
1061 (*benders)->bendersexitsol = bendersexitsol;
1062 (*benders)->bendersgetvar = bendersgetvar;
1063 (*benders)->benderscreatesub = benderscreatesub;
1064 (*benders)->benderspresubsolve = benderspresubsolve;
1065 (*benders)->benderssolvesubconvex = benderssolvesubconvex;
1066 (*benders)->benderssolvesub = benderssolvesub;
1067 (*benders)->benderspostsolve = benderspostsolve;
1068 (*benders)->bendersfreesub = bendersfreesub;
1069 (*benders)->bendersdata = bendersdata;
1070 SCIP_CALL( SCIPclockCreate(&(*benders)->setuptime, SCIP_CLOCKTYPE_DEFAULT) );
1071 SCIP_CALL( SCIPclockCreate(&(*benders)->bendersclock, SCIP_CLOCKTYPE_DEFAULT) );
1072 (*benders)->nlpparam = SCIP_NLPPARAM_DEFAULT(set->scip); /*lint !e446*/
1073
1074 /* add parameters */
1075 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/priority", name);
1076 (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "priority of Benders' decomposition <%s>", name);
1077 SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc,
1078 &(*benders)->priority, FALSE, priority, INT_MIN/4, INT_MAX/4,
1079 paramChgdBendersPriority, (SCIP_PARAMDATA*)(*benders)) ); /*lint !e740*/
1080
1081 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/cutlp", name);
1082 SCIP_CALL( SCIPsetAddBoolParam(set, messagehdlr, blkmem, paramname,
1083 "should Benders' cuts be generated for LP solutions?", &(*benders)->cutlp, FALSE, cutlp, NULL, NULL) ); /*lint !e740*/
1084
1085 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/cutpseudo", name);
1086 SCIP_CALL( SCIPsetAddBoolParam(set, messagehdlr, blkmem, paramname,
1087 "should Benders' cuts be generated for pseudo solutions?", &(*benders)->cutpseudo, FALSE, cutpseudo, NULL, NULL) ); /*lint !e740*/
1088
1089 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/cutrelax", name);
1090 SCIP_CALL( SCIPsetAddBoolParam(set, messagehdlr, blkmem, paramname,
1091 "should Benders' cuts be generated for relaxation solutions?", &(*benders)->cutrelax, FALSE, cutrelax, NULL, NULL) ); /*lint !e740*/
1092
1093 /* These parameters are left for the user to decide in a settings file. This departs from the usual SCIP convention
1094 * where the settings available at the creation of the plugin can be set in the function call.
1095 */
1096 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/transfercuts", name);
1097 SCIP_CALL( SCIPsetAddBoolParam(set, messagehdlr, blkmem, paramname,
1098 "should Benders' cuts from LNS heuristics be transferred to the main SCIP instance?", &(*benders)->transfercuts,
1099 FALSE, SCIP_DEFAULT_TRANSFERCUTS, NULL, NULL) ); /*lint !e740*/
1100
1101 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/lnscheck", name);
1102 SCIP_CALL( SCIPsetAddBoolParam(set, messagehdlr, blkmem, paramname,
1103 "should Benders' decomposition be used in LNS heurisics?", &(*benders)->lnscheck, FALSE, SCIP_DEFAULT_LNSCHECK,
1104 NULL, NULL) ); /*lint !e740*/
1105
1106 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/lnsmaxdepth", name);
1107 SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname,
1108 "maximum depth at which the LNS check is performed (-1: no limit)", &(*benders)->lnsmaxdepth, TRUE,
1110
1111 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/lnsmaxcalls", name);
1112 SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname,
1113 "the maximum number of Benders' decomposition calls in LNS heuristics (-1: no limit)", &(*benders)->lnsmaxcalls,
1114 TRUE, SCIP_DEFAULT_LNSMAXCALLS, -1, INT_MAX, NULL, NULL) );
1115
1116 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/lnsmaxcallsroot", name);
1117 SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname,
1118 "the maximum number of root node Benders' decomposition calls in LNS heuristics (-1: no limit)",
1119 &(*benders)->lnsmaxcallsroot, TRUE, SCIP_DEFAULT_LNSMAXCALLSROOT, -1, INT_MAX, NULL, NULL) );
1120
1121 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/cutsasconss", name);
1122 SCIP_CALL( SCIPsetAddBoolParam(set, messagehdlr, blkmem, paramname,
1123 "should the transferred cuts be added as constraints?", &(*benders)->cutsasconss, FALSE,
1124 SCIP_DEFAULT_CUTSASCONSS, NULL, NULL) ); /*lint !e740*/
1125
1126 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/subprobfrac", name);
1127 SCIP_CALL( SCIPsetAddRealParam(set, messagehdlr, blkmem, paramname,
1128 "fraction of subproblems that are solved in each iteration", &(*benders)->subprobfrac, FALSE,
1129 SCIP_DEFAULT_SUBPROBFRAC, 0.0, 1.0, NULL, NULL) ); /*lint !e740*/
1130
1131 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/updateauxvarbound", name);
1132 SCIP_CALL( SCIPsetAddBoolParam(set, messagehdlr, blkmem, paramname,
1133 "should the auxiliary variable bound be updated by solving the subproblem?", &(*benders)->updateauxvarbound,
1134 FALSE, SCIP_DEFAULT_UPDATEAUXVARBOUND, NULL, NULL) ); /*lint !e740*/
1135
1136 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/auxvarsimplint", name);
1137 SCIP_CALL( SCIPsetAddBoolParam(set, messagehdlr, blkmem, paramname,
1138 "if the subproblem objective is integer, then define the auxiliary variables as implicit integers?",
1139 &(*benders)->auxvarsimplint, FALSE, SCIP_DEFAULT_AUXVARSIMPLINT, NULL, NULL) ); /*lint !e740*/
1140
1141 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/cutcheck", name);
1142 SCIP_CALL( SCIPsetAddBoolParam(set, messagehdlr, blkmem, paramname,
1143 "should Benders' cuts be generated while checking solutions?",
1144 &(*benders)->cutcheck, FALSE, SCIP_DEFAULT_CUTCHECK, NULL, NULL) ); /*lint !e740*/
1145
1146 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/cutstrengthenmult", name);
1147 SCIP_CALL( SCIPsetAddRealParam(set, messagehdlr, blkmem, paramname,
1148 "the convex combination multiplier for the cut strengthening", &(*benders)->convexmult, FALSE,
1149 SCIP_DEFAULT_STRENGTHENMULT, 0.0, 1.0, NULL, NULL) ); /*lint !e740*/
1150
1151 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/noimprovelimit", name);
1152 SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname,
1153 "the maximum number of cut strengthening without improvement", &(*benders)->noimprovelimit, TRUE,
1154 SCIP_DEFAULT_NOIMPROVELIMIT, 0, INT_MAX, NULL, NULL) );
1155
1156 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/corepointperturb", name);
1157 SCIP_CALL( SCIPsetAddRealParam(set, messagehdlr, blkmem, paramname,
1158 "the constant use to perturb the cut strengthening core point", &(*benders)->perturbeps, FALSE,
1159 SCIP_DEFAULT_STRENGTHENPERTURB, 0.0, 1.0, NULL, NULL) ); /*lint !e740*/
1160
1161 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/cutstrengthenenabled", name);
1162 SCIP_CALL( SCIPsetAddBoolParam(set, messagehdlr, blkmem, paramname,
1163 "should the core point cut strengthening be employed (only applied to fractional solutions or continuous subproblems)?",
1164 &(*benders)->strengthenenabled, FALSE, SCIP_DEFAULT_STRENGTHENENABLED, NULL, NULL) ); /*lint !e740*/
1165
1166 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/cutstrengthenintpoint", name);
1167 SCIP_CALL( SCIPsetAddCharParam(set, messagehdlr, blkmem, paramname,
1168 "where should the strengthening interior point be sourced from ('l'p relaxation, 'f'irst solution, 'i'ncumbent solution, 'r'elative interior point, vector of 'o'nes, vector of 'z'eros)",
1169 &(*benders)->strengthenintpoint, FALSE, SCIP_DEFAULT_STRENGTHENINTPOINT, "lfiroz", NULL, NULL) ); /*lint !e740*/
1170
1171 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/numthreads", name);
1172 SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname,
1173 "the number of threads to use when solving the subproblems", &(*benders)->numthreads, TRUE,
1174 SCIP_DEFAULT_NUMTHREADS, 1, INT_MAX, NULL, NULL) );
1175
1176 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/execfeasphase", name);
1177 SCIP_CALL( SCIPsetAddBoolParam(set, messagehdlr, blkmem, paramname,
1178 "should a feasibility phase be executed during the root node, i.e. adding slack variables to constraints to ensure feasibility",
1179 &(*benders)->execfeasphase, FALSE, SCIP_DEFAULT_EXECFEASPHASE, NULL, NULL) ); /*lint !e740*/
1180
1181 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/slackvarcoef", name);
1182 SCIP_CALL( SCIPsetAddRealParam(set, messagehdlr, blkmem, paramname,
1183 "the initial objective coefficient of the slack variables in the subproblem", &(*benders)->slackvarcoef, FALSE,
1184 SCIP_DEFAULT_SLACKVARCOEF, 0.0, SCIPsetInfinity(set), NULL, NULL) ); /*lint !e740*/
1185
1186 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/maxslackvarcoef", name);
1187 SCIP_CALL( SCIPsetAddRealParam(set, messagehdlr, blkmem, paramname,
1188 "the maximal objective coefficient of the slack variables in the subproblem", &(*benders)->maxslackvarcoef, FALSE,
1189 SCIP_DEFAULT_MAXSLACKVARCOEF, 0.0, SCIPsetInfinity(set), NULL, NULL) ); /*lint !e740*/
1190
1191 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/checkconsconvexity", name);
1192 SCIP_CALL( SCIPsetAddBoolParam(set, messagehdlr, blkmem, paramname,
1193 "should the constraints of the subproblems be checked for convexity?", &(*benders)->checkconsconvexity, FALSE,
1194 SCIP_DEFAULT_CHECKCONSCONVEXITY, NULL, NULL) ); /*lint !e740*/
1195
1196 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/nlpiterlimit", name);
1197 SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname,
1198 "iteration limit for NLP solver", &(*benders)->nlpparam.iterlimit, FALSE,
1199 SCIP_DEFAULT_NLPITERLIMIT, 0, INT_MAX, NULL, NULL) ); /*lint !e740*/
1200
1201 return SCIP_OKAY;
1202}
1203
1204/** creates a Benders' decomposition structure
1205 *
1206 * To use the Benders' decomposition for solving a problem, it first has to be activated with a call to SCIPactivateBenders().
1207 */
1209 SCIP_BENDERS** benders, /**< pointer to Benders' decomposition data structure */
1210 SCIP_SET* set, /**< global SCIP settings */
1211 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
1212 BMS_BLKMEM* blkmem, /**< block memory for parameter settings */
1213 const char* name, /**< name of Benders' decomposition */
1214 const char* desc, /**< description of Benders' decomposition */
1215 int priority, /**< priority of the Benders' decomposition */
1216 SCIP_Bool cutlp, /**< should Benders' cuts be generated for LP solutions */
1217 SCIP_Bool cutpseudo, /**< should Benders' cuts be generated for pseudo solutions */
1218 SCIP_Bool cutrelax, /**< should Benders' cuts be generated for relaxation solutions */
1219 SCIP_Bool shareauxvars, /**< should this Benders' use the highest priority Benders aux vars */
1220 SCIP_DECL_BENDERSCOPY ((*benderscopy)), /**< copy method of Benders' decomposition or NULL if you don't want to copy your plugin into sub-SCIPs */
1221 SCIP_DECL_BENDERSFREE ((*bendersfree)), /**< destructor of Benders' decomposition */
1222 SCIP_DECL_BENDERSINIT ((*bendersinit)), /**< initialize Benders' decomposition */
1223 SCIP_DECL_BENDERSEXIT ((*bendersexit)), /**< deinitialize Benders' decomposition */
1224 SCIP_DECL_BENDERSINITPRE((*bendersinitpre)),/**< presolving initialization method for Benders' decomposition */
1225 SCIP_DECL_BENDERSEXITPRE((*bendersexitpre)),/**< presolving deinitialization method for Benders' decomposition */
1226 SCIP_DECL_BENDERSINITSOL((*bendersinitsol)),/**< solving process initialization method of Benders' decomposition */
1227 SCIP_DECL_BENDERSEXITSOL((*bendersexitsol)),/**< solving process deinitialization method of Benders' decomposition */
1228 SCIP_DECL_BENDERSGETVAR((*bendersgetvar)),/**< returns the master variable for a given subproblem variable */
1229 SCIP_DECL_BENDERSCREATESUB((*benderscreatesub)),/**< creates a Benders' decomposition subproblem */
1230 SCIP_DECL_BENDERSPRESUBSOLVE((*benderspresubsolve)),/**< called prior to the subproblem solving loop */
1231 SCIP_DECL_BENDERSSOLVESUBCONVEX((*benderssolvesubconvex)),/**< the solving method for convex Benders' decomposition subproblems */
1232 SCIP_DECL_BENDERSSOLVESUB((*benderssolvesub)),/**< the solving method for the Benders' decomposition subproblems */
1233 SCIP_DECL_BENDERSPOSTSOLVE((*benderspostsolve)),/**< called after the subproblems are solved. */
1234 SCIP_DECL_BENDERSFREESUB((*bendersfreesub)),/**< the freeing method for the Benders' decomposition subproblems */
1235 SCIP_BENDERSDATA* bendersdata /**< Benders' decomposition data */
1236 )
1237{
1238 assert(benders != NULL);
1239 assert(name != NULL);
1240 assert(desc != NULL);
1241
1242 SCIP_CALL_FINALLY( doBendersCreate(benders, set, messagehdlr, blkmem, name, desc, priority, cutlp, cutpseudo,
1243 cutrelax, shareauxvars, benderscopy, bendersfree, bendersinit, bendersexit, bendersinitpre, bendersexitpre,
1244 bendersinitsol, bendersexitsol, bendersgetvar, benderscreatesub, benderspresubsolve, benderssolvesubconvex,
1245 benderssolvesub, benderspostsolve, bendersfreesub, bendersdata), (void) SCIPbendersFree(benders, set) );
1246
1247 return SCIP_OKAY;
1248}
1249
1250
1251/** releases the variables that have been captured in the hashmap */
1252static
1254 SCIP* scip, /**< the SCIP data structure */
1255 SCIP_BENDERS* benders /**< Benders' decomposition */
1256 )
1257{
1258 int nentries;
1259 int i;
1260
1261 assert(scip != NULL);
1262 assert(benders != NULL);
1263
1264 assert(benders->mastervarsmap != NULL);
1265
1266 nentries = SCIPhashmapGetNEntries(benders->mastervarsmap);
1267
1268 for( i = 0; i < nentries; ++i )
1269 {
1270 SCIP_HASHMAPENTRY* entry;
1271 entry = SCIPhashmapGetEntry(benders->mastervarsmap, i);
1272
1273 if( entry != NULL )
1274 {
1275 SCIP_VAR* var;
1276 var = (SCIP_VAR*) SCIPhashmapEntryGetImage(entry);
1277
1278 SCIP_CALL( SCIPreleaseVar(scip, &var) );
1279 }
1280 }
1281
1282 return SCIP_OKAY;
1283}
1284
1286/** calls destructor and frees memory of Benders' decomposition */
1288 SCIP_BENDERS** benders, /**< pointer to Benders' decomposition data structure */
1289 SCIP_SET* set /**< global SCIP settings */
1290 )
1291{
1292 int i;
1293
1294 assert(benders != NULL);
1295 assert(*benders != NULL);
1296 assert(!(*benders)->initialized);
1297 assert(set != NULL);
1298
1299 /* call destructor of Benders' decomposition */
1300 if( (*benders)->bendersfree != NULL )
1301 {
1302 SCIP_CALL( (*benders)->bendersfree(set->scip, *benders) );
1303 }
1304
1305 /* if the Benders' decomposition is a copy and a varmap has been passed to SCIP_BENDERS, then the variable map
1306 * between the source and the target SCIP needs to be freed.
1307 */
1308 if( (*benders)->iscopy && (*benders)->mastervarsmap != NULL )
1309 {
1310 SCIP_CALL( releaseVarMappingHashmapVars((*benders)->sourcescip, (*benders)) );
1311 SCIPhashmapFree(&(*benders)->mastervarsmap);
1312 }
1313
1314 /* freeing the Benders' cuts */
1315 for( i = 0; i < (*benders)->nbenderscuts; i++ )
1316 {
1317 SCIP_CALL( SCIPbenderscutFree(&((*benders)->benderscuts[i]), set) );
1318 }
1319 BMSfreeMemoryArrayNull(&(*benders)->benderscuts);
1320
1321 SCIPclockFree(&(*benders)->bendersclock);
1322 SCIPclockFree(&(*benders)->setuptime);
1323 BMSfreeMemoryArray(&(*benders)->name);
1324 BMSfreeMemoryArray(&(*benders)->desc);
1325 BMSfreeMemory(benders);
1326
1327 return SCIP_OKAY;
1328}
1329
1330/* adds a slack variable to the given constraint */
1331static
1333 SCIP* scip, /**< the SCIP data structure */
1334 SCIP_BENDERS* benders, /**< Benders' decomposition */
1335 SCIP_CONS* cons, /**< constraint to which the slack variable(s) is added to */
1336 SCIP_CONSHDLR** linearconshdlrs, /**< an array storing the linear constraint handlers */
1337 SCIP_CONSHDLR* nlconshdlr, /**< pointer to the nonlinear constraint handler */
1338 int nlinearconshdlrs /**< the number of linear constraint handlers */
1339 )
1340{
1341 SCIP_CONSHDLR* conshdlr;
1342 SCIP_VAR* var;
1343 SCIP_Real rhs;
1344 SCIP_Real lhs;
1345 SCIP_Real objcoef;
1346 int i;
1347 SCIP_Bool linearcons;
1348 SCIP_Bool success;
1349 char name[SCIP_MAXSTRLEN];
1350
1351 conshdlr = SCIPconsGetHdlr(cons);
1352
1353 /* assume that the constraint is not linear, then we check whether it is linear */
1354 linearcons = FALSE;
1355
1356 /* checking whether the constraint is a linear constraint. If so, we add a coefficient to the constraint */
1357 for( i = 0; i < nlinearconshdlrs; ++i )
1358 {
1359 if( conshdlr == linearconshdlrs[i] )
1360 {
1361 linearcons = TRUE;
1362 break;
1363 }
1364 }
1365
1366 if( !linearcons && conshdlr != nlconshdlr )
1367 {
1368 SCIPwarningMessage(scip, "The subproblem includes constraint <%s>. "
1369 "This is not supported and the slack variable will not be added to the constraint. Feasibility cuts may be invalid.\n",
1370 SCIPconshdlrGetName(conshdlr));
1371 }
1372
1373 if( linearcons )
1374 {
1375 rhs = SCIPconsGetRhs(scip, cons, &success);
1376 assert(success);
1377 lhs = SCIPconsGetLhs(scip, cons, &success);
1378 assert(success);
1379 }
1380 else
1381 {
1382 rhs = SCIPgetRhsNonlinear(cons);
1383 lhs = SCIPgetLhsNonlinear(cons);
1384 }
1385
1386 /* getting the objective coefficient for the slack variables */
1387 objcoef = benders->slackvarcoef;
1388
1389 /* if the right hand side is finite, then we need to add a slack variable with a negative coefficient */
1390 if( !SCIPisInfinity(scip, rhs) )
1391 {
1392 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_%s_neg", SLACKVAR_NAME, SCIPconsGetName(cons) );
1393
1395
1396 /* adding the slack variable to the subproblem */
1397 SCIP_CALL( SCIPaddVar(scip, var) );
1398
1399 /* adds the slack variable to the constraint */
1400 if( linearcons )
1401 {
1402 SCIP_CALL( SCIPconsAddCoef(scip, cons, var, -1.0) );
1403 }
1404 else
1405 {
1406 SCIP_CALL( SCIPaddLinearVarNonlinear(scip, cons, var, -1.0) );
1407 }
1408
1409 /* releasing the variable */
1410 SCIP_CALL( SCIPreleaseVar(scip, &var) );
1411 }
1412
1413 /* if the left hand side if finite, then we need to add a slack variable with a positive coefficient */
1414 if( !SCIPisInfinity(scip, -lhs) )
1415 {
1416 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_%s_pos", SLACKVAR_NAME, SCIPconsGetName(cons) );
1417
1419
1420 /* adding the slack variable to the subproblem */
1421 SCIP_CALL( SCIPaddVar(scip, var) );
1422
1423 /* adds the slack variable to the constraint */
1424 if( linearcons )
1425 {
1426 SCIP_CALL( SCIPconsAddCoef(scip, cons, var, 1.0) );
1427 }
1428 else
1429 {
1430 SCIP_CALL( SCIPaddLinearVarNonlinear(scip, cons, var, 1.0) );
1431 }
1432
1433 /* releasing the variable */
1434 SCIP_CALL( SCIPreleaseVar(scip, &var) );
1435 }
1436
1437 return SCIP_OKAY;
1438}
1439
1440/** adds the slack variables to each of the constraints for the generation of feasibility cuts for the given non-linear
1441 * subproblem
1443static
1445 SCIP_BENDERS* benders, /**< Benders' decomposition */
1446 SCIP_SET* set, /**< global SCIP settings */
1447 int probnumber /**< the subproblem number */
1448 )
1449{
1450 SCIP* subproblem;
1451 SCIP_CONSHDLR* linearconshdlrs[NLINEARCONSHDLRS];
1452 SCIP_CONSHDLR* nlconshdlr;
1453 SCIP_CONS* cons;
1454 int i;
1455
1456 assert(benders != NULL);
1457 assert(set != NULL);
1458 assert(probnumber >= 0 && probnumber < SCIPbendersGetNSubproblems(benders));
1459
1460 subproblem = SCIPbendersSubproblem(benders, probnumber);
1461
1462 /* get pointers to linear constraints handlers, so can avoid string comparisons */
1463 linearconshdlrs[0] = SCIPfindConshdlr(subproblem, "knapsack");
1464 linearconshdlrs[1] = SCIPfindConshdlr(subproblem, "linear");
1465 linearconshdlrs[2] = SCIPfindConshdlr(subproblem, "logicor");
1466 linearconshdlrs[3] = SCIPfindConshdlr(subproblem, "setppc");
1467 linearconshdlrs[4] = SCIPfindConshdlr(subproblem, "varbound");
1468
1469 nlconshdlr = SCIPfindConshdlr(subproblem, "nonlinear");
1470
1471 for( i = 0; i < SCIPgetNOrigConss(subproblem); ++i )
1472 {
1473 cons = SCIPgetOrigConss(subproblem)[i];
1474
1475 /* adding the slack variables to the constraint */
1476 SCIP_CALL( addSlackVars(subproblem, benders, cons, linearconshdlrs, nlconshdlr, NLINEARCONSHDLRS) );
1477 }
1478
1479 return SCIP_OKAY;
1480}
1481
1482/** initialises a MIP subproblem by putting the problem into SCIP_STAGE_SOLVING. This is achieved by calling SCIPsolve
1483 * and then interrupting the solve in a node focus event handler.
1484 * The LP subproblem is also initialised using this method; however, a different event handler is added. This event
1485 * handler will put the LP subproblem into probing mode.
1486 * The MIP solving function is called to initialise the subproblem because this function calls SCIPsolve with the
1487 * appropriate parameter settings for Benders' decomposition.
1489static
1491 SCIP_BENDERS* benders, /**< Benders' decomposition */
1492 SCIP_SET* set, /**< global SCIP settings */
1493 int probnumber, /**< the subproblem number */
1494 SCIP_Bool* infeasible, /**< pointer to store whether the lp is detected as infeasible */
1495 SCIP_Bool* success /**< was the initialisation process successful */
1496 )
1497{
1498 SCIP* subproblem;
1499 SCIP_STATUS solvestatus;
1500
1501 assert(benders != NULL);
1502 assert(probnumber >= 0 && probnumber < SCIPbendersGetNSubproblems(benders));
1503 assert(success != NULL);
1504
1505 (*success) = FALSE;
1506 (*infeasible) = FALSE;
1507
1508 subproblem = SCIPbendersSubproblem(benders, probnumber);
1509 assert(subproblem != NULL);
1510
1511 /* Getting the problem into the right SCIP stage for solving */
1512 SCIP_CALL( SCIPbendersSolveSubproblemCIP(set->scip, benders, probnumber, &solvestatus, FALSE) );
1513
1514 /* Constructing the LP that can be solved in later iterations */
1515 if( solvestatus != SCIP_STATUS_BESTSOLLIMIT && solvestatus != SCIP_STATUS_TIMELIMIT
1516 && solvestatus != SCIP_STATUS_MEMLIMIT )
1517 {
1518 assert(SCIPgetStage(subproblem) == SCIP_STAGE_SOLVING);
1519
1520 SCIP_CALL( SCIPconstructLP(subproblem, infeasible) );
1521
1522 (*success) = !(*infeasible);
1523 }
1524
1525 return SCIP_OKAY;
1526}
1527
1528
1529/** initialises an LP subproblem by putting the problem into probing mode. The probing mode is invoked in a node focus
1530 * event handler. This event handler is added just prior to calling the initialise subproblem function.
1532static
1534 SCIP_BENDERS* benders, /**< Benders' decomposition */
1535 SCIP_SET* set, /**< global SCIP settings */
1536 int probnumber, /**< the subproblem number */
1537 SCIP_Bool* infeasible /**< pointer to store whether the lp is detected as infeasible */
1538 )
1539{
1540 SCIP* subproblem;
1541 SCIP_EVENTHDLR* eventhdlr;
1542 SCIP_EVENTHDLRDATA* eventhdlrdata;
1543 SCIP_Bool success;
1544
1545 assert(benders != NULL);
1546 assert(probnumber >= 0 && probnumber < SCIPbendersGetNSubproblems(benders));
1547 assert(infeasible != NULL);
1548
1549 subproblem = SCIPbendersSubproblem(benders, probnumber);
1550 assert(subproblem != NULL);
1551
1552 /* include event handler into SCIP */
1553 SCIP_CALL( SCIPallocBlockMemory(subproblem, &eventhdlrdata) );
1554
1555 SCIP_CALL( initEventhandlerData(subproblem, eventhdlrdata) );
1556
1558 eventExecBendersNodefocus, eventhdlrdata) );
1559 SCIP_CALL( SCIPsetEventhdlrInitsol(subproblem, eventhdlr, eventInitsolBendersNodefocus) );
1560 SCIP_CALL( SCIPsetEventhdlrExitsol(subproblem, eventhdlr, eventExitsolBendersNodefocus) );
1561 SCIP_CALL( SCIPsetEventhdlrExit(subproblem, eventhdlr, eventExitBendersNodefocus) );
1562 SCIP_CALL( SCIPsetEventhdlrFree(subproblem, eventhdlr, eventFreeBendersNodefocus) );
1563 assert(eventhdlr != NULL);
1564
1565 /* calling an initial solve to put the problem into probing mode */
1566 SCIP_CALL( initialiseSubproblem(benders, set, probnumber, infeasible, &success) );
1567
1568 return SCIP_OKAY; /*lint !e438*/
1569}
1570
1571/** checks whether the convex relaxation of the subproblem is sufficient to solve the original problem to optimality
1572 *
1573 * We check whether we can conclude that the CIP is actually an LP or a convex NLP.
1574 * To do this, we check that all variables are of continuous type and that every constraint is either handled by known
1575 * linear constraint handler (knapsack, linear, logicor, setppc, varbound) or the nonlinear constraint handler.
1576 * In the latter case, we also check whether the nonlinear constraint is convex.
1577 * Further, nonlinear constraints are only considered if an NLP solver interface is available, i.e., and NLP could
1578 * be solved.
1579 * If constraints are present that cannot be identified as linear or convex nonlinear, then we assume that the
1580 * problem is not convex, thus solving its LP or NLP relaxation will not be sufficient.
1582static
1584 SCIP_BENDERS* benders, /**< Benders' decomposition */
1585 SCIP_SET* set, /**< global SCIP settings */
1586 int probnumber /**< the subproblem number, or -1 for the master problem */
1587 )
1588{
1589 SCIP* subproblem;
1590 SCIP_CONSHDLR* conshdlr;
1591 SCIP_CONS* cons;
1592 SCIP_HASHMAP* assumevarfixed;
1593 SCIP_VAR** vars;
1594 int nvars;
1595 int nbinvars;
1596 int nintvars;
1597 int nimplintvars;
1598 int i;
1599 int j;
1600 SCIP_Bool convexcons;
1601 SCIP_Bool discretevar;
1602 SCIP_Bool isnonlinear;
1603 SCIP_CONSHDLR* linearconshdlrs[NLINEARCONSHDLRS];
1604 SCIP_CONSHDLR* nlconshdlr = NULL;
1605
1606 assert(benders != NULL);
1607 assert(set != NULL);
1608 assert(probnumber >= -1 && probnumber < SCIPbendersGetNSubproblems(benders));
1609
1610 assumevarfixed = NULL;
1611 if( probnumber >= 0 )
1612 subproblem = SCIPbendersSubproblem(benders, probnumber);
1613 else
1614 subproblem = set->scip;
1615
1616 assert(subproblem != NULL);
1617
1618 convexcons = FALSE;
1619 discretevar = FALSE;
1620 isnonlinear = FALSE;
1621
1622 /* getting the number of integer and binary variables to determine the problem type */
1623 SCIP_CALL( SCIPgetVarsData(subproblem, &vars, &nvars, &nbinvars, &nintvars, &nimplintvars, NULL) );
1624
1625 /* if there are any binary, integer or implicit integer variables, then the subproblems is marked as non-convex */
1626 if( nbinvars != 0 || nintvars != 0 || nimplintvars != 0 )
1627 {
1628 discretevar = TRUE;
1629 }
1630
1631 /* get pointers to linear constraints handlers, so can avoid string comparisons */
1632 linearconshdlrs[0] = SCIPfindConshdlr(subproblem, "knapsack");
1633 linearconshdlrs[1] = SCIPfindConshdlr(subproblem, "linear");
1634 linearconshdlrs[2] = SCIPfindConshdlr(subproblem, "logicor");
1635 linearconshdlrs[3] = SCIPfindConshdlr(subproblem, "setppc");
1636 linearconshdlrs[4] = SCIPfindConshdlr(subproblem, "varbound");
1637
1638 /* Get pointer to the nonlinear constraint handler if we also have an NLP solver to solve NLPs.
1639 * If there is no NLP solver, but there are (convex) nonlinear constraints, then the LP relaxation of subproblems
1640 * will (currently) not be sufficient to solve subproblems to optimality. Thus, we also take the presence of convex
1641 * nonlinear constraints as signal for having to solve the CIP eventually, thus, by abuse of notation,
1642 * return not-convex here. In summary, we do not need to have a special look onto non-linear constraints
1643 * if no NLP solver is present, and can treat them as any other constraint that is not of linear type.
1644 */
1645 if( SCIPgetNNlpis(subproblem) > 0 )
1646 {
1647 nlconshdlr = SCIPfindConshdlr(subproblem, "nonlinear");
1648 }
1649
1650 /* if the nonlinear constraint handler exists, then we create a hashmap of variables that can be assumed to be fixed.
1651 * These variables correspond to the copies of the master variables in the subproblem
1652 */
1653 if( probnumber >= 0 && nlconshdlr != NULL )
1654 {
1655 SCIP_VAR* mappedvar;
1656
1657 SCIP_CALL( SCIPhashmapCreate(&assumevarfixed, SCIPblkmem(set->scip), SCIPgetNVars(subproblem)) );
1658
1659 /* finding the subproblem variables that correspond to master variables */
1660 for( i = 0; i < nvars; i++ )
1661 {
1662 /* getting the corresponding master problem variable for the given variable */
1663 SCIP_CALL( SCIPbendersGetVar(benders, set, vars[i], &mappedvar, -1) );
1664
1665 /* if the mapped variable is not NULL, then it must be stored as a possible fixed variable */
1666 if( mappedvar != NULL )
1667 {
1668 SCIP_CALL( SCIPhashmapInsert(assumevarfixed, vars[i], vars[i]) );
1669 }
1670 }
1671 }
1672
1673 for( i = 0; i < SCIPgetNOrigConss(subproblem); ++i )
1674 {
1675 cons = SCIPgetOrigConss(subproblem)[i];
1676 conshdlr = SCIPconsGetHdlr(cons);
1677
1678 for( j = 0; j < NLINEARCONSHDLRS; ++j )
1679 if( conshdlr == linearconshdlrs[j] )
1680 break;
1681
1682 /* if linear constraint, then we are good */
1683 if( j < NLINEARCONSHDLRS )
1684 {
1685#ifdef SCIP_MOREDEBUG
1686 SCIPdebugMsg(subproblem, "subproblem <%s>: constraint <%s> is linear\n", SCIPgetProbName(subproblem), SCIPconsGetName(cons));
1687#endif
1688 continue;
1689 }
1690
1691 /* if cons_nonlinear (and nlconshdlr != NULL), then check whether convex */
1692 if( conshdlr == nlconshdlr )
1693 {
1694 SCIP_Bool isconvex;
1695 SCIP_EXPRCURV curv;
1696 SCIP_Bool havelhs;
1697 SCIP_Bool haverhs;
1698
1699 isnonlinear = TRUE;
1700
1701 havelhs = !SCIPisInfinity(subproblem, -SCIPgetLhsNonlinear(cons));
1702 haverhs = !SCIPisInfinity(subproblem, SCIPgetRhsNonlinear(cons));
1703 if( havelhs && haverhs )
1704 {
1705 isconvex = FALSE;
1706 }
1707 else
1708 {
1709 /* look at curvature stored in cons, though at this stage this will be unknown a.a. */
1710 curv = SCIPgetCurvatureNonlinear(cons);
1711 isconvex = ((!havelhs || (curv & SCIP_EXPRCURV_CONCAVE) == SCIP_EXPRCURV_CONCAVE)) &&
1712 ((!haverhs || (curv & SCIP_EXPRCURV_CONVEX) == SCIP_EXPRCURV_CONVEX));
1713
1714 if( !isconvex )
1715 {
1716 /* if not found convex, compute curvature via nlhdlr_convex and decide again */
1717
1718 /* make sure activities are up to date. SCIPhasExprCurvature currently assumes that this is already the case */
1720
1721 SCIP_CALL( SCIPhasExprCurvature(subproblem, SCIPgetExprNonlinear(cons), havelhs ? SCIP_EXPRCURV_CONCAVE : SCIP_EXPRCURV_CONVEX, &isconvex, assumevarfixed) );
1722 }
1723 }
1724
1725 if( isconvex )
1726 {
1727#ifdef SCIP_MOREDEBUG
1728 SCIPdebugMsg(subproblem, "subproblem <%s>: nonlinear constraint <%s> is convex\n", SCIPgetProbName(subproblem), SCIPconsGetName(cons));
1729#endif
1730 continue;
1731 }
1732 else
1733 {
1734#ifdef SCIP_MOREDEBUG
1735 SCIPdebugMsg(subproblem, "subproblem <%s>: nonlinear constraint <%s> not convex\n", SCIPgetProbName(subproblem), SCIPconsGetName(cons));
1736#endif
1737 goto TERMINATE;
1738 }
1739 }
1740
1741#ifdef SCIP_MOREDEBUG
1742 SCIPdebugMsg(subproblem, "subproblem <%s>: potentially nonconvex constraint <%s>\n", SCIPgetProbName(subproblem), SCIPconsGetName(cons));
1743#endif
1744 goto TERMINATE;
1745 }
1746
1747 /* if we made it until here, then all constraints are known and convex */
1748 convexcons = TRUE;
1749
1750TERMINATE:
1751 /* setting the flag for the convexity of the subproblem. If convexity doesn't need to be checked, then it is assumed
1752 * that the subproblems are convex. However, if there are discrete variables, then the problem must be set as
1753 * non-convex. The discrete master variables will be changed to continuous, but this will happen at the first call to
1754 * SCIPbendersSetupSubproblem
1755 */
1756 if( probnumber >= 0 )
1757 {
1758 convexcons = convexcons || !benders->checkconsconvexity;
1759
1760 if( convexcons && !discretevar )
1762 else if( convexcons && discretevar )
1764 else if( !convexcons && !discretevar )
1766 else if( !convexcons && discretevar )
1768 else
1769 SCIPABORT();
1770 }
1771
1772 /* setting the non-linear subproblem flag */
1773 if( probnumber >= 0 )
1774 SCIPbendersSetSubproblemIsNonlinear(benders, probnumber, isnonlinear);
1775 else
1776 SCIPbendersSetMasterIsNonlinear(benders, isnonlinear);
1777
1778 if( probnumber >= 0 )
1779 {
1780 SCIPsetDebugMsg(set, "subproblem <%s> has been found to be of type %d\n", SCIPgetProbName(subproblem),
1781 SCIPbendersGetSubproblemType(benders, probnumber));
1782 }
1783
1784 /* releasing the fixed variable hashmap */
1785 if( assumevarfixed != NULL )
1786 SCIPhashmapFree(&assumevarfixed);
1787
1788 return SCIP_OKAY;
1789}
1790
1791/** creates the subproblems and registers it with the Benders' decomposition struct */
1792static
1794 SCIP_BENDERS* benders, /**< Benders' decomposition */
1795 SCIP_SET* set /**< global SCIP settings */
1796 )
1797{
1798 SCIP* subproblem;
1799 SCIP_EVENTHDLR* eventhdlr;
1800 SCIP_VAR* mastervar;
1801 SCIP_VAR** vars;
1802 int nvars;
1803 int nsubproblems;
1804 int i;
1805 int j;
1806
1807 assert(benders != NULL);
1808 assert(set != NULL);
1809
1810 /* if the subproblems have already been created, then they will not be created again. This is the case if the
1811 * transformed problem has been freed and then retransformed. The subproblems should only be created when the problem
1812 * is first transformed. */
1813 if( benders->subprobscreated )
1814 return SCIP_OKAY;
1815
1816 nsubproblems = SCIPbendersGetNSubproblems(benders);
1817
1818 /* creating all subproblems */
1819 for( i = 0; i < nsubproblems; i++ )
1820 {
1821 /* calling the create subproblem call back method */
1822 SCIP_CALL( benders->benderscreatesub(set->scip, benders, i) );
1823
1824 subproblem = SCIPbendersSubproblem(benders, i);
1825
1826 /* the subproblem SCIP instance could be set to NULL. This is because user defined subproblem solving methods
1827 * could be used that don't solve a SCIP instance. Thus, the following setup of the subproblem SCIP instance is
1828 * not required.
1829 *
1830 * NOTE: since the subproblems are supplied as NULL pointers, the internal convexity check can not be performed.
1831 * The user needs to explicitly specify the subproblem type.
1832 */
1833 if( subproblem != NULL )
1834 {
1835 /* setting global limits for the subproblems. This overwrites the limits set by the user */
1836 SCIP_CALL( SCIPsetIntParam(subproblem, "limits/maxorigsol", 0) );
1837
1838 /* getting the number of integer and binary variables to determine the problem type */
1839 SCIP_CALL( SCIPgetVarsData(subproblem, &vars, &nvars, NULL, NULL, NULL, NULL) );
1840
1841 /* The objective function coefficients of the master problem are set to zero. This is necessary for the Benders'
1842 * decomposition algorithm, since the cut methods and the objective function check assumes that the objective
1843 * coefficients of the master problem variables are zero.
1844 *
1845 * This only occurs if the Benders' decomposition is not a copy. It is assumed that the correct objective
1846 * coefficients are given during the first subproblem creation.
1847 *
1848 * If the subproblems were copied, then the master variables will be checked to ensure that they have a zero
1849 * objective value.
1850 */
1851 if( !benders->iscopy || benders->threadsafe )
1852 {
1853 SCIP_Bool objchanged = FALSE;
1854
1855 assert(SCIPgetStage(subproblem) == SCIP_STAGE_PROBLEM);
1856 for( j = 0; j < nvars; j++ )
1857 {
1858 /* retrieving the master problem variable */
1859 SCIP_CALL( SCIPbendersGetVar(benders, set, vars[j], &mastervar, -1) );
1860
1861 /* if mastervar is not NULL, then the subproblem variable has a corresponding master problem variable */
1862 if( mastervar != NULL && SCIPvarGetObj(vars[j]) != 0.0 )
1863 {
1864 SCIPverbMessage(subproblem, SCIP_VERBLEVEL_FULL, NULL, "Benders' decomposition: Changing the objective "
1865 "coefficient of copy of master problem variable <%s> in subproblem %d to zero.\n",
1866 SCIPvarGetName(mastervar), i);
1867 /* changing the subproblem variable objective coefficient to zero */
1868 SCIP_CALL( SCIPchgVarObj(subproblem, vars[j], 0.0) );
1869
1870 objchanged = TRUE;
1871 }
1872 }
1873
1874 if( objchanged )
1875 {
1876 SCIPverbMessage(subproblem, SCIP_VERBLEVEL_HIGH, NULL, "Benders' decomposition: Objective coefficients of "
1877 "copied of master problem variables has been changed to zero.\n");
1878 }
1879 }
1880
1881 /* changing all of the master problem variable to continuous. */
1883
1884 /* checking the convexity of the subproblem. The convexity of the subproblem indicates whether the convex
1885 * relaxation is a valid relaxation for the problem
1886 */
1887 SCIP_CALL( checkSubproblemConvexity(benders, set, i) );
1888
1889 /* if the problem is convex and has nonlinear constraints, then slack variables must be added to each of the
1890 * constraints
1891 */
1892 if( benders->execfeasphase ||
1894 && SCIPbendersSubproblemIsNonlinear(benders, i)) )
1895 {
1896 /* the slack variables are only added to the subproblem once. If the initialisation methods are called from a
1897 * copy, then the slack variables are not re-added. Alternatively, if the copy must be threadsafe, then the
1898 * subproblems are created from scratch again, so the slack variables need to be added.
1899 */
1900 if( !benders->iscopy || benders->threadsafe )
1901 {
1902 SCIP_CALL( addSlackVarsToConstraints(benders, set, i) );
1903 }
1904
1905 /* setting the flag to indicate that slack variables have been added to the subproblem constraints. This is only
1906 * set if the slack variables have been added at the request of the user.
1907 */
1908 if( benders->execfeasphase )
1909 benders->feasibilityphase = TRUE;
1910 }
1911
1912 /* after checking the subproblem for convexity, if the subproblem has convex constraints and continuous variables,
1913 * then the problem is entered into probing mode. Otherwise, it is initialised as a CIP
1914 */
1916 {
1917 /* if the user has not implemented a solve subproblem callback, then the subproblem solves are performed
1918 * internally. To be more efficient the subproblem is put into probing mode. */
1919 if( benders->benderssolvesubconvex == NULL && benders->benderssolvesub == NULL
1920 && SCIPgetStage(subproblem) <= SCIP_STAGE_PROBLEM )
1921 {
1922 SCIP_Bool infeasible;
1923 SCIP_CALL( initialiseLPSubproblem(benders, set, i, &infeasible) );
1924
1925 /* if the initialisation process indicates that the LP is infeasible, then the complete problem is
1926 * infeasible. The subprobsinfeasible flag is set so that SCIP can be informed at the correct point
1927 * during the solving process.
1928 */
1929 if( infeasible )
1931 }
1932 }
1933 else
1934 {
1935 SCIP_EVENTHDLRDATA* eventhdlrdata_mipnodefocus;
1936 SCIP_EVENTHDLRDATA* eventhdlrdata_upperbound;
1937
1938 /* because the subproblems could be reused in the copy, the event handler is not created again. If the
1939 * threadsafe is TRUE, then it is assumed that the subproblems are not reused.
1940 * NOTE: This currently works with the benders_default implementation. It may not be very general. */
1941 if( benders->benderssolvesubconvex == NULL && benders->benderssolvesub == NULL
1942 && (!benders->iscopy || benders->threadsafe) )
1943 {
1944 SCIP_CALL( SCIPallocBlockMemory(subproblem, &eventhdlrdata_mipnodefocus) );
1945 SCIP_CALL( SCIPallocBlockMemory(subproblem, &eventhdlrdata_upperbound) );
1946
1947 SCIP_CALL( initEventhandlerData(subproblem, eventhdlrdata_mipnodefocus) );
1948 SCIP_CALL( initEventhandlerData(subproblem, eventhdlrdata_upperbound) );
1949
1950 /* include the first LP solved event handler into the subproblem */
1952 MIPNODEFOCUS_EVENTHDLR_DESC, eventExecBendersMipnodefocus, eventhdlrdata_mipnodefocus) );
1953 SCIP_CALL( SCIPsetEventhdlrInitsol(subproblem, eventhdlr, eventInitsolBendersMipnodefocus) );
1954 SCIP_CALL( SCIPsetEventhdlrExitsol(subproblem, eventhdlr, eventExitsolBendersMipnodefocus) );
1955 SCIP_CALL( SCIPsetEventhdlrExit(subproblem, eventhdlr, eventExitBendersMipnodefocus) );
1956 SCIP_CALL( SCIPsetEventhdlrFree(subproblem, eventhdlr, eventFreeBendersMipnodefocus) );
1957 assert(eventhdlr != NULL);
1958
1959 /* include the upper bound interrupt event handler into the subproblem */
1961 UPPERBOUND_EVENTHDLR_DESC, eventExecBendersUpperbound, eventhdlrdata_upperbound) );
1962 SCIP_CALL( SCIPsetEventhdlrInitsol(subproblem, eventhdlr, eventInitsolBendersUpperbound) );
1963 SCIP_CALL( SCIPsetEventhdlrExitsol(subproblem, eventhdlr, eventExitsolBendersUpperbound) );
1964 SCIP_CALL( SCIPsetEventhdlrExit(subproblem, eventhdlr, eventExitBendersUpperbound) );
1965 SCIP_CALL( SCIPsetEventhdlrFree(subproblem, eventhdlr, eventFreeBendersUpperbound) );
1966 assert(eventhdlr != NULL);
1967 }
1968 }
1969 }
1970 else
1971 {
1972 /* a user must specify the subproblem type if they are not supplying a SCIP instance. */
1974 {
1975 SCIPerrorMessage("If the subproblem is set to NULL, then the subproblem type must be specified.\n");
1976 SCIPerrorMessage("In the subproblem creation callback, call SCIPbendersSetSubproblemType with the appropriate problem type.\n");
1977
1978 return SCIP_ERROR;
1979 }
1980 }
1981 }
1982
1983 /* checking the convexity of the master problem. This information is useful for the cut generation methods, such as
1984 * non-good and integer cuts
1985 */
1986 SCIP_CALL( checkSubproblemConvexity(benders, set, -1) );
1987
1988 benders->subprobscreated = TRUE;
1989
1990 return SCIP_OKAY;
1991}
1992
1994/** initializes Benders' decomposition */
1996 SCIP_BENDERS* benders, /**< Benders' decomposition */
1997 SCIP_SET* set /**< global SCIP settings */
1998 )
1999{
2000 int i;
2001
2002 assert(benders != NULL);
2003 assert(set != NULL);
2004
2005 if( benders->initialized )
2006 {
2007 SCIPerrorMessage("Benders' decomposition <%s> already initialized\n", benders->name);
2008 return SCIP_INVALIDCALL;
2009 }
2010
2011 if( set->misc_resetstat )
2012 {
2013 SCIPclockReset(benders->setuptime);
2014 SCIPclockReset(benders->bendersclock);
2015
2016 benders->ncalls = 0;
2017 benders->ncutsfound = 0;
2018 benders->ntransferred = 0;
2019 }
2020
2021 /* start timing */
2022 SCIPclockStart(benders->setuptime, set);
2023
2024 if( benders->bendersinit != NULL )
2025 {
2026 SCIP_CALL( benders->bendersinit(set->scip, benders) );
2027 }
2028
2029 benders->initialized = TRUE;
2030
2031 /* if the Benders' decomposition is a copy, then the auxiliary variables already exist. So they are registered with
2032 * the Benders' decomposition struct during the init stage. If the Benders' decomposition is not a copy, then the
2033 * auxiliary variables need to be created, which occurs in the initpre stage
2034 */
2035 if( benders->iscopy )
2036 {
2037 /* the copied auxiliary variables must be assigned to the target Benders' decomposition */
2038 SCIP_CALL( assignAuxiliaryVariables(set->scip, benders) );
2039 }
2040
2041 /* creates the subproblems and sets up the probing mode for LP subproblems. This function calls the benderscreatesub
2042 * callback. */
2043 SCIP_CALL( createSubproblems(benders, set) );
2044
2045 /* storing the solution tolerance set by the SCIP parameters */
2046 SCIP_CALL( SCIPsetGetRealParam(set, "benders/solutiontol", &benders->solutiontol) );
2047
2048 /* allocating memory for the stored constraints array */
2049 if( benders->storedcutssize == 0 )
2050 {
2053 benders->nstoredcuts = 0;
2054 }
2055
2056 /* initialising the Benders' cuts */
2058 for( i = 0; i < benders->nbenderscuts; i++ )
2059 {
2061 }
2062
2063 /* stop timing */
2064 SCIPclockStop(benders->setuptime, set);
2065
2066 return SCIP_OKAY;
2067}
2068
2069
2070/** Transfers Benders' cuts that were generated while solving a sub-SCIP to the original SCIP instance. This involves
2071 * creating a constraint/cut that is equivalent to the generated cut in the sub-SCIP. This new constraint/cut is then
2072 * added to the original SCIP instance.
2074static
2076 SCIP* sourcescip, /**< the source SCIP from when the Benders' decomposition was copied */
2077 SCIP_BENDERS* benders, /**< the Benders' decomposition structure of the sub SCIP */
2078 SCIP_VAR** vars, /**< the variables from the source constraint */
2079 SCIP_Real* vals, /**< the coefficients of the variables in the source constriant */
2080 SCIP_Real lhs, /**< the LHS of the source constraint */
2081 SCIP_Real rhs, /**< the RHS of the source constraint */
2082 int nvars /**< the number of variables in the source constraint */
2083 )
2084{
2085 SCIP_BENDERS* sourcebenders; /* the Benders' decomposition of the source SCIP */
2086 SCIP_CONSHDLR* consbenders; /* a helper variable for the Benders' decomposition constraint handler */
2087 SCIP_CONS* transfercons = NULL; /* the constraint that is generated to transfer the constraints/cuts */
2088 SCIP_ROW* transfercut = NULL; /* the cut that is generated to transfer the constraints/cuts */
2089 SCIP_VAR* sourcevar; /* the source variable that will be added to the transferred cut */
2090 SCIP_VAR* origvar;
2091 SCIP_Real scalar;
2092 SCIP_Real constant;
2093 char cutname[SCIP_MAXSTRLEN]; /* the name of the transferred cut */
2094 int i;
2095 SCIP_Bool fail;
2096
2097 assert(sourcescip != NULL);
2098 assert(benders != NULL);
2099 assert(vars != NULL);
2100 assert(vals != NULL);
2101
2102 /* retrieving the source Benders' decomposition structure */
2103 sourcebenders = SCIPfindBenders(sourcescip, SCIPbendersGetName(benders));
2104
2105 /* retrieving the Benders' decomposition constraint handler */
2106 consbenders = SCIPfindConshdlr(sourcescip, "benders");
2107
2108 /* setting the name of the transferred cut */
2109 (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "transferredcut_%d",
2110 SCIPbendersGetNTransferredCuts(sourcebenders) );
2111
2112 /* TODO: It could be more efficient to pass an updated vars array with the vals array to the
2113 * SCIPcreateConsBasicLinear/SCIPcreateEmptyRowConshdlr. This should be implemented to improve the performance of the
2114 * Large Neighbourhood Benders Search.
2115 */
2116
2117 /* creating an empty row/constraint for the transferred cut */
2118 if( sourcebenders->cutsasconss )
2119 {
2120 SCIP_CALL( SCIPcreateConsBasicLinear(sourcescip, &transfercons, cutname, 0, NULL, NULL, lhs, rhs) );
2121 SCIP_CALL( SCIPsetConsRemovable(sourcescip, transfercons, TRUE) );
2122 }
2123 else
2124 {
2125 SCIP_CALL( SCIPcreateEmptyRowConshdlr(sourcescip, &transfercut, consbenders, cutname, lhs, rhs, FALSE,
2126 FALSE, TRUE) );
2127 }
2128
2129 fail = FALSE;
2130 for( i = 0; i < nvars; i++ )
2131 {
2132 /* getting the original variable for the transformed variable */
2133 origvar = vars[i];
2134 scalar = 1.0;
2135 constant = 0.0;
2136 SCIP_CALL( SCIPvarGetOrigvarSum(&origvar, &scalar, &constant) );
2137
2138 /* getting the source var from the hash map */
2139 sourcevar = (SCIP_VAR*) SCIPhashmapGetImage(benders->mastervarsmap, origvar);
2140
2141 /* if the source variable is not found, then the mapping in incomplete. So the constraint can not be
2142 * transferred. */
2143 if( sourcevar == NULL )
2144 {
2145 fail = TRUE;
2146 break;
2147 }
2148
2149 if( sourcebenders->cutsasconss )
2150 {
2151 assert( transfercons != NULL );
2152 SCIP_CALL( SCIPaddCoefLinear(sourcescip, transfercons, sourcevar, vals[i]) ); /*lint !e644*/
2153 }
2154 else
2155 {
2156 assert( transfercut != NULL );
2157 SCIP_CALL( SCIPaddVarToRow(sourcescip, transfercut, sourcevar, vals[i]) ); /*lint !e644*/
2158 }
2159 }
2160
2161 /* if all of the source variables were found to generate the cut */
2162 if( !fail )
2163 {
2164 if( sourcebenders->cutsasconss )
2165 {
2166 SCIP_CALL( SCIPaddCons(sourcescip, transfercons) );
2167 }
2168 else
2169 {
2170 SCIP_CALL( SCIPaddPoolCut(sourcescip, transfercut) );
2171 }
2172
2173 sourcebenders->ntransferred++;
2174 }
2175
2176 /* release the row/constraint */
2177 if( sourcebenders->cutsasconss )
2178 {
2179 /* only release if the creation of the constraint failed. */
2180 SCIP_CALL( SCIPreleaseCons(sourcescip, &transfercons) );
2181 }
2182 else
2183 {
2184 SCIP_CALL( SCIPreleaseRow(sourcescip, &transfercut) );
2185 }
2186
2187 return SCIP_OKAY;
2188}
2189
2190
2191/** transfers the cuts generated in a subscip to the source scip */
2192static
2194 SCIP* sourcescip, /**< the source SCIP from when the Benders' decomposition was copied */
2195 SCIP* subscip, /**< the sub SCIP where the Benders' cuts were generated */
2196 SCIP_BENDERS* benders /**< the Benders' decomposition structure of the sub SCIP */
2197 )
2198{
2199 SCIP_BENDERS* sourcebenders; /* the Benders' decomposition of the source SCIP */
2200 SCIP_VAR** vars; /* the variables of the added constraint/row */
2201 SCIP_Real* vals; /* the values of the added constraint/row */
2202 SCIP_Real lhs; /* the LHS of the added constraint/row */
2203 SCIP_Real rhs; /* the RHS of the added constraint/row */
2204 int naddedcuts;
2205 int nvars;
2206 int i;
2207
2208 assert(subscip != NULL);
2209 assert(benders != NULL);
2210
2211 /* retrieving the source Benders' decomposition structure */
2212 sourcebenders = SCIPfindBenders(sourcescip, SCIPbendersGetName(benders));
2213
2214 /* exit if the cuts should not be transferred from the sub SCIP to the source SCIP. */
2215 if( !sourcebenders->transfercuts || benders->mastervarsmap == NULL )
2216 return SCIP_OKAY;
2217
2218 /* retrieving the number of stored Benders' cuts */
2219 naddedcuts = SCIPbendersGetNStoredCuts(benders);
2220
2221 /* looping over all added cuts to construct the cut for the source scip */
2222 for( i = 0; i < naddedcuts; i++ )
2223 {
2224 /* collecting the variable information from the constraint */
2225 SCIP_CALL( SCIPbendersGetStoredCutData(benders, i, &vars, &vals, &lhs, &rhs, &nvars) );
2226
2227 if( nvars > 0 )
2228 {
2229 /* create and add the cut to be transferred from the sub SCIP to the source SCIP */
2230 SCIP_CALL( createAndAddTransferredCut(sourcescip, benders, vars, vals, lhs, rhs, nvars) );
2231 }
2232 }
2233
2234 return SCIP_OKAY;
2235}
2236
2238/** calls exit method of Benders' decomposition */
2240 SCIP_BENDERS* benders, /**< Benders' decomposition */
2241 SCIP_SET* set /**< global SCIP settings */
2242 )
2243{
2244 int nsubproblems;
2245 int i;
2246
2247 assert(benders != NULL);
2248 assert(set != NULL);
2249
2250 if( !benders->initialized )
2251 {
2252 SCIPerrorMessage("Benders' decomposition <%s> not initialized\n", benders->name);
2253 return SCIP_INVALIDCALL;
2254 }
2255
2256 /* start timing */
2257 SCIPclockStart(benders->setuptime, set);
2258
2259 if( benders->bendersexit != NULL )
2260 {
2261 SCIP_CALL( benders->bendersexit(set->scip, benders) );
2262 }
2263
2264 /* if the Benders' decomposition is a copy, then is a variable mapping was provided, then the generated cuts will
2265 * be transferred to the source scip
2266 */
2267 if( benders->iscopy && benders->mastervarsmap != NULL )
2268 {
2269 SCIP_CALL( transferBendersCuts(benders->sourcescip, set->scip, benders) );
2270 }
2271
2272 /* releasing the stored constraints */
2273 for( i = benders->nstoredcuts - 1; i >= 0; i-- )
2274 {
2275 SCIPfreeBlockMemoryArray(set->scip, &benders->storedcuts[i]->vals, benders->storedcuts[i]->nvars);
2276 SCIPfreeBlockMemoryArray(set->scip, &benders->storedcuts[i]->vars, benders->storedcuts[i]->nvars);
2277 SCIPfreeBlockMemory(set->scip, &benders->storedcuts[i]); /*lint !e866*/
2278 }
2279
2280 BMSfreeBlockMemoryArray(SCIPblkmem(set->scip), &benders->storedcuts, benders->storedcutssize);
2281 benders->storedcutssize = 0;
2282 benders->nstoredcuts = 0;
2283
2284 /* releasing all of the auxiliary variables */
2285 nsubproblems = SCIPbendersGetNSubproblems(benders);
2286 for( i = 0; i < nsubproblems; i++ )
2287 {
2288 /* it is possible that the master problem is not solved. As such, the auxiliary variables will not be created. So
2289 * we don't need to release the variables
2290 */
2291 if( benders->auxiliaryvars[i] != NULL )
2292 {
2293 /* we need to remove the locks from the auxiliary variables. This will be called always for the highest priority
2294 * Benders' plugin and others if the auxiliary variables are not shared
2295 */
2296 if( !benders->iscopy && SCIPvarGetNLocksDown(benders->auxiliaryvars[i]) > 0 )
2297 SCIP_CALL( SCIPaddVarLocksType(set->scip, benders->auxiliaryvars[i], SCIP_LOCKTYPE_MODEL, -1, 0) );
2298
2299 SCIP_CALL( SCIPreleaseVar(set->scip, &benders->auxiliaryvars[i]) );
2300 }
2301 }
2302
2303 /* if a corepoint has been used for cut strengthening, then this needs to be freed */
2304 if( benders->corepoint != NULL )
2305 {
2306 SCIP_CALL( SCIPfreeSol(set->scip, &benders->corepoint) );
2307 }
2308
2309 /* calling the exit method for the Benders' cuts */
2311 for( i = 0; i < benders->nbenderscuts; i++ )
2312 {
2314 }
2315
2316 benders->initialized = FALSE;
2317
2318 /* stop timing */
2319 SCIPclockStop(benders->setuptime, set);
2320
2321 return SCIP_OKAY;
2322}
2323
2324/** Checks whether a subproblem is independent. */
2325static
2327 SCIP* scip, /**< the SCIP data structure */
2328 SCIP_BENDERS* benders /**< Benders' decomposition */
2329 )
2330{
2331 SCIP_VAR** vars;
2332 int nvars;
2333 int nsubproblems;
2334 int i;
2335 int j;
2336
2337 assert(scip != NULL);
2338 assert(benders != NULL);
2339
2340 /* retrieving the master problem variables */
2341 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
2342
2343 nsubproblems = SCIPbendersGetNSubproblems(benders);
2344
2345 /* looping over all subproblems to check whether there exists at least one master problem variable */
2346 for( i = 0; i < nsubproblems; i++ )
2347 {
2348 SCIP_Bool independent = FALSE;
2349
2350 /* if there are user defined solving or freeing functions, then it is not possible to declare the independence of
2351 * the subproblems.
2352 */
2353 if( benders->benderssolvesubconvex == NULL && benders->benderssolvesub == NULL
2354 && benders->bendersfreesub == NULL )
2355 {
2356 independent = TRUE;
2357
2358 for( j = 0; j < nvars; j++ )
2359 {
2360 SCIP_VAR* subprobvar;
2361
2362 /* getting the subproblem problem variable corresponding to the master problem variable */
2363 SCIP_CALL( SCIPgetBendersSubproblemVar(scip, benders, vars[j], &subprobvar, i) );
2364
2365 /* if the subporblem variable is not NULL, then the subproblem depends on the master problem */
2366 if( subprobvar != NULL )
2367 {
2368 independent = FALSE;
2369 break;
2370 }
2371 }
2372
2373 /* setting the independent flag */
2374 SCIPbendersSetSubproblemIsIndependent(benders, i, independent);
2375 }
2376 }
2377
2378 return SCIP_OKAY;
2379}
2381/** informs the Benders' decomposition that the presolving process is being started */
2383 SCIP_BENDERS* benders, /**< Benders' decomposition */
2384 SCIP_SET* set, /**< global SCIP settings */
2385 SCIP_STAT* stat /**< dynamic problem statistics */
2386 )
2387{
2388 assert(benders != NULL);
2389 assert(set != NULL);
2390 assert(stat != NULL);
2391
2392 /* if the Benders' decomposition is the original, then the auxiliary variables need to be created. If the Benders'
2393 * decomposition is a copy, then the auxiliary variables already exist. The assignment of the auxiliary variables
2394 * occurs in bendersInit
2395 */
2396 if( !benders->iscopy )
2397 {
2398 /* check the subproblem independence. This check is only performed if the user has not implemented a solve
2399 * subproblem function.
2400 */
2401 if( benders->benderssolvesubconvex == NULL && benders->benderssolvesub == NULL )
2402 SCIP_CALL( checkSubproblemIndependence(set->scip, benders) );
2403
2404 /* adding the auxiliary variables to the master problem */
2405 SCIP_CALL( addAuxiliaryVariablesToMaster(set->scip, benders) );
2406 }
2407
2408 /* call presolving initialization method of Benders' decomposition */
2409 if( benders->bendersinitpre != NULL )
2410 {
2411 /* start timing */
2412 SCIPclockStart(benders->setuptime, set);
2413
2414 SCIP_CALL( benders->bendersinitpre(set->scip, benders) );
2415
2416 /* stop timing */
2417 SCIPclockStop(benders->setuptime, set);
2418 }
2419
2420 return SCIP_OKAY;
2421}
2422
2424/** informs the Benders' decomposition that the presolving process has completed */
2426 SCIP_BENDERS* benders, /**< Benders' decomposition */
2427 SCIP_SET* set, /**< global SCIP settings */
2428 SCIP_STAT* stat /**< dynamic problem statistics */
2429 )
2430{
2431 assert(benders != NULL);
2432 assert(set != NULL);
2433 assert(stat != NULL);
2434
2435 /* call presolving deinitialization method of Benders' decomposition */
2436 if( benders->bendersexitpre != NULL )
2437 {
2438 /* start timing */
2439 SCIPclockStart(benders->setuptime, set);
2440
2441 SCIP_CALL( benders->bendersexitpre(set->scip, benders) );
2442
2443 /* stop timing */
2444 SCIPclockStop(benders->setuptime, set);
2445 }
2446
2447 return SCIP_OKAY;
2448}
2450/** informs Benders' decomposition that the branch and bound process is being started */
2452 SCIP_BENDERS* benders, /**< Benders' decomposition */
2453 SCIP_SET* set /**< global SCIP settings */
2454 )
2455{
2456 int i;
2457
2458 assert(benders != NULL);
2459 assert(set != NULL);
2460
2461 /* call solving process initialization method of Benders' decomposition */
2462 if( benders->bendersinitsol != NULL )
2463 {
2464 /* start timing */
2465 SCIPclockStart(benders->setuptime, set);
2466
2467 SCIP_CALL( benders->bendersinitsol(set->scip, benders) );
2468
2469 /* stop timing */
2470 SCIPclockStop(benders->setuptime, set);
2471 }
2472
2473 /* calling the initsol method for the Benders' cuts */
2475 for( i = 0; i < benders->nbenderscuts; i++ )
2476 {
2478 }
2479
2480 return SCIP_OKAY;
2481}
2483/** informs Benders' decomposition that the branch and bound process data is being freed */
2485 SCIP_BENDERS* benders, /**< Benders' decomposition */
2486 SCIP_SET* set /**< global SCIP settings */
2487 )
2488{
2489 int nsubproblems;
2490 int i;
2491
2492 assert(benders != NULL);
2493 assert(set != NULL);
2494
2495 nsubproblems = SCIPbendersGetNSubproblems(benders);
2496 /* freeing all subproblems that are independent, this is because they have not bee freed during the subproblem
2497 * solving loop.
2498 */
2499 for( i = 0; i < nsubproblems; i++ )
2500 {
2501 if( SCIPbendersSubproblemIsIndependent(benders, i) )
2502 {
2503 /* disabling the independence of the subproblem so that it can be freed */
2505
2506 /* freeing the independent subproblem */
2507 SCIP_CALL( SCIPbendersFreeSubproblem(benders, set, i) );
2508 }
2509 }
2510
2511 /* call solving process deinitialization method of Benders' decomposition */
2512 if( benders->bendersexitsol != NULL )
2513 {
2514 /* start timing */
2515 SCIPclockStart(benders->setuptime, set);
2516
2517 SCIP_CALL( benders->bendersexitsol(set->scip, benders) );
2518
2519 /* stop timing */
2520 SCIPclockStop(benders->setuptime, set);
2521 }
2522
2523 /* sorting the Benders' decomposition cuts in order of priority. Only a single cut is generated for each subproblem
2524 * per solving iteration. This is particularly important in the case of the optimality and feasibility cuts. Since
2525 * these work on two different solutions to the subproblem, it is not necessary to generate both cuts. So, once the
2526 * feasibility cut is generated, then no other cuts will be generated.
2527 */
2529
2530 /* calling the exitsol method for the Benders' cuts */
2531 for( i = 0; i < benders->nbenderscuts; i++ )
2532 {
2534 }
2535
2536 return SCIP_OKAY;
2537}
2539/** activates Benders' decomposition such that it is called in LP solving loop */
2541 SCIP_BENDERS* benders, /**< the Benders' decomposition structure */
2542 SCIP_SET* set, /**< global SCIP settings */
2543 int nsubproblems /**< the number subproblems used in this decomposition */
2544 )
2545{
2546 SCIP_EVENTHDLR* eventhdlr;
2547 SCIP_EVENTHDLRDATA* eventhdlrdata;
2548 int i;
2549
2550 assert(benders != NULL);
2551 assert(set != NULL);
2552 assert(set->stage == SCIP_STAGE_INIT || set->stage == SCIP_STAGE_PROBLEM);
2553
2554 if( !benders->active )
2555 {
2556 benders->active = TRUE;
2557 set->nactivebenders++;
2558 set->benderssorted = FALSE;
2559
2560 benders->nsubproblems = nsubproblems;
2561 benders->nactivesubprobs = nsubproblems;
2562 benders->prevlowerbound = -SCIPsetInfinity(set);
2563 benders->strengthenround = FALSE;
2564
2565 /* allocating memory for the subproblems arrays */
2568 SCIP_ALLOC( BMSallocMemoryArray(&benders->solvestat, benders->nsubproblems) );
2579
2580 /* creating the priority queue for the subproblem solving status */
2581 SCIP_CALL( SCIPpqueueCreate(&benders->subprobqueue, benders->nsubproblems, 1.1,
2582 benders->benderssubcomp == NULL ? benderssubcompdefault : benders->benderssubcomp, NULL) );
2583
2584 for( i = 0; i < benders->nsubproblems; i++ )
2585 {
2586 SCIP_SUBPROBLEMSOLVESTAT* solvestat;
2587
2588 benders->subproblems[i] = NULL;
2589 benders->auxiliaryvars[i] = NULL;
2590 benders->subprobobjval[i] = SCIPsetInfinity(set);
2591 benders->bestsubprobobjval[i] = SCIPsetInfinity(set);
2592 benders->subproblowerbound[i] = -SCIPsetInfinity(set);
2594 benders->subprobisconvex[i] = FALSE;
2595 benders->subprobisnonlinear[i] = FALSE;
2596 benders->subprobsetup[i] = FALSE;
2597 benders->indepsubprob[i] = FALSE;
2598 benders->subprobenabled[i] = TRUE;
2599 benders->mastervarscont[i] = FALSE;
2600
2601 /* initialising the subproblem solving status */
2602 SCIP_ALLOC( BMSallocMemory(&solvestat) );
2603 solvestat->idx = i;
2604 solvestat->ncalls = 0;
2605 solvestat->avgiter = 0;
2606 benders->solvestat[i] = solvestat;
2607
2608 /* inserting the initial elements into the priority queue */
2609 SCIP_CALL( SCIPpqueueInsert(benders->subprobqueue, benders->solvestat[i]) );
2610 }
2611
2612 /* adding an eventhandler for updating the lower bound when the root node is solved. */
2613 eventhdlrdata = (SCIP_EVENTHDLRDATA*)benders;
2614
2615 /* include event handler into SCIP */
2617 eventExecBendersNodesolved, eventhdlrdata) );
2618 SCIP_CALL( SCIPsetEventhdlrInitsol(set->scip, eventhdlr, eventInitsolBendersNodesolved) );
2619 assert(eventhdlr != NULL);
2620 }
2621
2622 return SCIP_OKAY;
2623}
2625/** deactivates Benders' decomposition such that it is no longer called in LP solving loop */
2627 SCIP_BENDERS* benders, /**< the Benders' decomposition structure */
2628 SCIP_SET* set /**< global SCIP settings */
2629 )
2630{
2631 int i;
2632
2633 assert(benders != NULL);
2634 assert(set != NULL);
2635 assert(set->stage == SCIP_STAGE_INIT || set->stage == SCIP_STAGE_PROBLEM);
2636
2637 if( benders->active )
2638 {
2639 int nsubproblems;
2640
2641 nsubproblems = SCIPbendersGetNSubproblems(benders);
2642
2643#ifndef NDEBUG
2644 /* checking whether the auxiliary variables and subproblems are all NULL */
2645 for( i = 0; i < nsubproblems; i++ )
2646 assert(benders->auxiliaryvars[i] == NULL);
2647#endif
2648
2649 /* if the subproblems were created by the Benders' decomposition core, then they need to be freed */
2650 if( benders->freesubprobs )
2651 {
2652 for( i = SCIPbendersGetNSubproblems(benders) - 1; i >= 0; i-- )
2653 {
2654 SCIP* subproblem = SCIPbendersSubproblem(benders, i);
2655 SCIP_CALL( SCIPfree(&subproblem) );
2656 }
2657 }
2658
2659 benders->active = FALSE;
2660 set->nactivebenders--;
2661 set->benderssorted = FALSE;
2662
2663 /* freeing the priority queue memory */
2664 SCIPpqueueFree(&benders->subprobqueue);
2665
2666 for( i = nsubproblems - 1; i >= 0; i-- )
2667 BMSfreeMemory(&benders->solvestat[i]);
2668
2669 /* freeing the memory allocated during the activation of the Benders' decomposition */
2681 BMSfreeMemoryArray(&benders->solvestat);
2683 }
2684
2685 return SCIP_OKAY;
2686}
2688/** returns whether the given Benders' decomposition is in use in the current problem */
2690 SCIP_BENDERS* benders /**< the Benders' decomposition structure */
2691 )
2692{
2693 assert(benders != NULL);
2694
2695 return benders->active;
2696}
2697
2698/** updates the lower bound for all auxiliary variables. This is called if the first LP enforced is unbounded. */
2699static
2701 SCIP_BENDERS* benders, /**< Benders' decomposition */
2702 SCIP_SET* set, /**< global SCIP settings */
2703 SCIP_RESULT* result /**< the result from updating the auxiliary variable lower bound */
2704 )
2705{
2706 int nsubproblems;
2707 int i;
2708
2709 assert(benders != NULL);
2710 assert(set != NULL);
2711
2712 (*result) = SCIP_DIDNOTRUN;
2713
2714 nsubproblems = SCIPbendersGetNSubproblems(benders);
2715
2716 for( i = 0; i < nsubproblems; i++ )
2717 {
2718 SCIP_VAR* auxiliaryvar;
2719 SCIP_Real lowerbound;
2720 SCIP_Bool infeasible;
2721
2722 infeasible = FALSE;
2723
2724 /* computing the lower bound of the subproblem by solving it without any variable fixings */
2725 SCIP_CALL( SCIPbendersComputeSubproblemLowerbound(benders, set, i, &lowerbound, &infeasible) );
2726
2727 /* if the subproblem is infeasible, then the original problem is infeasible */
2728 if( infeasible )
2729 {
2730 (*result) = SCIP_INFEASIBLE;
2731 break;
2732 }
2733
2734 /* retrieving the auxiliary variable */
2735 auxiliaryvar = SCIPbendersGetAuxiliaryVar(benders, i);
2736
2737 /* only update the lower bound if it is greater than the current lower bound */
2738 if( SCIPsetIsGT(set, lowerbound, SCIPvarGetLbGlobal(auxiliaryvar)) )
2739 {
2740 SCIPsetDebugMsg(set, "Tightened lower bound of <%s> to %g\n", SCIPvarGetName(auxiliaryvar), lowerbound);
2741 /* updating the lower bound of the auxiliary variable */
2742 SCIP_CALL( SCIPchgVarLb(set->scip, auxiliaryvar, lowerbound) );
2743 (*result) = SCIP_REDUCEDDOM;
2744 }
2745
2746 /* stores the lower bound for the subproblem */
2747 SCIPbendersUpdateSubproblemLowerbound(benders, i, lowerbound);
2748 }
2749
2750 return SCIP_OKAY;
2751}
2752
2753/** sets the core point used for cut strengthening. If the strenghtenintpoint is set to 'i', then the core point is
2754 * reinitialised each time the incumbent is updated
2756static
2758 SCIP* scip, /**< the SCIP data structure */
2759 SCIP_BENDERS* benders /**< Benders' decomposition */
2760 )
2761{
2762 SCIP_SOL* bestsol;
2763
2764 assert(scip != NULL);
2765 assert(benders != NULL);
2766
2767 /* if the core point is not NULL and the interior point is not reinitialised, then nothing is done */
2768 if( benders->corepoint != NULL && benders->strengthenintpoint != 'i' )
2769 return SCIP_OKAY;
2770
2771 bestsol = SCIPgetBestSol(scip);
2772
2773 /* if the core point should be updated, then this only happens if the incumbent solution has been updated */
2774 if( benders->strengthenintpoint == 'i' && benders->initcorepoint == bestsol )
2775 return SCIP_OKAY;
2776
2777 /* if a corepoint has been used for cut strengthening, then this needs to be freed */
2778 if( benders->corepoint != NULL )
2779 {
2780 SCIP_CALL( SCIPfreeSol(scip, &benders->corepoint) );
2781 }
2782
2783 switch( benders->strengthenintpoint )
2784 {
2785 SCIP_VAR** vars;
2786 SCIP_Real timelimit;
2787 int nvars;
2788 int i;
2789
2790 case 'l':
2792 SCIP_CALL( SCIPunlinkSol(scip, benders->corepoint) );
2793 break;
2794 case 'f':
2795 case 'i':
2796 SCIP_CALL( SCIPcreateSolCopy(scip, &benders->corepoint, bestsol) );
2797 SCIP_CALL( SCIPunlinkSol(scip, benders->corepoint) );
2798 benders->initcorepoint = bestsol;
2799 break;
2800 case 'r':
2801 /* prepare time limit */
2802 SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
2803 if ( ! SCIPisInfinity(scip, timelimit) )
2804 timelimit -= SCIPgetSolvingTime(scip);
2805
2806 /* if there is time remaining, then compute the relative interior point. Otherwise, return the LP solution */
2807 if ( timelimit > 0.0 )
2808 {
2809 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, 0, "Computing relative interior point (time limit: %g, iter limit: %d) ...\n", timelimit, INT_MAX);
2810 SCIP_CALL( SCIPcomputeLPRelIntPoint(scip, TRUE, FALSE, timelimit, INT_MAX, &benders->corepoint) );
2811 }
2812 else
2813 {
2815 SCIP_CALL( SCIPunlinkSol(scip, benders->corepoint) );
2816 }
2817 break;
2818 case 'z':
2819 SCIP_CALL( SCIPcreateSol(scip, &benders->corepoint, NULL) );
2820 break;
2821 case 'o':
2822 SCIP_CALL( SCIPcreateSol(scip, &benders->corepoint, NULL) );
2823
2824 /* getting the variable data so that the */
2825 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
2826
2827 /* setting all variable values to 1.0 */
2828 for( i = 0; i < nvars; i++ )
2829 {
2830 SCIP_CALL( SCIPsetSolVal(scip, benders->corepoint, vars[i], 1.0) );
2831 }
2832 break;
2833 default:
2835 SCIP_CALL( SCIPunlinkSol(scip, benders->corepoint) );
2836 }
2837
2838 return SCIP_OKAY;
2839}
2840
2841/** performs cut strengthening by using an interior solution to generate cuts */
2842static
2844 SCIP_BENDERS* benders, /**< Benders' decomposition */
2845 SCIP_SET* set, /**< global SCIP settings */
2846 SCIP_SOL* sol, /**< primal CIP solution */
2847 SCIP_BENDERSENFOTYPE type, /**< the type of solution being enforced */
2848 SCIP_Bool checkint, /**< are the subproblems called during a check/enforce of integer sols? */
2849 SCIP_Bool perturbsol, /**< should the solution be perturbed to escape infeasibility? */
2850 SCIP_Bool* auxviol, /**< set to TRUE only if the solution is feasible but the aux vars are violated */
2851 SCIP_Bool* infeasible, /**< is the master problem infeasible with respect to the Benders' cuts? */
2852 SCIP_Bool* skipsolve, /**< should the main solve be skipped as a result of this strengthening? */
2853 SCIP_RESULT* result /**< result of the pricing process */
2854 )
2855{
2856 SCIP_SOL* sepapoint;
2857 SCIP_VAR** vars;
2858 int prevcutsfound;
2859 int nvars;
2860 int i;
2861
2862 assert(benders != NULL);
2863 assert(set != NULL);
2864
2865 (*result) = SCIP_DIDNOTRUN;
2866 (*skipsolve) = FALSE;
2867
2868 /* the cut stabilisation is only performed when enforcing LP solutions. The solution is not NULL if the stabilisation
2869 * is currently being performed. It is important to avoid recursion
2870 */
2871 if( type != SCIP_BENDERSENFOTYPE_LP || sol != NULL )
2872 return SCIP_OKAY;
2873
2874 /* checking if a change to the lower bound has occurred */
2875 if( SCIPsetIsGT(set, SCIPgetLowerbound(set->scip), benders->prevlowerbound)
2876 || SCIPgetCurrentNode(set->scip) != benders->prevnode )
2877 {
2878 benders->prevnode = SCIPgetCurrentNode(set->scip);
2879 benders->prevlowerbound = SCIPgetLowerbound(set->scip);
2880 benders->noimprovecount = 0;
2881 }
2882 else
2883 benders->noimprovecount++;
2884
2885 /* if the number of iterations without improvement exceeds 3*noimprovelimit, then the no stabilisation is performed
2886 */
2887 if( benders->noimprovecount > 3*benders->noimprovelimit )
2888 return SCIP_OKAY;
2889
2890 /* if there is no incumbent solution, then it is not possible to create the core point and hence the strengthening
2891 * can not be performed
2892 */
2893 if( SCIPgetBestSol(set->scip) == NULL )
2894 return SCIP_OKAY;
2895
2896 /* if no LP iterations have been performed since the last call of the cut strenghtening, then the strengthening is
2897 * aborted
2898 */
2899 if( benders->prevnlpiter == SCIPgetNLPIterations(set->scip) )
2900 return SCIP_OKAY;
2901
2902 benders->prevnlpiter = SCIPgetNLPIterations(set->scip);
2903
2904 /* if the separation point solution is NULL, then we create the solution using the current LP relaxation. */
2905 SCIP_CALL( setAndUpdateCorePoint(set->scip, benders) );
2906
2907 /* creating the separation point
2908 * TODO: This could be a little to memory heavy, it may be better just to create the separation point once and then
2909 * update it each time.
2910 */
2911 SCIP_CALL( SCIPcreateLPSol(set->scip, &sepapoint, NULL) );
2912 SCIP_CALL( SCIPunlinkSol(set->scip, sepapoint) );
2913
2914 SCIP_CALL( SCIPgetVarsData(set->scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
2915 assert(vars != NULL);
2916
2917 /* creating a solution that is a convex combination of the LP solution and the separation point */
2918 for( i = 0; i < nvars; i++ )
2919 {
2920 SCIP_VAR* subvar;
2921 SCIP_Real corepointval;
2922 SCIP_Real lpsolval;
2923 SCIP_Real newsolval;
2924 int j;
2925
2926 corepointval = SCIPgetSolVal(set->scip, benders->corepoint, vars[i]);
2927 lpsolval = SCIPgetSolVal(set->scip, sol, vars[i]);
2928 newsolval = lpsolval;
2929
2930 /* checking whether the master variable is mapped to any subproblem variables */
2931 subvar = NULL;
2932 j = 0;
2933 while( subvar == NULL && j < SCIPgetBendersNSubproblems(set->scip, benders) )
2934 {
2935 SCIP_CALL( SCIPgetBendersSubproblemVar(set->scip, benders, vars[i], &subvar, j) );
2936 j++;
2937 }
2938
2939 /* if the variable is a linking variable and it is not fixed, then a convex combination with the corepoint is
2940 * computed.
2941 */
2942 if( subvar != NULL && SCIPvarGetStatus(vars[i]) != SCIP_VARSTATUS_FIXED )
2943 {
2944 /* if the number of iterations without improvement exceeds noimprovelimit, then no convex combination is
2945 * created
2946 */
2947 if( !perturbsol && benders->noimprovecount <= benders->noimprovelimit )
2948 {
2949 newsolval = lpsolval*benders->convexmult + corepointval*(1 - benders->convexmult);
2950
2951 /* updating the core point */
2952 SCIP_CALL( SCIPsetSolVal(set->scip, benders->corepoint, vars[i], newsolval) );
2953 }
2954
2955 /* if the number of iterations without improvement is less than 2*noimprovelimit, then perturbation is
2956 * performed
2957 * TODO: This should be a random vector!!!!
2958 */
2959 if( perturbsol || benders->noimprovecount <= 2*benders->noimprovelimit )
2960 newsolval += benders->perturbeps;
2961 }
2962
2963 /* updating the separation point */
2964 SCIP_CALL( SCIPsetSolVal(set->scip, sepapoint, vars[i], newsolval) );
2965 }
2966
2967 /* storing the number of cuts found */
2968 prevcutsfound = SCIPbendersGetNCutsFound(benders);
2969
2970 SCIPsetDebugMsg(set, "solving Benders' decomposition subproblems with stabilised point.\n");
2971
2972 /* calling the subproblem solving method to generate cuts from the separation solution */
2973 SCIP_CALL( SCIPsolveBendersSubproblems(set->scip, benders, sepapoint, result, infeasible, auxviol, type, checkint) );
2974
2975 SCIPsetDebugMsg(set, "solved Benders' decomposition subproblems with stabilised point. noimprovecount %d result %d\n",
2976 benders->noimprovecount, (*result));
2977
2978 /* if constraints were added, then the main Benders' solving loop is skipped. */
2979 if( !(*infeasible) && ((*result) == SCIP_CONSADDED || (*result) == SCIP_SEPARATED) )
2980 (*skipsolve) = TRUE;
2981
2982 /* capturing cut strengthening statistics */
2983 benders->nstrengthencalls++;
2984 benders->nstrengthencuts += (SCIPbendersGetNCutsFound(benders) - prevcutsfound);
2985
2986 /* if no cuts were added, then the strengthening round is marked as failed */
2987 if( SCIPbendersGetNCutsFound(benders) == prevcutsfound )
2988 benders->nstrengthenfails++;
2989
2990 /* freeing the sepapoint solution */
2991 SCIP_CALL( SCIPfreeSol(set->scip, &sepapoint) );
2992
2993 return SCIP_OKAY;
2994}
2995
2996
2997/** Returns whether only the convex relaxations will be checked in this solve loop
2998 * when Benders' is used in the LNS heuristics, only the convex relaxations of the master/subproblems are checked,
2999 * i.e. no integer cuts are generated. In this case, then Benders' decomposition is performed under the assumption
3000 * that all subproblems are convex relaxations.
3001 */
3003 SCIP_BENDERS* benders, /**< Benders' decomposition */
3004 SCIP_Bool subscipsoff /**< flag indicating whether plugins using sub-SCIPs are deactivated */
3005 )
3006{
3007 return benders->iscopy && benders->lnscheck && subscipsoff;
3008}
3009
3010/** returns the number of subproblems that will be checked in this iteration */
3011static
3013 SCIP_BENDERS* benders, /**< Benders' decomposition */
3014 SCIP_SET* set, /**< global SCIP settings */
3015 SCIP_BENDERSENFOTYPE type /**< the type of solution being enforced */
3016 )
3017{
3018 if( benders->ncalls == 0 || type == SCIP_BENDERSENFOTYPE_CHECK
3020 return SCIPbendersGetNSubproblems(benders);
3021 else
3022 return (int) SCIPsetCeil(set, (SCIP_Real) SCIPbendersGetNSubproblems(benders)*benders->subprobfrac);
3023}
3024
3025/** returns whether the solving of the given subproblem needs to be executed */
3026static
3028 SCIP_BENDERS* benders, /**< Benders' decomposition */
3029 int probnumber /**< the subproblem index */
3030 )
3031{
3032 return (!SCIPbendersSubproblemIsIndependent(benders, probnumber)
3033 && SCIPbendersSubproblemIsEnabled(benders, probnumber));
3034}
3035
3036/** creates an ordered list of subproblem indices to be solved */
3037static
3039 SCIP_BENDERS* benders, /**< Benders' decomposition */
3040 SCIP_SET* set, /**< global SCIP settings */
3041 SCIP_BENDERSENFOTYPE type, /**< the type of solution being enforced */
3042 int** solveidx, /**< a list of subproblem indices to the solved in the current iteration */
3043 int* nsolveidx /**< the number of subproblem indices in the list */
3044 )
3045{
3046 int nsubproblems;
3047 int numtocheck;
3048 int subproblemcount;
3049
3050 assert(benders != NULL);
3051 assert(set != NULL);
3052 assert((*solveidx) != NULL);
3053 assert(nsolveidx != NULL);
3054 assert(SCIPpqueueNElems(benders->subprobqueue) <= SCIPbendersGetNSubproblems(benders));
3055
3056 nsubproblems = SCIPbendersGetNSubproblems(benders);
3057
3058 /* it is possible to only solve a subset of subproblems. This is given by a parameter. */
3059 numtocheck = numSubproblemsToCheck(benders, set, type);
3060
3061 (*nsolveidx) = 0;
3062
3063 subproblemcount = 0;
3064 while( subproblemcount < nsubproblems && subproblemcount < numtocheck )
3065 {
3066 SCIP_SUBPROBLEMSOLVESTAT* solvestat;
3067
3069 (*solveidx)[(*nsolveidx)] = solvestat->idx;
3070 (*nsolveidx)++;
3071
3072 subproblemcount++;
3073 }
3074}
3075
3076/** updates the subproblem solving statistics and inserts the indices into the queue */
3077static
3079 SCIP_BENDERS* benders, /**< Benders' decomposition */
3080 int* solveidx, /**< the list of indices of subproblems that were solved */
3081 int nsolveidx, /**< the number of subproblem indices */
3082 SCIP_Bool updatestat /**< should the statistics be updated */
3083 )
3084{
3085 int i;
3086
3087 assert(benders != NULL);
3088 assert(solveidx != NULL);
3089
3090 for( i = 0; i < nsolveidx; i++ )
3091 {
3092 SCIP* subproblem;
3093 SCIP_SUBPROBLEMSOLVESTAT* solvestat;
3094
3095 subproblem = SCIPbendersSubproblem(benders, solveidx[i]);
3096 solvestat = benders->solvestat[solveidx[i]];
3097 assert(solvestat->idx == solveidx[i]);
3098
3099 /* updating the solving statistics */
3100 if( updatestat )
3101 {
3102 if( subproblem == NULL )
3103 solvestat->avgiter = 1;
3104 else
3105 solvestat->avgiter = (SCIP_Real)(solvestat->avgiter*solvestat->ncalls + SCIPgetNLPIterations(subproblem))
3106 /(SCIP_Real)(solvestat->ncalls + 1);
3107 solvestat->ncalls++;
3108 }
3109
3110 /* inserting the solving statistics into the priority queue */
3111 SCIP_CALL( SCIPpqueueInsert(benders->subprobqueue, solvestat) );
3112 }
3113
3114 assert(SCIPpqueueNElems(benders->subprobqueue) == SCIPbendersGetNSubproblems(benders));
3115
3116 return SCIP_OKAY;
3117}
3118
3119/** Solves each of the Benders' decomposition subproblems for the given solution. All, or a fraction, of subproblems are
3120 * solved before the Benders' decomposition cuts are generated.
3121 * Since a convex relaxation of the subproblem could be solved to generate cuts, a parameter nverified is used to
3122 * identified the number of subproblems that have been solved in their "original" form. For example, if the subproblem
3123 * is a MIP, then if the LP is solved to generate cuts, this does not constitute a verification. The verification is
3124 * only performed when the MIP is solved.
3126static
3128 SCIP_BENDERS* benders, /**< Benders' decomposition */
3129 SCIP_SET* set, /**< global SCIP settings */
3130 SCIP_SOL* sol, /**< primal CIP solution */
3131 SCIP_BENDERSENFOTYPE type, /**< the type of solution being enforced */
3132 SCIP_BENDERSSOLVELOOP solveloop, /**< the current solve loop */
3133 SCIP_Bool checkint, /**< are the subproblems called during a check/enforce of integer sols? */
3134 int* nverified, /**< the number of subproblems verified in the current loop */
3135 int* solveidx, /**< the indices of subproblems to be solved in this loop */
3136 int nsolveidx, /**< the number of subproblems to be solved in this loop */
3137 SCIP_Bool** subprobsolved, /**< an array indicating the subproblems that were solved in this loop. */
3138 SCIP_BENDERSSUBSTATUS** substatus, /**< array to store the status of the subsystem */
3139 SCIP_Bool* infeasible, /**< is the master problem infeasible with respect to the Benders' cuts? */
3140 SCIP_Bool* optimal, /**< is the current solution optimal? */
3141 SCIP_Bool* stopped /**< was the solving process stopped? */
3142 )
3143{
3144 SCIP_Bool onlyconvexcheck;
3145#ifdef _OPENMP
3146 int numthreads;
3147 int maxnthreads;
3148#endif
3149 int i;
3150 int j;
3151
3152 /* local variables for parallelisation of the solving loop */
3153 int locnverified = *nverified;
3154 SCIP_Bool locinfeasible = *infeasible;
3155 SCIP_Bool locoptimal = *optimal;
3156 SCIP_Bool locstopped = *stopped;
3157
3158 SCIP_RETCODE retcode = SCIP_OKAY;
3159
3160 assert(benders != NULL);
3161 assert(set != NULL);
3162
3163 /* getting the number of threads to use when solving the subproblems. This will be either be
3164 * min(numthreads, maxnthreads).
3165 * NOTE: This may not be correct. The Benders' decomposition parallelisation should not take all minimum threads if
3166 * they are specified. The number of threads should be specified with the Benders' decomposition parameters.
3167 */
3168#ifdef _OPENMP
3169 SCIP_CALL( SCIPsetGetIntParam(set, "parallel/maxnthreads", &maxnthreads) );
3170 numthreads = MIN(benders->numthreads, maxnthreads);
3171#endif
3172
3173 /* in the case of an LNS check, only the convex relaxations of the subproblems will be solved. This is a performance
3174 * feature, since solving the convex relaxation is typically much faster than solving the corresponding CIP. While
3175 * the CIP is not solved during the LNS check, the solutions are still of higher quality than when Benders' is not
3176 * employed.
3177 */
3178 onlyconvexcheck = SCIPbendersOnlyCheckConvexRelax(benders, SCIPsetGetSubscipsOff(set));
3179
3180 SCIPsetDebugMsg(set, "Performing the subproblem solving process. Number of subproblems to check %d\n", nsolveidx);
3181
3182 SCIPsetDebugMsg(set, "Benders' decomposition - solve loop %d\n", solveloop);
3183
3184 if( type == SCIP_BENDERSENFOTYPE_CHECK && sol == NULL )
3185 {
3186 /* TODO: Check whether this is absolutely necessary. I think that this if statment can be removed. */
3187 locinfeasible = TRUE;
3188 }
3189 else
3190 {
3191 /* solving each of the subproblems for Benders' decomposition */
3192 /* TODO: ensure that the each of the subproblems solve and update the parameters with the correct return values
3193 */
3194#ifndef __INTEL_COMPILER
3195 #pragma omp parallel for num_threads(numthreads) private(i) reduction(&&:locoptimal) reduction(||:locinfeasible) reduction(+:locnverified) reduction(||:locstopped) reduction(min:retcode)
3196#endif
3197 for( j = 0; j < nsolveidx; j++ )
3198 {
3199 SCIP_Bool subinfeas = FALSE;
3200 SCIP_Bool convexsub;
3201 SCIP_Bool solvesub = TRUE;
3202 SCIP_Bool solved;
3203
3204 i = solveidx[j];
3206
3207 /* the subproblem is initially flagged as not solved for this solving loop */
3208 (*subprobsolved)[i] = FALSE;
3209
3210 /* setting the subsystem status to UNKNOWN at the start of each solve loop */
3211 (*substatus)[i] = SCIP_BENDERSSUBSTATUS_UNKNOWN;
3212
3213 /* for the second solving loop, if the problem is an LP, it is not solved again. If the problem is a MIP,
3214 * then the subproblem objective function value is set to infinity. However, if the subproblem is proven
3215 * infeasible from the LP, then the IP loop is not performed.
3216 * If the solve loop is SCIP_BENDERSSOLVELOOP_USERCIP, then nothing is done. It is assumed that the user will
3217 * correctly update the objective function within the user-defined solving function.
3218 */
3219 if( solveloop == SCIP_BENDERSSOLVELOOP_CIP )
3220 {
3221 if( convexsub || (*substatus)[i] == SCIP_BENDERSSUBSTATUS_INFEAS )
3222 solvesub = FALSE;
3223 else
3224 {
3225 SCIPbendersSetSubproblemObjval(benders, i, SCIPbendersSubproblem(benders, i) != NULL ?
3227 }
3228 }
3229
3230 /* if the subproblem is independent, then it does not need to be solved. In this case, the nverified flag will
3231 * increase by one. When the subproblem is not independent, then it needs to be checked.
3232 */
3233 if( !subproblemIsActive(benders, i) )
3234 {
3235 /* NOTE: There is no need to update the optimal flag. This is because optimal is always TRUE until a
3236 * non-optimal subproblem is found.
3237 */
3238 /* if the auxiliary variable value is infinity, then the subproblem has not been solved yet. Currently the
3239 * subproblem statue is unknown. */
3243 {
3244 SCIPbendersSetSubproblemObjval(benders, i, SCIPbendersSubproblem(benders, i) != NULL ?
3246
3247 (*substatus)[i] = SCIP_BENDERSSUBSTATUS_UNKNOWN;
3248 locoptimal = FALSE;
3249
3250 SCIPsetDebugMsg(set, "Benders' decomposition: subproblem %d is not active, but has not been solved."
3251 " setting status to UNKNOWN\n", i);
3252 }
3253 else
3254 {
3256 SCIPbendersGetAuxiliaryVarVal(benders, set, sol, i)) < benders->solutiontol )
3257 {
3259 (*substatus)[i] = SCIP_BENDERSSUBSTATUS_OPTIMAL;
3260 }
3261 else
3262 {
3264 (*substatus)[i] = SCIP_BENDERSSUBSTATUS_AUXVIOL;
3265 }
3266
3267 SCIPsetDebugMsg(set, "Benders' decomposition: subproblem %d is not active, setting status to OPTIMAL\n", i);
3268 }
3269
3270 (*subprobsolved)[i] = TRUE;
3271
3272 /* the nverified counter is only increased in the convex solving loop */
3273 if( solveloop == SCIP_BENDERSSOLVELOOP_CONVEX || solveloop == SCIP_BENDERSSOLVELOOP_USERCONVEX )
3274 locnverified++;
3275 }
3276 else if( solvesub )
3277 {
3278 retcode = SCIPbendersExecSubproblemSolve(benders, set, sol, i, solveloop, FALSE, &solved, &subinfeas, type);
3279
3280 /* the solution for the subproblem is only processed if the return code is SCIP_OKAY */
3281 if( retcode == SCIP_OKAY )
3282 {
3283#ifdef SCIP_DEBUG
3284 if( type == SCIP_BENDERSENFOTYPE_LP )
3285 {
3286 SCIPsetDebugMsg(set, "Enfo LP: Subproblem %d Type %d (%f < %f)\n", i,
3287 SCIPbendersGetSubproblemType(benders, i), SCIPbendersGetAuxiliaryVarVal(benders, set, sol, i),
3288 SCIPbendersGetSubproblemObjval(benders, i));
3289 }
3290#endif
3291 (*subprobsolved)[i] = solved;
3292
3293 locinfeasible = locinfeasible || subinfeas;
3294 if( subinfeas )
3295 (*substatus)[i] = SCIP_BENDERSSUBSTATUS_INFEAS;
3296
3297 /* if the subproblems are solved to check integer feasibility, then the optimality check must be performed.
3298 * This will only be performed if checkint is TRUE and the subproblem was solved. The subproblem may not be
3299 * solved if the user has defined a solving function
3300 */
3301 if( checkint && (*subprobsolved)[i] )
3302 {
3303 /* if the subproblem is feasible, then it is necessary to update the value of the auxiliary variable to the
3304 * objective function value of the subproblem.
3305 */
3306 if( !subinfeas )
3307 {
3308 SCIP_Bool subproboptimal;
3309
3310 subproboptimal = SCIPbendersSubproblemIsOptimal(benders, set, sol, i);
3311
3312 if( subproboptimal )
3313 (*substatus)[i] = SCIP_BENDERSSUBSTATUS_OPTIMAL;
3314 else
3315 (*substatus)[i] = SCIP_BENDERSSUBSTATUS_AUXVIOL;
3316
3317 /* It is only possible to determine the optimality of a solution within a given subproblem in four
3318 * different cases:
3319 * i) solveloop == SCIP_BENDERSSOLVELOOP_CONVEX or USERCONVEX and the subproblem is convex.
3320 * ii) solveloop == SCIP_BENDERSOLVELOOP_CONVEX and only the convex relaxations will be checked.
3321 * iii) solveloop == SCIP_BENDERSSOLVELOOP_USERCIP and the subproblem was solved, since the user has
3322 * defined a solve function, it is expected that the solving is correctly executed.
3323 * iv) solveloop == SCIP_BENDERSSOLVELOOP_CIP and the MIP for the subproblem has been solved.
3324 */
3325 if( convexsub || onlyconvexcheck
3326 || solveloop == SCIP_BENDERSSOLVELOOP_CIP
3327 || solveloop == SCIP_BENDERSSOLVELOOP_USERCIP )
3328 locoptimal = locoptimal && subproboptimal;
3329
3330#ifdef SCIP_DEBUG
3331 if( convexsub || solveloop >= SCIP_BENDERSSOLVELOOP_CIP )
3332 {
3333 if( subproboptimal )
3334 {
3335 SCIPsetDebugMsg(set, "Subproblem %d is Optimal (%f >= %f)\n", i,
3337 }
3338 else
3339 {
3340 SCIPsetDebugMsg(set, "Subproblem %d is NOT Optimal (%f < %f)\n", i,
3342 }
3343 }
3344#endif
3345
3346 /* the nverified variable is only incremented when the original form of the subproblem has been solved.
3347 * What is meant by "original" is that the LP relaxation of CIPs are solved to generate valid cuts. So
3348 * if the subproblem is defined as a CIP, then it is only classified as checked if the CIP is solved.
3349 * There are three cases where the "original" form is solved are:
3350 * i) solveloop == SCIP_BENDERSSOLVELOOP_CONVEX or USERCONVEX and the subproblem is an LP
3351 * - the original form has been solved.
3352 * ii) solveloop == SCIP_BENDERSSOLVELOOP_CIP or USERCIP and the CIP for the subproblem has been
3353 * solved.
3354 * iii) or, only a convex check is performed.
3355 */
3356 if( ((solveloop == SCIP_BENDERSSOLVELOOP_CONVEX || solveloop == SCIP_BENDERSSOLVELOOP_USERCONVEX)
3357 && convexsub)
3358 || ((solveloop == SCIP_BENDERSSOLVELOOP_CIP || solveloop == SCIP_BENDERSSOLVELOOP_USERCIP)
3359 && !convexsub)
3360 || onlyconvexcheck )
3361 locnverified++;
3362 }
3363 }
3364 }
3365 }
3366
3367 /* checking whether the limits have been exceeded in the master problem */
3368 locstopped = SCIPisStopped(set->scip);
3369 }
3370 }
3371
3372 /* setting the input parameters to the local variables */
3373 SCIPsetDebugMsg(set, "Local variable values: nverified %d infeasible %u optimal %u stopped %u\n", locnverified,
3374 locinfeasible, locoptimal, locstopped);
3375 *nverified = locnverified;
3376 *infeasible = locinfeasible;
3377 *optimal = locoptimal;
3378 *stopped = locstopped;
3379
3380 return retcode;
3381}
3382
3383/** Calls the Benders' decompsition cuts for the given solve loop. There are four cases:
3384 * i) solveloop == SCIP_BENDERSSOLVELOOP_CONVEX - only the LP Benders' cuts are called
3385 * ii) solveloop == SCIP_BENDERSSOLVELOOP_CIP - only the CIP Benders' cuts are called
3386 * iii) solveloop == SCIP_BENDERSSOLVELOOP_USERCONVEX - only the LP Benders' cuts are called
3387 * iv) solveloop == SCIP_BENDERSSOLVELOOP_USERCIP - only the CIP Benders' cuts are called
3388 *
3389 * The priority of the results are: SCIP_CONSADDED (SCIP_SEPARATED), SCIP_DIDNOTFIND, SCIP_FEASIBLE, SCIP_DIDNOTRUN. In
3390 * this function, there are four levels of results that need to be assessed. These are:
3391 * i) The result from the individual cut for the subproblem
3392 * ii) The overall result for the subproblem from all cuts
3393 * iii) the overall result for the solve loop from all cuts
3394 * iv) the over all result from all solve loops.
3395 * In each level, the priority of results must be adhered to.
3397static
3399 SCIP_BENDERS* benders, /**< Benders' decomposition */
3400 SCIP_SET* set, /**< global SCIP settings */
3401 SCIP_SOL* sol, /**< primal CIP solution */
3402 SCIP_RESULT* result, /**< result of the pricing process */
3403 SCIP_BENDERSENFOTYPE type, /**< the type of solution being enforced */
3404 SCIP_BENDERSSOLVELOOP solveloop, /**< the current solve loop */
3405 SCIP_Bool checkint, /**< are the subproblems called during a check/enforce of integer sols? */
3406 SCIP_Bool* subprobsolved, /**< an array indicating the subproblems that were solved in this loop. */
3407 SCIP_BENDERSSUBSTATUS* substatus, /**< array to store the status of the subsystem */
3408 int* solveidx, /**< the indices of subproblems to be solved in this loop */
3409 int nsolveidx, /**< the number of subproblems to be solved in this loop */
3410 int** mergecands, /**< the subproblems that are merge candidates */
3411 int* npriomergecands, /**< the number of priority merge candidates. */
3412 int* nmergecands, /**< the number of merge candidates. */
3413 int* nsolveloops /**< the number of solve loops, is updated w.r.t added cuts */
3414 )
3415{
3416 SCIP_BENDERSCUT** benderscuts;
3417 SCIP_RESULT solveloopresult;
3418 int nbenderscuts;
3419 SCIP_Longint addedcuts = 0;
3420 int i;
3421 int j;
3422 int k;
3423 SCIP_Bool onlyconvexcheck;
3424
3425 assert(benders != NULL);
3426 assert(set != NULL);
3427
3428 /* getting the Benders' decomposition cuts */
3429 benderscuts = SCIPbendersGetBenderscuts(benders);
3430 nbenderscuts = SCIPbendersGetNBenderscuts(benders);
3431
3432 solveloopresult = SCIP_DIDNOTRUN;
3433
3434 /* in the case of an LNS check, only the convex relaxations of the subproblems will be solved. This is a performance
3435 * feature, since solving the convex relaxation is typically much faster than solving the corresponding CIP. While
3436 * the CIP is not solved during the LNS check, the solutions are still of higher quality than when Benders' is not
3437 * employed.
3438 */
3439 onlyconvexcheck = SCIPbendersOnlyCheckConvexRelax(benders, SCIPsetGetSubscipsOff(set));
3440
3441 /* It is only possible to add cuts to the problem if it has not already been solved */
3444 && (benders->cutcheck || type != SCIP_BENDERSENFOTYPE_CHECK) )
3445 {
3446 /* This is done in two loops. The first is by subproblem and the second is by cut type. */
3447 for( k = 0; k < nsolveidx; k++ )
3448 {
3449 SCIP_RESULT subprobresult;
3450 SCIP_Bool convexsub;
3451
3452 i = solveidx[k];
3453
3455
3456 /* cuts can only be generated if the subproblem is not independent and if it has been solved. Additionally, the
3457 * status of the subproblem solving must not be INFEASIBLE while in a cut strengthening round.
3458 * The subproblem solved flag is important for the user-defined subproblem solving methods
3459 */
3460 if( subproblemIsActive(benders, i) && subprobsolved[i]
3461 && !(substatus[i] == SCIP_BENDERSSUBSTATUS_INFEAS && benders->strengthenround) )
3462 {
3463 subprobresult = SCIP_DIDNOTRUN;
3464 for( j = 0; j < nbenderscuts; j++ )
3465 {
3466 SCIP_RESULT cutresult;
3467 SCIP_Longint prevaddedcuts;
3468
3469 assert(benderscuts[j] != NULL);
3470
3471 prevaddedcuts = SCIPbenderscutGetNFound(benderscuts[j]);
3472 cutresult = SCIP_DIDNOTRUN;
3473
3474 /* the result is updated only if a Benders' cut is generated or one was not found. However, if a cut has
3475 * been found in a previous iteration, then the result is returned as SCIP_CONSADDED or SCIP_SEPARATED.
3476 * This result is permitted because if a constraint was added, the solution that caused the error in the cut
3477 * generation will be cutoff from the master problem.
3478 */
3479 if( (SCIPbenderscutIsLPCut(benderscuts[j]) && (solveloop == SCIP_BENDERSSOLVELOOP_CONVEX
3480 || solveloop == SCIP_BENDERSSOLVELOOP_USERCONVEX))
3481 || (!SCIPbenderscutIsLPCut(benderscuts[j]) && ((solveloop == SCIP_BENDERSSOLVELOOP_CIP && !convexsub)
3482 || solveloop == SCIP_BENDERSSOLVELOOP_USERCIP)) )
3483 SCIP_CALL( SCIPbenderscutExec(benderscuts[j], set, benders, sol, i, type, &cutresult) );
3484
3485 addedcuts += (SCIPbenderscutGetNFound(benderscuts[j]) - prevaddedcuts);
3486
3487 /* the result is updated only if a Benders' cut is generated */
3488 if( cutresult == SCIP_CONSADDED || cutresult == SCIP_SEPARATED )
3489 {
3490 subprobresult = cutresult;
3491
3492 benders->ncutsfound++;
3493
3494 /* at most a single cut is generated for each subproblem */
3495 break;
3496 }
3497 else
3498 {
3499 /* checking from lowest priority result */
3500 if( subprobresult == SCIP_DIDNOTRUN )
3501 subprobresult = cutresult;
3502 else if( subprobresult == SCIP_FEASIBLE && cutresult == SCIP_DIDNOTFIND )
3503 subprobresult = cutresult;
3504 /* if the subprobresult is SCIP_DIDNOTFIND, then it can't be updated. */
3505 }
3506 }
3507
3508 /* the highest priority for the results is CONSADDED and SEPARATED. The solveloopresult will always be
3509 * updated if the subprobresult is either of these.
3510 */
3511 if( subprobresult == SCIP_CONSADDED || subprobresult == SCIP_SEPARATED )
3512 {
3513 solveloopresult = subprobresult;
3514 }
3515 else if( subprobresult == SCIP_FEASIBLE )
3516 {
3517 /* updating the solve loop result based upon the priority */
3518 if( solveloopresult == SCIP_DIDNOTRUN )
3519 solveloopresult = subprobresult;
3520 }
3521 else if( subprobresult == SCIP_DIDNOTFIND )
3522 {
3523 /* updating the solve loop result based upon the priority */
3524 if( solveloopresult == SCIP_DIDNOTRUN || solveloopresult == SCIP_FEASIBLE )
3525 solveloopresult = subprobresult;
3526
3527 /* since a cut was not found, then merging could be useful to avoid this in subsequent iterations. The
3528 * candidate is labelled as a non-priority merge candidate
3529 */
3530 if( substatus[i] != SCIP_BENDERSSUBSTATUS_OPTIMAL )
3531 {
3532 (*mergecands)[(*nmergecands)] = i;
3533 (*nmergecands)++;
3534 }
3535 }
3536 else if( subprobresult == SCIP_DIDNOTRUN )
3537 {
3538 /* if the subproblem is infeasible and no cut generation methods were run, then the infeasibility will
3539 * never be resolved. As such, the subproblem will be merged into the master problem. If the subproblem
3540 * was not infeasible, then it is added as a possible merge candidate
3541 */
3542 if( substatus[i] == SCIP_BENDERSSUBSTATUS_INFEAS )
3543 {
3544 (*mergecands)[(*nmergecands)] = (*mergecands)[(*npriomergecands)];
3545 (*mergecands)[(*npriomergecands)] = i;
3546 (*npriomergecands)++;
3547 (*nmergecands)++;
3548 }
3549 else if( substatus[i] != SCIP_BENDERSSUBSTATUS_OPTIMAL )
3550 {
3551 (*mergecands)[(*nmergecands)] = i;
3552 (*nmergecands)++;
3553 }
3554 }
3555 }
3556 }
3557 }
3558
3559 /* updating the overall result based upon the priorities */
3560 if( solveloopresult == SCIP_CONSADDED || solveloopresult == SCIP_SEPARATED )
3561 {
3562 (*result) = solveloopresult;
3563 }
3564 else if( solveloopresult == SCIP_FEASIBLE )
3565 {
3566 /* updating the solve loop result based upon the priority */
3567 if( (*result) == SCIP_DIDNOTRUN )
3568 (*result) = solveloopresult;
3569 }
3570 else if( solveloopresult == SCIP_DIDNOTFIND )
3571 {
3572 /* updating the solve loop result based upon the priority */
3573 if( (*result) == SCIP_DIDNOTRUN || (*result) == SCIP_FEASIBLE )
3574 (*result) = solveloopresult;
3575 }
3576
3577 /* if no cuts were added, then the number of solve loops is increased */
3578 if( addedcuts == 0 && SCIPbendersGetNConvexSubproblems(benders) < SCIPbendersGetNSubproblems(benders)
3579 && checkint && !onlyconvexcheck )
3580 (*nsolveloops) = 2;
3581
3582 return SCIP_OKAY;
3583}
3584
3585/** Solves the subproblem using the current master problem solution.
3586 *
3587 * The checkint flag indicates whether integer feasibility can be assumed. If it is not assumed, i.e. checkint ==
3588 * FALSE, then only the convex relaxations of the subproblems are solved. If integer feasibility is assumed, i.e.
3589 * checkint == TRUE, then the convex relaxations and the full CIP are solved to generate Benders' cuts and check
3590 * solution feasibility.
3591 *
3592 * TODO: consider allowing the possibility to pass solution information back from the subproblems instead of the scip
3593 * instance. This would allow the use of different solvers for the subproblems, more importantly allowing the use of an
3594 * LP solver for LP subproblems.
3595 */
3597 SCIP_BENDERS* benders, /**< Benders' decomposition */
3598 SCIP_SET* set, /**< global SCIP settings */
3599 SCIP_SOL* sol, /**< primal CIP solution */
3600 SCIP_RESULT* result, /**< result of the pricing process */
3601 SCIP_Bool* infeasible, /**< is the master problem infeasible with respect to the Benders' cuts? */
3602 SCIP_Bool* auxviol, /**< set to TRUE only if the solution is feasible but the aux vars are violated */
3603 SCIP_BENDERSENFOTYPE type, /**< the type of solution being enforced */
3604 SCIP_Bool checkint /**< should the integer solution be checked by the subproblems */
3605 )
3606{
3607 int nsubproblems;
3608 int subproblemcount;
3609 int nsolveloops;
3610 int nverified;
3611 int nsolved;
3612 int* mergecands;
3613 int npriomergecands;
3614 int nmergecands;
3615 int* solveidx;
3616 int* executedidx;
3617 int nsolveidx;
3618 int nexecutedidx;
3619 int nfree;
3620 SCIP_Bool* subprobsolved;
3621 SCIP_BENDERSSUBSTATUS* substatus;
3622 SCIP_Bool optimal;
3623 SCIP_Bool allverified;
3624 SCIP_Bool success;
3625 SCIP_Bool stopped;
3626 int i;
3627 int l;
3628
3629 success = TRUE;
3630 stopped = FALSE;
3631
3632 SCIPsetDebugMsg(set, "Starting Benders' decomposition subproblem solving. type %d checkint %u\n", type, checkint);
3633
3634#ifdef SCIP_MOREDEBUG
3635 SCIP_CALL( SCIPprintSol(set->scip, sol, NULL, FALSE) );
3636#endif
3637
3638 /* start timing */
3639 SCIPclockStart(benders->bendersclock, set);
3640
3641 nsubproblems = SCIPbendersGetNSubproblems(benders);
3642
3643 (*auxviol) = FALSE;
3644 (*infeasible) = FALSE;
3645
3646 /* It is assumed that the problem is optimal, until a subproblem is found not to be optimal. However, not all
3647 * subproblems could be checked in each iteration. As such, it is not possible to state that the problem is optimal
3648 * if not all subproblems are checked. Situations where this may occur is when a subproblem is a MIP and only the LP
3649 * is solved. Also, in a distributed computation, then it may be advantageous to only solve some subproblems before
3650 * resolving the master problem. As such, for a problem to be optimal, then (optimal && allverified) == TRUE
3651 */
3652 optimal = TRUE;
3653 nverified = 0;
3654 nsolved = 0;
3655
3656 assert(benders != NULL);
3657 assert(result != NULL);
3658 assert(infeasible != NULL);
3659 assert(auxviol != NULL);
3660
3661 /* if the Benders' decomposition is called from a sub-SCIP and the sub-SCIPs have been deactivated, then it is
3662 * assumed that this is an LNS heuristic. As such, the check is not performed and the solution is assumed to be
3663 * feasible
3664 */
3665 if( benders->iscopy && set->subscipsoff
3666 && (!benders->lnscheck
3667 || (benders->lnsmaxdepth > -1 && SCIPgetDepth(benders->sourcescip) >= benders->lnsmaxdepth)
3668 || (benders->lnsmaxcalls > -1 && SCIPbendersGetNCalls(benders) >= benders->lnsmaxcalls)
3669 || (type != SCIP_BENDERSENFOTYPE_CHECK && SCIPgetDepth(set->scip) == 0 && benders->lnsmaxcallsroot > -1
3670 && SCIPbendersGetNCalls(benders) >= benders->lnsmaxcallsroot)) )
3671 {
3672 (*result) = SCIP_DIDNOTRUN;
3673 return SCIP_OKAY;
3674 }
3675
3676 /* it is not necessary to check all primal solutions by solving the Benders' decomposition subproblems.
3677 * Only the improving solutions are checked to improve efficiency of the algorithm.
3678 * If the solution is non-improving, the result FEASIBLE is returned. While this may be incorrect w.r.t to the
3679 * Benders' subproblems, this solution will never be the optimal solution. A non-improving solution may be used
3680 * within LNS primal heuristics. If this occurs, the improving solution, if found, will be checked by the solving
3681 * the Benders' decomposition subproblems.
3682 * TODO: Add a parameter to control this behaviour.
3683 */
3684 if( checkint && SCIPsetIsLE(set, SCIPgetPrimalbound(set->scip)*(int)SCIPgetObjsense(set->scip),
3685 SCIPgetSolOrigObj(set->scip, sol)*(int)SCIPgetObjsense(set->scip)) )
3686 {
3687 (*result) = SCIP_DIDNOTRUN;
3688 return SCIP_OKAY;
3689 }
3690
3691 /* if the enforcement type is SCIP_BENDERSENFOTYPE_LP and the LP is currently unbounded. This could mean that there
3692 * is no lower bound on the auxiliary variables. In this case, we try to update the lower bound for the auxiliary
3693 * variables.
3694 */
3696 && benders->updateauxvarbound )
3697 {
3698 SCIP_CALL( updateAuxiliaryVarLowerbound(benders, set, result) );
3699
3700 /* the auxiliary variable bound will only be updated once. */
3701 benders->updateauxvarbound = FALSE;
3702 }
3703
3704 /* sets the stored objective function values of the subproblems to infinity */
3706
3707 *result = SCIP_DIDNOTRUN;
3708
3709 if( benders->benderspresubsolve != NULL && !benders->strengthenround )
3710 {
3711 SCIP_Bool skipsolve;
3712
3713 skipsolve = FALSE;
3714 SCIP_CALL( benders->benderspresubsolve(set->scip, benders, sol, type, checkint, infeasible, auxviol, &skipsolve,
3715 result) );
3716
3717 /* evaluate result */
3718 if( (*result) != SCIP_DIDNOTRUN
3719 && (*result) != SCIP_FEASIBLE
3720 && (*result) != SCIP_INFEASIBLE
3721 && (*result) != SCIP_CONSADDED
3722 && (*result) != SCIP_SEPARATED )
3723 {
3724 SCIPerrorMessage("the user-defined pre subproblem solving method for the Benders' decomposition <%s> returned "
3725 "invalid result <%d>\n", benders->name, *result);
3726 return SCIP_INVALIDRESULT;
3727 }
3728
3729 /* if the solve must be skipped, then the solving loop is exited and the user defined result is returned */
3730 if( skipsolve )
3731 {
3732 SCIPsetDebugMsg(set, "skipping the subproblem solving for Benders' decomposition <%s>. "
3733 "returning result <%d>\n", benders->name, *result);
3734 return SCIP_OKAY;
3735 }
3736 }
3737
3738 /* the cut strengthening is performed before the regular subproblem solve is called. To avoid recursion, the flag
3739 * strengthenround is set to TRUE when the cut strengthening is performed. The cut strengthening is not performed as
3740 * part of the large neighbourhood Benders' search.
3741 *
3742 * NOTE: cut strengthening is only applied for fractional solutions and integer solutions if there are no CIP
3743 * subproblems.
3744 */
3745 if( benders->strengthenenabled && !benders->strengthenround && !benders->iscopy
3746 && (!checkint || SCIPbendersGetNConvexSubproblems(benders) == SCIPbendersGetNSubproblems(benders)) )
3747 {
3748 SCIP_Bool skipsolve;
3749
3750 benders->strengthenround = TRUE;
3751 /* if the user has not requested the solve to be skipped, then the cut strengthening is performed */
3752 SCIP_CALL( performInteriorSolCutStrengthening(benders, set, sol, type, checkint, FALSE, infeasible, auxviol,
3753 &skipsolve, result) );
3754 benders->strengthenround = FALSE;
3755
3756 /* if the solve must be skipped, then the solving loop is exited and the user defined result is returned */
3757 if( skipsolve )
3758 {
3759 SCIPsetDebugMsg(set, "skipping the subproblem solving because cut strengthening found a cut "
3760 "for Benders' decomposition <%s>. Returning result <%d>\n", benders->name, *result);
3761 return SCIP_OKAY;
3762 }
3763
3764 /* the result flag need to be reset to DIDNOTRUN for the main subproblem solve */
3765 (*result) = SCIP_DIDNOTRUN;
3766 }
3767
3768 /* allocating memory for the infeasible subproblem array */
3769 SCIP_CALL( SCIPallocClearBlockMemoryArray(set->scip, &subprobsolved, nsubproblems) );
3770 SCIP_CALL( SCIPallocClearBlockMemoryArray(set->scip, &substatus, nsubproblems) );
3771 SCIP_CALL( SCIPallocClearBlockMemoryArray(set->scip, &mergecands, nsubproblems) );
3772 npriomergecands = 0;
3773 nmergecands = 0;
3774
3775 /* allocating the memory for the subproblem solving and cut generation indices */
3776 SCIP_CALL( SCIPallocClearBlockMemoryArray(set->scip, &solveidx, nsubproblems) );
3777 SCIP_CALL( SCIPallocClearBlockMemoryArray(set->scip, &executedidx, nsubproblems) );
3778 nsolveidx = 0;
3779 nexecutedidx = 0;
3780
3781 /* only a subset of the subproblems are initially solved. Both solving loops are executed for the subproblems to
3782 * check whether any cuts are generated. If a cut is generated, then no further subproblems are solved. If a cut is
3783 * not generated, then an additional set of subproblems are solved.
3784 */
3785 while( nsolved < nsubproblems )
3786 {
3787 /* getting the indices for the subproblems that will be solved */
3788 createSolveSubproblemIndexList(benders, set, type, &solveidx, &nsolveidx);
3789
3790 /* by default the number of solve loops is 1. This is the case if all subproblems are LP or the user has defined a
3791 * benderssolvesub callback. If there is a subproblem that is not an LP, then 2 solve loops are performed. The first
3792 * loop is the LP solving loop, the second solves the subproblem to integer optimality.
3793 */
3794 nsolveloops = 1;
3795
3796 for( l = 0; l < nsolveloops; l++ )
3797 {
3798 SCIP_BENDERSSOLVELOOP solveloop; /* identifies what problem type is solve in this solve loop */
3799
3800 /* if either benderssolvesubconvex or benderssolvesub are implemented, then the user callbacks are invoked */
3801 if( benders->benderssolvesubconvex != NULL || benders->benderssolvesub != NULL )
3802 {
3803 if( l == 0 )
3805 else
3807 }
3808 else
3809 solveloop = (SCIP_BENDERSSOLVELOOP) l;
3810
3811 /* solving the subproblems for this round of enforcement/checking. */
3812 SCIP_CALL( solveBendersSubproblems(benders, set, sol, type, solveloop, checkint, &nverified,
3813 solveidx, nsolveidx, &subprobsolved, &substatus, infeasible, &optimal, &stopped) );
3814
3815 /* if the solving has been stopped, then the subproblem solving and cut generation must terminate */
3816 if( stopped )
3817 break;
3818
3819 /* Generating cuts for the subproblems. Cuts are only generated when the solution is from primal heuristics,
3820 * relaxations or the LP
3821 */
3822 if( type != SCIP_BENDERSENFOTYPE_PSEUDO )
3823 {
3824 SCIP_CALL( generateBendersCuts(benders, set, sol, result, type, solveloop, checkint, subprobsolved,
3825 substatus, solveidx, nsolveidx, &mergecands, &npriomergecands, &nmergecands, &nsolveloops) );
3826 }
3827 else
3828 {
3829 /* The first solving loop solves the convex subproblems and the convex relaxations of the CIP subproblems. The
3830 * second solving loop solves the CIP subproblems. The second solving loop is only called if the integer
3831 * feasibility is being checked and if the convex subproblems and convex relaxations are not infeasible.
3832 */
3833 if( !(*infeasible) && checkint && !SCIPbendersOnlyCheckConvexRelax(benders, SCIPsetGetSubscipsOff(set))
3835 nsolveloops = 2;
3836 }
3837 }
3838
3839 nsolved += nsolveidx;
3840
3841 /* storing the indices of the subproblems for which the solving loop was executed */
3842 for( i = 0; i < nsolveidx; i++ )
3843 executedidx[nexecutedidx++] = solveidx[i];
3844
3845 /* if the result is CONSADDED or SEPARATED, then a cut is generated and no further subproblem processing is
3846 * required
3847 */
3848 if( (*result) == SCIP_CONSADDED || (*result) == SCIP_SEPARATED )
3849 break;
3850 }
3851
3852 /* inserting the subproblems into the priority queue for the next solve call */
3853 SCIP_CALL( updateSubproblemStatQueue(benders, executedidx, nexecutedidx, TRUE) );
3854
3855 if( stopped )
3856 goto TERMINATE;
3857
3858 allverified = (nverified == nsubproblems);
3859
3860 SCIPsetDebugMsg(set, "End Benders' decomposition subproblem solve. result %d infeasible %u auxviol %u nverified %d\n",
3861 *result, *infeasible, *auxviol, nverified);
3862
3863#ifdef SCIP_DEBUG
3864 if( (*result) == SCIP_CONSADDED )
3865 {
3866 SCIPsetDebugMsg(set, "Benders' decomposition: Cut added\n");
3867 }
3868#endif
3869
3870 /* if the number of checked pseudo solutions exceeds a set limit, then all subproblems are passed as merge
3871 * candidates. Currently, merging subproblems into the master problem is the only method for resolving numerical
3872 * troubles.
3873 *
3874 * We are only interested in the pseudo solutions that have been checked completely for integrality. This is
3875 * identified by checkint == TRUE. This means that the Benders' decomposition constraint is one of the last
3876 * constraint handlers that must resolve the infeasibility. If the Benders' decomposition framework can't resolve the
3877 * infeasibility, then this will result in an error.
3878 */
3879 if( type == SCIP_BENDERSENFOTYPE_PSEUDO && checkint )
3880 {
3881 benders->npseudosols++;
3882
3883 if( benders->npseudosols > BENDERS_MAXPSEUDOSOLS )
3884 {
3885 /* if a priority merge candidate already exists, then no other merge candidates need to be added.*/
3886 if( npriomergecands == 0 )
3887 {
3888 /* all subproblems are added to the merge candidate list. The first active subproblem is added as a
3889 * priority merge candidate
3890 */
3891 nmergecands = 0;
3892 npriomergecands = 1;
3893 for( i = 0; i < nsubproblems; i++ )
3894 {
3895 /* only active subproblems are added to the merge candidate list */
3896 if( subproblemIsActive(benders, i) )
3897 {
3898 mergecands[nmergecands] = i;
3899 nmergecands++;
3900 }
3901 }
3902
3903 SCIPverbMessage(set->scip, SCIP_VERBLEVEL_HIGH, NULL, " The number of checked pseudo solutions exceeds the "
3904 "limit of %d. All active subproblems are merge candidates, with subproblem %d a priority candidate.\n",
3905 BENDERS_MAXPSEUDOSOLS, mergecands[0]);
3906 }
3907 }
3908 }
3909 else
3910 benders->npseudosols = 0;
3911
3912 /* if the result is SCIP_DIDNOTFIND, then there was a error in generating cuts in all subproblems that are not
3913 * optimal. This result does not cutoff any solution, so the Benders' decomposition algorithm will fail.
3914 *
3915 * It could happen that the cut strengthening approach causes an error the cut generation. In this case, an error
3916 * should not be thrown. So, this check will be skipped when in a strengthening round.
3917 * TODO: Work out a way to ensure Benders' decomposition does not terminate due to a SCIP_DIDNOTFIND result.
3918 */
3919 if( (*result) == SCIP_DIDNOTFIND && !benders->strengthenround )
3920 {
3921 if( type == SCIP_BENDERSENFOTYPE_PSEUDO )
3922 (*result) = SCIP_SOLVELP;
3923 else
3924 (*result) = SCIP_INFEASIBLE;
3925
3926 SCIPerrorMessage("An error was found when generating cuts for non-optimal subproblems of Benders' "
3927 "decomposition <%s>. Consider merging the infeasible subproblems into the master problem.\n", SCIPbendersGetName(benders));
3928
3929 /* since no other cuts are generated, then this error will result in a crash. It is possible to avoid the error,
3930 * by merging the affected subproblem into the master problem.
3931 *
3932 * NOTE: If the error occurs while checking solutions, i.e. SCIP_BENDERSENFOTYPE_CHECK, then it is valid to set
3933 * the result to SCIP_INFEASIBLE and the success flag to TRUE
3934 */
3935 if( type != SCIP_BENDERSENFOTYPE_CHECK )
3936 success = FALSE;
3937
3938 goto POSTSOLVE;
3939 }
3940
3941 if( type == SCIP_BENDERSENFOTYPE_PSEUDO )
3942 {
3943 if( (*infeasible) || !allverified )
3944 (*result) = SCIP_SOLVELP;
3945 else
3946 {
3947 (*result) = SCIP_FEASIBLE;
3948
3949 /* if the subproblems are not infeasible, but they are also not optimal. This means that there is a violation
3950 * in the auxiliary variable values. In this case, a feasible result is returned with the auxviol flag set to
3951 * TRUE.
3952 */
3953 (*auxviol) = !optimal;
3954 }
3955 }
3956 else if( checkint && (type == SCIP_BENDERSENFOTYPE_CHECK
3957 || ((*result) != SCIP_CONSADDED && (*result) != SCIP_SEPARATED)) )
3958 {
3959 /* if the subproblems are being solved as part of conscheck, then the results flag must be returned after the solving
3960 * has completed.
3961 */
3962 if( (*infeasible) || !allverified )
3963 (*result) = SCIP_INFEASIBLE;
3964 else
3965 {
3966 (*result) = SCIP_FEASIBLE;
3967
3968 /* if the subproblems are not infeasible, but they are also not optimal. This means that there is a violation
3969 * in the auxiliary variable values. In this case, a feasible result is returned with the auxviol flag set to
3970 * TRUE.
3971 */
3972 (*auxviol) = !optimal;
3973 }
3974 }
3975
3976POSTSOLVE:
3977 /* calling the post-solve call back for the Benders' decomposition algorithm. This allows the user to work directly
3978 * with the solved subproblems and the master problem */
3979 if( benders->benderspostsolve != NULL )
3980 {
3981 SCIP_Bool merged;
3982
3983 merged = FALSE;
3984
3985 SCIP_CALL( benders->benderspostsolve(set->scip, benders, sol, type, mergecands, npriomergecands, nmergecands,
3986 checkint, (*infeasible), &merged) );
3987
3988 if( merged )
3989 {
3990 (*result) = SCIP_CONSADDED;
3991
3992 /* since subproblems have been merged, then constraints have been added. This could resolve the unresolved
3993 * infeasibility, so the error has been corrected.
3994 */
3995 success = TRUE;
3996 }
3997 else if( !success )
3998 {
3999 SCIPerrorMessage("An error occurred during Benders' decomposition cut generations and no merging had been "
4000 "performed. It is not possible to continue solving the problem by Benders' decomposition\n");
4001 }
4002 }
4003
4004TERMINATE:
4005 /* if the solving process has stopped, then all subproblems need to be freed */
4006 if( stopped )
4007 nfree = nsubproblems;
4008 else
4009 nfree = nexecutedidx;
4010
4011 /* freeing the subproblems after the cuts are generated */
4012 subproblemcount = 0;
4013 while( subproblemcount < nfree )
4014 {
4015 int subidx;
4016
4017 if( stopped )
4018 subidx = subproblemcount;
4019 else
4020 subidx = executedidx[subproblemcount];
4021
4022 SCIP_CALL( SCIPbendersFreeSubproblem(benders, set, subidx) );
4023
4024 subproblemcount++;
4025 }
4026
4027#ifndef NDEBUG
4028 for( i = 0; i < nsubproblems; i++ )
4029 assert(SCIPbendersSubproblem(benders, i) == NULL
4031 || !SCIPinProbing(SCIPbendersSubproblem(benders, i))
4032 || !subproblemIsActive(benders, i));
4033#endif
4034
4035 /* increment the number of calls to the Benders' decomposition subproblem solve */
4036 benders->ncalls++;
4037
4038 SCIPsetDebugMsg(set, "End Benders' decomposition execution method. result %d infeasible %u auxviol %u\n", *result,
4039 *infeasible, *auxviol);
4040
4041 /* end timing */
4042 SCIPclockStop(benders->bendersclock, set);
4043
4044 /* freeing memory */
4045 SCIPfreeBlockMemoryArray(set->scip, &executedidx, nsubproblems);
4046 SCIPfreeBlockMemoryArray(set->scip, &solveidx, nsubproblems);
4047 SCIPfreeBlockMemoryArray(set->scip, &mergecands, nsubproblems);
4048 SCIPfreeBlockMemoryArray(set->scip, &substatus, nsubproblems);
4049 SCIPfreeBlockMemoryArray(set->scip, &subprobsolved, nsubproblems);
4050
4051 /* if there was an error in generating cuts and merging was not performed, then the solution is perturbed in an
4052 * attempt to generate a cut and correct the infeasibility
4053 */
4054 if( !success && !stopped )
4055 {
4056 SCIP_Bool skipsolve;
4057 SCIP_RESULT perturbresult;
4058
4059 skipsolve = FALSE;
4060
4061 benders->strengthenround = TRUE;
4062 /* if the user has not requested the solve to be skipped, then the cut strengthening is performed */
4063 SCIP_CALL( performInteriorSolCutStrengthening(benders, set, sol, type, checkint, TRUE, infeasible, auxviol,
4064 &skipsolve, &perturbresult) );
4065 benders->strengthenround = FALSE;
4066
4067 if( perturbresult == SCIP_CONSADDED || perturbresult == SCIP_SEPARATED )
4068 (*result) = perturbresult;
4069
4070 success = skipsolve;
4071 }
4072
4073 /* if the Benders' decomposition subproblem check stopped, then we don't have a valid result. In this case, the
4074 * safest thing to do is report INFEASIBLE.
4075 */
4076 if( stopped )
4077 (*result) = SCIP_INFEASIBLE;
4078
4079 /* if the subproblem verification identifies the solution as feasible, then a check whether slack variables have been
4080 * used is necessary. If any slack variables are non-zero, then the solution is reverified after the objective
4081 * coefficient for the slack variables is increased.
4082 */
4083 if( (*result) == SCIP_FEASIBLE )
4084 {
4085 SCIP_Bool activeslack;
4086
4087 SCIP_CALL( SCIPbendersSolSlackVarsActive(benders, &activeslack) );
4088 SCIPsetDebugMsg(set, "Type: %d Active slack: %u Feasibility Phase: %u\n", type, activeslack,
4089 benders->feasibilityphase);
4090 if( activeslack )
4091 {
4092 if( type == SCIP_BENDERSENFOTYPE_CHECK )
4093 (*result) = SCIP_INFEASIBLE;
4094 else
4095 {
4096 /* increasing the value of the slack variable by a factor of 10 */
4097 benders->slackvarcoef *= 10.0;
4098
4099 if( benders->slackvarcoef <= benders->maxslackvarcoef )
4100 {
4101 SCIPmessagePrintVerbInfo(SCIPgetMessagehdlr(set->scip), set->disp_verblevel, SCIP_VERBLEVEL_HIGH, "Increasing the slack variable coefficient to %g.\n", benders->slackvarcoef);
4102 }
4103 else
4104 {
4105 SCIPmessagePrintVerbInfo(SCIPgetMessagehdlr(set->scip), set->disp_verblevel, SCIP_VERBLEVEL_HIGH, "Fixing the slack variables to zero.\n");
4106 }
4107
4108 /* resolving the subproblems with an increased slack variable */
4109 SCIP_CALL( SCIPsolveBendersSubproblems(set->scip, benders, sol, result, infeasible, auxviol, type, checkint) );
4110 }
4111 }
4112 else if( benders->feasibilityphase )
4113 {
4114 if( type != SCIP_BENDERSENFOTYPE_CHECK )
4115 {
4116 /* disabling the feasibility phase */
4117 benders->feasibilityphase = FALSE;
4118
4119 /* resolving the subproblems with the slack variables set to zero */
4120 SCIP_CALL( SCIPsolveBendersSubproblems(set->scip, benders, sol, result, infeasible, auxviol, type, checkint) );
4121 }
4122 }
4123 }
4124
4125 if( !success )
4126 return SCIP_ERROR;
4127 else
4128 return SCIP_OKAY;
4129}
4130
4131/** solves the user-defined subproblem solving function */
4132static
4134 SCIP_BENDERS* benders, /**< Benders' decomposition */
4135 SCIP_SET* set, /**< global SCIP settings */
4136 SCIP_SOL* sol, /**< primal CIP solution */
4137 int probnumber, /**< the subproblem number */
4138 SCIP_BENDERSSOLVELOOP solveloop, /**< the solve loop iteration. The first iter is for LP, the second for IP */
4139 SCIP_Bool* infeasible, /**< returns whether the current subproblem is infeasible */
4140 SCIP_Real* objective, /**< the objective function value of the subproblem */
4141 SCIP_RESULT* result /**< the result from solving the subproblem */
4142 )
4143{
4144 assert(benders != NULL);
4145 assert(probnumber >= 0 && probnumber < benders->nsubproblems);
4146 assert(benders->benderssolvesubconvex != NULL || benders->benderssolvesub != NULL);
4147
4148 assert(solveloop == SCIP_BENDERSSOLVELOOP_USERCONVEX || solveloop == SCIP_BENDERSSOLVELOOP_USERCIP);
4149
4150 (*objective) = -SCIPsetInfinity(set);
4151
4152 /* calls the user defined subproblem solving method. Only the convex relaxations are solved during the Large
4153 * Neighbourhood Benders' Search. */
4154 if( solveloop == SCIP_BENDERSSOLVELOOP_USERCONVEX )
4155 {
4156 if( benders->benderssolvesubconvex != NULL )
4157 {
4158 SCIP_CALL( benders->benderssolvesubconvex(set->scip, benders, sol, probnumber,
4159 SCIPbendersOnlyCheckConvexRelax(benders, SCIPsetGetSubscipsOff(set)), objective, result) );
4160 }
4161 else
4162 (*result) = SCIP_DIDNOTRUN;
4163 }
4164 else if( solveloop == SCIP_BENDERSSOLVELOOP_USERCIP )
4165 {
4166 if( benders->benderssolvesub != NULL )
4167 {
4168 SCIP_CALL( benders->benderssolvesub(set->scip, benders, sol, probnumber, objective, result) );
4169 }
4170 else
4171 (*result) = SCIP_DIDNOTRUN;
4172 }
4173
4174 /* evaluate result */
4175 if( (*result) != SCIP_DIDNOTRUN
4176 && (*result) != SCIP_FEASIBLE
4177 && (*result) != SCIP_INFEASIBLE
4178 && (*result) != SCIP_UNBOUNDED )
4179 {
4180 SCIPerrorMessage("the user-defined solving method for the Benders' decomposition <%s> returned invalid result <%d>\n",
4181 benders->name, *result);
4182 return SCIP_INVALIDRESULT;
4183 }
4184
4185 if( (*result) == SCIP_INFEASIBLE )
4186 (*infeasible) = TRUE;
4187
4188 if( (*result) == SCIP_FEASIBLE
4189 && (SCIPsetIsInfinity(set, -(*objective)) || SCIPsetIsInfinity(set, (*objective))) )
4190 {
4191 SCIPerrorMessage("the user-defined solving method for the Benders' decomposition <%s> returned objective value %g\n",
4192 benders->name, (*objective));
4193 return SCIP_ERROR;
4194 }
4195
4196 /* if the result is SCIP_DIDNOTFIND, then an error is returned and SCIP will terminate. */
4197 if( (*result) == SCIP_DIDNOTFIND )
4198 return SCIP_ERROR;
4199 else
4200 return SCIP_OKAY;
4201}
4203/** executes the subproblem solving process */
4205 SCIP_BENDERS* benders, /**< Benders' decomposition */
4206 SCIP_SET* set, /**< global SCIP settings */
4207 SCIP_SOL* sol, /**< primal CIP solution */
4208 int probnumber, /**< the subproblem number */
4209 SCIP_BENDERSSOLVELOOP solveloop, /**< the solve loop iteration. The first iter is for LP, the second for IP */
4210 SCIP_Bool enhancement, /**< is the solve performed as part of and enhancement? */
4211 SCIP_Bool* solved, /**< flag to indicate whether the subproblem was solved */
4212 SCIP_Bool* infeasible, /**< returns whether the current subproblem is infeasible */
4213 SCIP_BENDERSENFOTYPE type /**< the enforcement type calling this function */
4214 )
4215{ /*lint --e{715}*/
4216 SCIP* subproblem;
4217 SCIP_RESULT result;
4218 SCIP_Real objective;
4219 SCIP_STATUS solvestatus = SCIP_STATUS_UNKNOWN;
4220
4221 assert(benders != NULL);
4222 assert(probnumber >= 0 && probnumber < benders->nsubproblems);
4223
4224 SCIPsetDebugMsg(set, "Benders' decomposition: solving subproblem %d\n", probnumber);
4225
4226 result = SCIP_DIDNOTRUN;
4227 objective = SCIPsetInfinity(set);
4228
4229 subproblem = SCIPbendersSubproblem(benders, probnumber);
4230
4231 if( subproblem == NULL && (benders->benderssolvesubconvex == NULL || benders->benderssolvesub == NULL) )
4232 {
4233 SCIPerrorMessage("The subproblem %d is set to NULL, but both bendersSolvesubconvex%s and bendersSolvesub%s "
4234 "are not defined.\n", probnumber, benders->name, benders->name);
4235 SCIPABORT();
4236 return SCIP_ERROR;
4237 }
4238
4239 /* initially setting the solved flag to FALSE */
4240 (*solved) = FALSE;
4241
4242 /* if the subproblem solve callback is implemented, then that is used instead of the default setup */
4243 if( solveloop == SCIP_BENDERSSOLVELOOP_USERCONVEX || solveloop == SCIP_BENDERSSOLVELOOP_USERCIP )
4244 {
4245 /* calls the user defined subproblem solving method. Only the convex relaxations are solved during the Large
4246 * Neighbourhood Benders' Search. */
4247 SCIP_CALL( executeUserDefinedSolvesub(benders, set, sol, probnumber, solveloop, infeasible, &objective, &result) );
4248
4249 /* if the result is DIDNOTRUN, then the subproblem was not solved */
4250 (*solved) = (result != SCIP_DIDNOTRUN);
4251 }
4252 else if( subproblem != NULL )
4253 {
4254 /* setting up the subproblem */
4255 if( solveloop == SCIP_BENDERSSOLVELOOP_CONVEX )
4256 {
4257 SCIP_CALL( SCIPbendersSetupSubproblem(benders, set, sol, probnumber, type) );
4258
4259 /* if the limits of the master problem were hit during the setup process, then the subproblem will not have
4260 * been setup. In this case, the solving function must be exited.
4261 */
4262 if( !SCIPbendersSubproblemIsSetup(benders, probnumber) )
4263 {
4264 SCIPbendersSetSubproblemObjval(benders, probnumber, SCIPsetInfinity(set));
4265 (*solved) = FALSE;
4266 return SCIP_OKAY;
4267 }
4268 }
4269 else
4270 {
4271 SCIP_CALL( updateEventhdlrUpperbound(benders, probnumber, SCIPbendersGetAuxiliaryVarVal(benders, set, sol, probnumber)) );
4272 }
4273
4274 /* solving the subproblem
4275 * the LP of the subproblem is solved in the first solveloop.
4276 * In the second solve loop, the MIP problem is solved */
4277 if( solveloop == SCIP_BENDERSSOLVELOOP_CONVEX
4279 {
4280 SCIP_CALL( SCIPbendersSolveSubproblemLP(set->scip, benders, probnumber, &solvestatus, &objective) );
4281
4282 /* if the (N)LP was solved without error, then the subproblem is labelled as solved */
4283 if( solvestatus == SCIP_STATUS_OPTIMAL || solvestatus == SCIP_STATUS_INFEASIBLE )
4284 (*solved) = TRUE;
4285
4286 if( solvestatus == SCIP_STATUS_INFEASIBLE )
4287 (*infeasible) = TRUE;
4288 }
4289 else
4290 {
4291 SCIP_SOL* bestsol;
4292
4293 SCIP_CALL( SCIPbendersSolveSubproblemCIP(set->scip, benders, probnumber, &solvestatus, FALSE) );
4294
4295 if( solvestatus == SCIP_STATUS_INFEASIBLE )
4296 (*infeasible) = TRUE;
4297
4298 /* if the generic subproblem solving methods are used, then the CIP subproblems are always solved. */
4299 (*solved) = TRUE;
4300
4301 bestsol = SCIPgetBestSol(subproblem);
4302 if( bestsol != NULL )
4303 objective = SCIPgetSolOrigObj(subproblem, bestsol)*(int)SCIPgetObjsense(set->scip);
4304 else
4305 objective = SCIPsetInfinity(set);
4306 }
4307 }
4308 else
4309 {
4310 SCIPABORT();
4311 }
4312
4313 if( !enhancement )
4314 {
4315 /* The following handles the cases when the subproblem is OPTIMAL, INFEASIBLE and UNBOUNDED.
4316 * If a subproblem is unbounded, then the auxiliary variables are set to -infinity and the unbounded flag is
4317 * returned as TRUE. No cut will be generated, but the result will be set to SCIP_FEASIBLE.
4318 */
4319 if( solveloop == SCIP_BENDERSSOLVELOOP_CONVEX || solveloop == SCIP_BENDERSSOLVELOOP_CIP )
4320 {
4321 /* TODO: Consider whether other solutions status should be handled */
4322 if( solvestatus == SCIP_STATUS_OPTIMAL )
4323 SCIPbendersSetSubproblemObjval(benders, probnumber, objective);
4324 else if( solvestatus == SCIP_STATUS_INFEASIBLE )
4325 SCIPbendersSetSubproblemObjval(benders, probnumber, SCIPsetInfinity(set));
4326 else if( solvestatus == SCIP_STATUS_USERINTERRUPT || solvestatus == SCIP_STATUS_BESTSOLLIMIT )
4327 SCIPbendersSetSubproblemObjval(benders, probnumber, objective);
4328 else if( solvestatus == SCIP_STATUS_MEMLIMIT || solvestatus == SCIP_STATUS_TIMELIMIT
4329 || solvestatus == SCIP_STATUS_UNKNOWN )
4330 {
4331 SCIPverbMessage(set->scip, SCIP_VERBLEVEL_FULL, NULL, " Benders' decomposition: Error solving "
4332 "subproblem %d. No cut will be generated for this subproblem.\n", probnumber);
4333 SCIPbendersSetSubproblemObjval(benders, probnumber, SCIPsetInfinity(set));
4334 }
4335 else if( solvestatus == SCIP_STATUS_UNBOUNDED )
4336 {
4337 SCIPerrorMessage("The Benders' decomposition subproblem %d is unbounded. This should not happen.\n",
4338 probnumber);
4339 SCIPABORT();
4340 }
4341 else
4342 {
4343 SCIPerrorMessage("Invalid status returned from solving Benders' decomposition subproblem %d. Solution status: %d\n",
4344 probnumber, solvestatus);
4345 SCIPABORT();
4346 }
4347 }
4348 else
4349 {
4350 assert(solveloop == SCIP_BENDERSSOLVELOOP_USERCONVEX || solveloop == SCIP_BENDERSSOLVELOOP_USERCIP);
4351 if( result == SCIP_FEASIBLE )
4352 SCIPbendersSetSubproblemObjval(benders, probnumber, objective);
4353 else if( result == SCIP_INFEASIBLE )
4354 SCIPbendersSetSubproblemObjval(benders, probnumber, SCIPsetInfinity(set));
4355 else if( result == SCIP_UNBOUNDED )
4356 {
4357 SCIPerrorMessage("The Benders' decomposition subproblem %d is unbounded. This should not happen.\n",
4358 probnumber);
4359 SCIPABORT();
4360 }
4361 else if( result != SCIP_DIDNOTRUN )
4362 {
4363 SCIPerrorMessage("Invalid result <%d> from user-defined subproblem solving method. This should not happen.\n",
4364 result);
4365 }
4366 }
4367 }
4368
4369 return SCIP_OKAY;
4370}
4372/** sets up the subproblem using the solution to the master problem */
4374 SCIP_BENDERS* benders, /**< Benders' decomposition */
4375 SCIP_SET* set, /**< global SCIP settings */
4376 SCIP_SOL* sol, /**< primal CIP solution */
4377 int probnumber, /**< the subproblem number */
4378 SCIP_BENDERSENFOTYPE type /**< the enforcement type calling this function */
4379 )
4380{
4381 SCIP* subproblem;
4382 SCIP_VAR** vars;
4383 SCIP_VAR* mastervar;
4384 SCIP_Real solval;
4385 int nvars;
4386 int i;
4387
4388 assert(benders != NULL);
4389 assert(set != NULL);
4390 assert(probnumber >= 0 && probnumber < SCIPbendersGetNSubproblems(benders));
4391
4392 subproblem = SCIPbendersSubproblem(benders, probnumber);
4393
4394 /* the subproblem setup can only be performed if the subproblem is not NULL */
4395 if( subproblem == NULL )
4396 {
4397 SCIPerrorMessage("The subproblem %d is NULL. Thus, the subproblem setup must be performed manually in either "
4398 "bendersSolvesubconvex%s or bendersSolvesub%s.\n", probnumber, benders->name, benders->name);
4399 return SCIP_ERROR;
4400 }
4401 assert(subproblem != NULL);
4402
4403 /* changing all of the master problem variable to continuous. */
4404 SCIP_CALL( SCIPbendersChgMastervarsToCont(benders, set, probnumber) );
4405
4406 /* if the Benders' decomposition subproblem is convex and has continuous variables, then probing mode
4407 * must be started.
4408 * If the subproblem contains non-convex constraints or discrete variables, then the problem must be initialised,
4409 * and then put into SCIP_STAGE_SOLVING to be able to change the variable bounds. The probing mode is entered once
4410 * the variable bounds are set.
4411 * In the latter case, the transformed problem is freed after each subproblem solve round. */
4413 {
4414 SCIP_CALL( SCIPstartProbing(subproblem) );
4415 }
4416 else
4417 {
4418 SCIP_Bool infeasible;
4419 SCIP_Bool success;
4420
4421 SCIP_CALL( initialiseSubproblem(benders, set, probnumber, &infeasible, &success) );
4422 assert(success == !infeasible);
4423
4424 /* if the problem is identified as infeasible, this means that the underlying LP is infeasible. Since no variable
4425 * fixings have been applied at this stage, this means that the complete problem is infeasible. It is only
4426 * possible to set this parameter if we are at the root node or in an initialisation stage.
4427 */
4428 if( infeasible )
4430
4431 if( !success )
4432 {
4433 /* set the flag to indicate that the subproblems have been set up */
4434 SCIPbendersSetSubproblemIsSetup(benders, probnumber, FALSE);
4435
4436 return SCIP_OKAY;
4437 }
4438 }
4439
4440 vars = SCIPgetVars(subproblem);
4441 nvars = SCIPgetNVars(subproblem);
4442
4443 /* looping over all variables in the subproblem to find those corresponding to the master problem variables. */
4444 /* TODO: It should be possible to store the pointers to the master variables to speed up the subproblem setup */
4445 for( i = 0; i < nvars; i++ )
4446 {
4447 SCIP_CALL( SCIPbendersGetVar(benders, set, vars[i], &mastervar, -1) );
4448
4449 if( mastervar != NULL )
4450 {
4451 /* It is possible due to numerics that the solution value exceeds the upper or lower bounds. When this
4452 * happens, it causes an error in the LP solver as a result of inconsistent bounds. So the following statements
4453 * are used to ensure that the bounds are not exceeded when applying the fixings for the Benders'
4454 * decomposition subproblems
4455 */
4456 solval = SCIPgetSolVal(set->scip, sol, mastervar);
4457 if( !SCIPisLT(set->scip, solval, SCIPvarGetUbLocal(vars[i])) )
4458 solval = SCIPvarGetUbLocal(vars[i]);
4459 else if( !SCIPisGT(set->scip, solval, SCIPvarGetLbLocal(vars[i])) )
4460 solval = SCIPvarGetLbLocal(vars[i]);
4461
4462 /* fixing the variable in the subproblem */
4463 if( !SCIPisEQ(subproblem, SCIPvarGetLbLocal(vars[i]), SCIPvarGetUbLocal(vars[i])) )
4464 {
4465 if( SCIPisGT(subproblem, solval, SCIPvarGetLbLocal(vars[i])) )
4466 {
4467 SCIP_CALL( SCIPchgVarLb(subproblem, vars[i], solval) );
4468 }
4469 if( SCIPisLT(subproblem, solval, SCIPvarGetUbLocal(vars[i])) )
4470 {
4471 SCIP_CALL( SCIPchgVarUb(subproblem, vars[i], solval) );
4472 }
4473 }
4474
4475 assert(SCIPisEQ(subproblem, SCIPvarGetLbLocal(vars[i]), SCIPvarGetUbLocal(vars[i])));
4476 }
4477 else if( strstr(SCIPvarGetName(vars[i]), SLACKVAR_NAME) != NULL )
4478 {
4479 /* if the slack variables have been added to help improve feasibility, then they remain unfixed with a large
4480 * objective coefficient. Once the root node has been solved to optimality, then the slack variables are
4481 * fixed to zero.
4482 */
4483 if( benders->feasibilityphase && SCIPgetDepth(set->scip) == 0 && type != SCIP_BENDERSENFOTYPE_CHECK )
4484 {
4485 /* The coefficient update or variable fixing can only be performed if the subproblem is in probing mode.
4486 * If the slack var coef gets very large, then we fix the slack variable to 0 instead.
4487 */
4488 if( SCIPinProbing(subproblem) )
4489 {
4490 if( benders->slackvarcoef <= benders->maxslackvarcoef )
4491 {
4492 SCIP_CALL( SCIPchgVarObjProbing(subproblem, vars[i], benders->slackvarcoef) );
4493 }
4494 else
4495 {
4496 SCIP_CALL( SCIPchgVarUbProbing(subproblem, vars[i], 0.0) );
4497 }
4498 }
4499 }
4500 else
4501 {
4502 /* if the subproblem is non-linear and convex, then slack variables have been added to the subproblem. These
4503 * need to be fixed to zero when first solving the subproblem. However, if the slack variables have been added
4504 * by setting the execfeasphase runtime parameter, then they must not get fixed to zero
4505 */
4506 assert( !SCIPisEQ(subproblem, SCIPvarGetLbLocal(vars[i]), SCIPvarGetUbLocal(vars[i])) );
4507 assert( SCIPisZero(subproblem, SCIPvarGetLbLocal(vars[i])) );
4508
4509 if( SCIPisLT(subproblem, 0.0, SCIPvarGetUbLocal(vars[i])) )
4510 {
4511 SCIP_CALL( SCIPchgVarUb(subproblem, vars[i], 0.0) );
4512 }
4513 }
4514 }
4515 }
4516
4517 /* if the subproblem contain non-convex constraints or discrete variables, then the probing mode is entered after
4518 * setting up the subproblem
4519 */
4521 {
4522 SCIP_CALL( SCIPstartProbing(subproblem) );
4523 }
4524
4525 /* set the flag to indicate that the subproblems have been set up */
4526 SCIPbendersSetSubproblemIsSetup(benders, probnumber, TRUE);
4527
4528 return SCIP_OKAY;
4529}
4530
4531/** Solve a Benders' decomposition subproblems. This will either call the user defined method or the generic solving
4532 * methods. If the generic method is called, then the subproblem must be set up before calling this method. */
4534 SCIP_BENDERS* benders, /**< Benders' decomposition */
4535 SCIP_SET* set, /**< global SCIP settings */
4536 SCIP_SOL* sol, /**< primal CIP solution, can be NULL */
4537 int probnumber, /**< the subproblem number */
4538 SCIP_Bool* infeasible, /**< returns whether the current subproblem is infeasible */
4539 SCIP_Bool solvecip, /**< directly solve the CIP subproblem */
4540 SCIP_Real* objective /**< the objective function value of the subproblem, can be NULL */
4541 )
4542{
4543 assert(benders != NULL);
4544 assert(set != NULL);
4545 assert(probnumber >= 0 && probnumber < SCIPbendersGetNSubproblems(benders));
4546
4547 assert(infeasible != NULL);
4548 (*infeasible) = FALSE;
4549
4550 /* the subproblem must be set up before this function is called. */
4551 if( SCIPbendersSubproblem(benders, probnumber) != NULL && !SCIPbendersSubproblemIsSetup(benders, probnumber)
4552 && !SCIPbendersSubproblemIsIndependent(benders, probnumber) )
4553 {
4554 SCIPerrorMessage("Benders' decomposition subproblem %d must be set up before calling SCIPbendersSolveSubproblem(). Call SCIPsetupSubproblem() first.\n", probnumber);
4555 return SCIP_ERROR;
4556 }
4557
4558 /* if the subproblem solve callback is implemented, then that is used instead of the default setup */
4559 if( benders->benderssolvesubconvex != NULL || benders->benderssolvesub != NULL)
4560 {
4561 SCIP_BENDERSSOLVELOOP solveloop;
4562 SCIP_RESULT result;
4563 SCIP_Real subobj;
4564
4565 if( solvecip )
4567 else
4569
4570 SCIP_CALL( executeUserDefinedSolvesub(benders, set, sol, probnumber, solveloop, infeasible, &subobj, &result) );
4571
4572 if( objective != NULL )
4573 (*objective) = subobj;
4574 }
4575 else
4576 {
4577 SCIP* subproblem;
4578
4579 subproblem = SCIPbendersSubproblem(benders, probnumber);
4580 assert(subproblem != NULL);
4581
4582 /* solving the subproblem */
4583 if( solvecip && SCIPbendersGetSubproblemType(benders, probnumber) != SCIP_BENDERSSUBTYPE_CONVEXCONT )
4584 {
4585 SCIP_STATUS solvestatus;
4586
4587 SCIP_CALL( SCIPbendersSolveSubproblemCIP(set->scip, benders, probnumber, &solvestatus, solvecip) );
4588
4589 if( solvestatus == SCIP_STATUS_INFEASIBLE )
4590 (*infeasible) = TRUE;
4591 if( objective != NULL )
4592 (*objective) = SCIPgetSolOrigObj(subproblem, SCIPgetBestSol(subproblem))*(int)SCIPgetObjsense(subproblem);
4593 }
4594 else
4595 {
4596 SCIP_Bool success;
4597
4598 /* if the subproblem has convex constraints and continuous variables, then it should have been initialised and
4599 * in SCIP_STAGE_SOLVING. In this case, the subproblem only needs to be put into probing mode.
4600 */
4602 {
4603 /* if the subproblem is not in probing mode, then it must be put into that mode for the LP solve. */
4604 if( !SCIPinProbing(subproblem) )
4605 {
4606 SCIP_CALL( SCIPstartProbing(subproblem) );
4607 }
4608
4609 success = TRUE;
4610 }
4611 else
4612 {
4613 SCIP_CALL( initialiseSubproblem(benders, set, probnumber, infeasible, &success) );
4614 }
4615
4616 /* if setting up the subproblem was successful */
4617 if( success )
4618 {
4619 SCIP_STATUS solvestatus;
4620 SCIP_Real lpobjective;
4621
4622 SCIP_CALL( SCIPbendersSolveSubproblemLP(set->scip, benders, probnumber, &solvestatus, &lpobjective) );
4623
4624 if( solvestatus == SCIP_STATUS_INFEASIBLE )
4625 (*infeasible) = TRUE;
4626 else if( objective != NULL )
4627 (*objective) = lpobjective;
4628 }
4629 else
4630 {
4631 if( objective != NULL )
4632 (*objective) = SCIPinfinity(subproblem);
4633 }
4634 }
4635 }
4636
4637 return SCIP_OKAY;
4638}
4639
4640/** copies the time and memory limit from the master problem to the subproblem */
4641static
4643 SCIP* scip, /**< the SCIP data structure */
4644 SCIP* subproblem /**< the Benders' decomposition subproblem */
4645 )
4646{
4647 SCIP_Real mastertimelimit;
4648 SCIP_Real subtimelimit;
4649 SCIP_Real maxsubtimelimit;
4650 SCIP_Real mastermemorylimit;
4651 SCIP_Real submemorylimit;
4652 SCIP_Real maxsubmemorylimit;
4653
4654 assert(scip != NULL);
4655
4656 /* setting the time limit for the Benders' decomposition subproblems. It is set to 102% of the remaining time. */
4657 SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &mastertimelimit) );
4658 maxsubtimelimit = SCIPparamGetRealMax(SCIPgetParam(subproblem, "limits/time"));
4659 subtimelimit = (mastertimelimit - SCIPgetSolvingTime(scip)) * 1.02;
4660 subtimelimit = MIN(subtimelimit, maxsubtimelimit);
4661 SCIP_CALL( SCIPsetRealParam(subproblem, "limits/time", MAX(0.0, subtimelimit)) );
4662
4663 /* setting the memory limit for the Benders' decomposition subproblems. */
4664 SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &mastermemorylimit) );
4665 maxsubmemorylimit = SCIPparamGetRealMax(SCIPgetParam(subproblem, "limits/memory"));
4666 submemorylimit = mastermemorylimit - (SCIPgetMemUsed(scip) + SCIPgetMemExternEstim(scip))/1048576.0;
4667 submemorylimit = MIN(submemorylimit, maxsubmemorylimit);
4668 SCIP_CALL( SCIPsetRealParam(subproblem, "limits/memory", MAX(0.0, submemorylimit)) );
4669
4670 return SCIP_OKAY;
4671}
4672
4673/** stores the original parameters from the subproblem */
4674static
4676 SCIP* subproblem, /**< the SCIP data structure */
4677 SCIP_SUBPROBPARAMS* origparams /**< the original subproblem parameters */
4678 )
4679{
4680 assert(subproblem != NULL);
4681 assert(origparams != NULL);
4682
4683 SCIP_CALL( SCIPgetRealParam(subproblem, "limits/memory", &origparams->limits_memory) );
4684 SCIP_CALL( SCIPgetRealParam(subproblem, "limits/time", &origparams->limits_time) );
4685 SCIP_CALL( SCIPgetBoolParam(subproblem, "conflict/enable", &origparams->conflict_enable) );
4686 SCIP_CALL( SCIPgetIntParam(subproblem, "lp/disablecutoff", &origparams->lp_disablecutoff) );
4687 SCIP_CALL( SCIPgetIntParam(subproblem, "lp/scaling", &origparams->lp_scaling) );
4688 SCIP_CALL( SCIPgetCharParam(subproblem, "lp/initalgorithm", &origparams->lp_initalg) );
4689 SCIP_CALL( SCIPgetCharParam(subproblem, "lp/resolvealgorithm", &origparams->lp_resolvealg) );
4690 SCIP_CALL( SCIPgetBoolParam(subproblem, "lp/alwaysgetduals", &origparams->lp_alwaysgetduals) );
4691 SCIP_CALL( SCIPgetBoolParam(subproblem, "misc/scaleobj", &origparams->misc_scaleobj) );
4692 SCIP_CALL( SCIPgetBoolParam(subproblem, "misc/catchctrlc", &origparams->misc_catchctrlc) );
4693 SCIP_CALL( SCIPgetIntParam(subproblem, "propagating/maxrounds", &origparams->prop_maxrounds) );
4694 SCIP_CALL( SCIPgetIntParam(subproblem, "propagating/maxroundsroot", &origparams->prop_maxroundsroot) );
4695 SCIP_CALL( SCIPgetIntParam(subproblem, "constraints/linear/propfreq", &origparams->cons_linear_propfreq) );
4696
4697 return SCIP_OKAY;
4698}
4699
4700/** sets the parameters for the subproblem */
4701static
4703 SCIP* scip, /**< the SCIP data structure */
4704 SCIP* subproblem /**< the subproblem SCIP instance */
4705 )
4706{
4707 assert(scip != NULL);
4708 assert(subproblem != NULL);
4709
4710 /* copying memory and time limits */
4711 SCIP_CALL( copyMemoryAndTimeLimits(scip, subproblem) );
4712
4713 /* Do we have to disable presolving? If yes, we have to store all presolving parameters. */
4715
4716 /* Disabling heuristics so that the problem is not trivially solved */
4718
4719 /* store parameters that are changed for the generation of the subproblem cuts */
4720 SCIP_CALL( SCIPsetBoolParam(subproblem, "conflict/enable", FALSE) );
4721
4722 SCIP_CALL( SCIPsetIntParam(subproblem, "lp/disablecutoff", 1) );
4723 SCIP_CALL( SCIPsetIntParam(subproblem, "lp/scaling", 0) );
4724
4725 SCIP_CALL( SCIPsetCharParam(subproblem, "lp/initalgorithm", 'd') );
4726 SCIP_CALL( SCIPsetCharParam(subproblem, "lp/resolvealgorithm", 'd') );
4727
4728 SCIP_CALL( SCIPsetBoolParam(subproblem, "lp/alwaysgetduals", TRUE) );
4729 SCIP_CALL( SCIPsetBoolParam(subproblem, "misc/scaleobj", FALSE) );
4730
4731 /* do not abort subproblem on CTRL-C */
4732 SCIP_CALL( SCIPsetBoolParam(subproblem, "misc/catchctrlc", FALSE) );
4733
4734#ifndef SCIP_MOREDEBUG
4735 SCIP_CALL( SCIPsetIntParam(subproblem, "display/verblevel", (int)SCIP_VERBLEVEL_NONE) );
4736#endif
4737
4738 SCIP_CALL( SCIPsetIntParam(subproblem, "propagating/maxrounds", 0) );
4739 SCIP_CALL( SCIPsetIntParam(subproblem, "propagating/maxroundsroot", 0) );
4740
4741 SCIP_CALL( SCIPsetIntParam(subproblem, "constraints/linear/propfreq", -1) );
4742
4743 SCIP_CALL( SCIPsetIntParam(subproblem, "heuristics/alns/freq", -1) );
4744
4745 SCIP_CALL( SCIPsetIntParam(subproblem, "separating/aggregation/freq", -1) );
4746 SCIP_CALL( SCIPsetIntParam(subproblem, "separating/gomory/freq", -1) );
4747
4748 return SCIP_OKAY;
4749}
4750
4751/** resets the original parameters from the subproblem */
4752static
4754 SCIP* subproblem, /**< the SCIP data structure */
4755 SCIP_SUBPROBPARAMS* origparams /**< the original subproblem parameters */
4756 )
4757{
4758 assert(subproblem != NULL);
4759 assert(origparams != NULL);
4760
4761 SCIP_CALL( SCIPsetRealParam(subproblem, "limits/memory", origparams->limits_memory) );
4762 SCIP_CALL( SCIPsetRealParam(subproblem, "limits/time", origparams->limits_time) );
4763 SCIP_CALL( SCIPsetBoolParam(subproblem, "conflict/enable", origparams->conflict_enable) );
4764 SCIP_CALL( SCIPsetIntParam(subproblem, "lp/disablecutoff", origparams->lp_disablecutoff) );
4765 SCIP_CALL( SCIPsetIntParam(subproblem, "lp/scaling", origparams->lp_scaling) );
4766 SCIP_CALL( SCIPsetCharParam(subproblem, "lp/initalgorithm", origparams->lp_initalg) );
4767 SCIP_CALL( SCIPsetCharParam(subproblem, "lp/resolvealgorithm", origparams->lp_resolvealg) );
4768 SCIP_CALL( SCIPsetBoolParam(subproblem, "lp/alwaysgetduals", origparams->lp_alwaysgetduals) );
4769 SCIP_CALL( SCIPsetBoolParam(subproblem, "misc/scaleobj", origparams->misc_scaleobj) );
4770 SCIP_CALL( SCIPsetBoolParam(subproblem, "misc/catchctrlc", origparams->misc_catchctrlc) );
4771 SCIP_CALL( SCIPsetIntParam(subproblem, "propagating/maxrounds", origparams->prop_maxrounds) );
4772 SCIP_CALL( SCIPsetIntParam(subproblem, "propagating/maxroundsroot", origparams->prop_maxroundsroot) );
4773 SCIP_CALL( SCIPsetIntParam(subproblem, "constraints/linear/propfreq", origparams->cons_linear_propfreq) );
4774
4775 return SCIP_OKAY;
4776}
4778/** returns NLP solver parameters used for solving NLP subproblems */
4780 SCIP_BENDERS* benders /**< Benders' decomposition */
4781 )
4782{
4783 assert(benders != NULL);
4784
4785 return benders->nlpparam;
4786}
4787
4788/** solves the LP of the Benders' decomposition subproblem
4789 *
4790 * This requires that the subproblem is in probing mode.
4791 */
4793 SCIP* scip, /**< the SCIP data structure */
4794 SCIP_BENDERS* benders, /**< the Benders' decomposition data structure */
4795 int probnumber, /**< the subproblem number */
4796 SCIP_STATUS* solvestatus, /**< status of subproblem solve */
4797 SCIP_Real* objective /**< optimal value of subproblem, if solved to optimality */
4798 )
4799{
4800 SCIP* subproblem;
4801 SCIP_SUBPROBPARAMS* origparams;
4802 SCIP_Bool solvenlp;
4803
4804 assert(benders != NULL);
4805 assert(solvestatus != NULL);
4806 assert(objective != NULL);
4807 assert(SCIPbendersSubproblemIsSetup(benders, probnumber));
4808
4809 /* TODO: This should be solved just as an LP, so as a MIP. There is too much overhead with the MIP.
4810 * Need to change status check for checking the LP. */
4811 subproblem = SCIPbendersSubproblem(benders, probnumber);
4812 assert(subproblem != NULL);
4813
4814 /* only solve the NLP relaxation if the NLP has been constructed and there exists an NLPI. If it is not possible to
4815 * solve the NLP relaxation, then the LP relaxation is used to generate Benders' cuts
4816 */
4817 solvenlp = FALSE;
4818 if( SCIPisNLPConstructed(subproblem) && SCIPgetNNlpis(subproblem) > 0
4820 solvenlp = TRUE;
4821
4822 *objective = SCIPinfinity(subproblem);
4823
4824 assert(SCIPisNLPConstructed(subproblem) || SCIPisLPConstructed(subproblem));
4825 assert(SCIPinProbing(subproblem));
4826
4827 /* allocating memory for the parameter storage */
4828 SCIP_CALL( SCIPallocBlockMemory(subproblem, &origparams) );
4829
4830 /* store the original parameters of the subproblem */
4831 SCIP_CALL( storeOrigSubproblemParams(subproblem, origparams) );
4832
4833 /* setting the subproblem parameters */
4834 SCIP_CALL( setSubproblemParams(scip, subproblem) );
4835
4836 if( solvenlp )
4837 {
4838 SCIP_NLPSOLSTAT nlpsolstat;
4839 SCIP_NLPTERMSTAT nlptermstat;
4840#ifdef SCIP_MOREDEBUG
4841 SCIP_SOL* nlpsol;
4842#endif
4843
4844 SCIP_CALL( SCIPsolveNLPParam(subproblem, benders->nlpparam) );
4845
4846 nlpsolstat = SCIPgetNLPSolstat(subproblem);
4847 nlptermstat = SCIPgetNLPTermstat(subproblem);
4848 SCIPdebugMsg(scip, "NLP solstat %d termstat %d\n", nlpsolstat, nlptermstat);
4849
4850 if( nlptermstat == SCIP_NLPTERMSTAT_OKAY && (nlpsolstat == SCIP_NLPSOLSTAT_LOCINFEASIBLE || nlpsolstat == SCIP_NLPSOLSTAT_GLOBINFEASIBLE) )
4851 {
4852 /* trust infeasible only if terminated "okay" */
4853 (*solvestatus) = SCIP_STATUS_INFEASIBLE;
4854 }
4855 else if( nlpsolstat == SCIP_NLPSOLSTAT_LOCOPT || nlpsolstat == SCIP_NLPSOLSTAT_GLOBOPT
4856 || nlpsolstat == SCIP_NLPSOLSTAT_FEASIBLE )
4857 {
4858#ifdef SCIP_MOREDEBUG
4859 SCIP_CALL( SCIPcreateNLPSol(subproblem, &nlpsol, NULL) );
4860 SCIP_CALL( SCIPprintSol(subproblem, nlpsol, NULL, FALSE) );
4861 SCIP_CALL( SCIPfreeSol(subproblem, &nlpsol) );
4862#endif
4863
4864 (*solvestatus) = SCIP_STATUS_OPTIMAL;
4865 (*objective) = SCIPretransformObj(subproblem, SCIPgetNLPObjval(subproblem));
4866 }
4867 else if( nlpsolstat == SCIP_NLPSOLSTAT_UNBOUNDED )
4868 {
4869 (*solvestatus) = SCIP_STATUS_UNBOUNDED;
4870 SCIPerrorMessage("The NLP of Benders' decomposition subproblem %d is unbounded. This should not happen.\n",
4871 probnumber);
4872 SCIPABORT();
4873 }
4874 else if( nlptermstat == SCIP_NLPTERMSTAT_TIMELIMIT )
4875 {
4876 (*solvestatus) = SCIP_STATUS_TIMELIMIT;
4877 }
4878 else if( nlptermstat == SCIP_NLPTERMSTAT_ITERLIMIT)
4879 {
4880 /* this is an approximation in lack of a better fitting SCIP_STATUS */
4881 SCIPwarningMessage(scip, "The NLP solver stopped due to an iteration limit for Benders' decomposition subproblem %d. Consider increasing benders/%s/nlpiterlimit.\n", probnumber,