SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
benderscut_opt.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-2023 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 benderscut_opt.c
26 * @ingroup OTHER_CFILES
27 * @brief Generates a standard Benders' decomposition optimality cut
28 * @author Stephen J. Maher
29 */
30
31/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32
33#include "scip/pub_expr.h"
34#include "scip/benderscut_opt.h"
35#include "scip/cons_linear.h"
36#include "scip/pub_benderscut.h"
37#include "scip/pub_benders.h"
38#include "scip/pub_lp.h"
39#include "scip/pub_nlp.h"
40#include "scip/pub_message.h"
41#include "scip/pub_misc.h"
43#include "scip/pub_var.h"
44#include "scip/scip.h"
45#include <string.h>
46
47#define BENDERSCUT_NAME "optimality"
48#define BENDERSCUT_DESC "Standard Benders' decomposition optimality cut"
49#define BENDERSCUT_PRIORITY 5000
50#define BENDERSCUT_LPCUT TRUE
51
52#define SCIP_DEFAULT_ADDCUTS FALSE /** Should cuts be generated, instead of constraints */
53#define SCIP_DEFAULT_CALCMIR TRUE /** Should the mixed integer rounding procedure be used for the cut */
54
55/*
56 * Data structures
57 */
58
59/** Benders' decomposition cuts data */
60struct SCIP_BenderscutData
61{
62 SCIP_Bool addcuts; /**< should cuts be generated instead of constraints */
63 SCIP_Bool calcmir; /**< should the mixed integer rounding procedure be applied to cuts */
64};
65
66
67/*
68 * Local methods
69 */
70
71/** in the case of numerical troubles, the LP is resolved with solution polishing activated */
72static
74 SCIP* subproblem, /**< the SCIP data structure */
75 SCIP_Bool* success /**< TRUE is the resolving of the LP was successful */
76 )
77{
78 int oldpolishing;
79 SCIP_Bool lperror;
80 SCIP_Bool cutoff;
81
84
85 (*success) = FALSE;
86
87 /* setting the solution polishing parameter */
88 SCIP_CALL( SCIPgetIntParam(subproblem, "lp/solutionpolishing", &oldpolishing) );
89 SCIP_CALL( SCIPsetIntParam(subproblem, "lp/solutionpolishing", 2) );
90
91 /* resolving the probing LP */
93
95 (*success) = TRUE;
96
97 /* resetting the solution polishing parameter */
98 SCIP_CALL( SCIPsetIntParam(subproblem, "lp/solutionpolishing", oldpolishing) );
99
100 return SCIP_OKAY;
101}
102
103/** verifying the activity of the cut when master variables are within epsilon of their upper or lower bounds
104 *
105 * When setting up the Benders' decomposition subproblem, master variables taking values that are within epsilon
106 * greater than their upper bound or less than their lower bound are set to their upper and lower bounds respectively.
107 * As such, there can be a difference between the subproblem dual solution objective and the optimality cut activity,
108 * when computed using the master problem solution directly. This check is to verify whether this difference is an
109 * actual error or due to the violation of the upper and lower bounds when setting up the Benders' decomposition
110 * subproblem.
111 */
112static
114 SCIP* masterprob, /**< the SCIP data structure */
115 SCIP_SOL* sol, /**< the master problem solution */
116 SCIP_VAR** vars, /**< pointer to array of variables in the generated cut with non-zero coefficient */
117 SCIP_Real* vals, /**< pointer to array of coefficients of the variables in the generated cut */
118 SCIP_Real lhs, /**< the left hand side of the cut */
119 SCIP_Real checkobj, /**< the objective of the subproblem computed from the dual solution */
120 int nvars, /**< the number of variables in the cut */
121 SCIP_Bool* valid /**< returns true is the cut is valid */
122 )
123{
124 SCIP_Real verifyobj;
125 int i;
126
128 assert(vars != NULL);
129 assert(vals != NULL);
130
131 /* initialising the verify objective with the left hand side of the optimality cut */
132 verifyobj = lhs;
133
134 /* computing the activity of the cut from the master solution and the constraint values */
135 for( i = 0; i < nvars; i++ )
136 {
137 SCIP_Real solval;
138
139 solval = SCIPgetSolVal(masterprob, sol, vars[i]);
140
141 /* checking whether the solution value is less than or greater than the variable bounds */
142 if( !SCIPisLT(masterprob, solval, SCIPvarGetUbLocal(vars[i])) )
143 solval = SCIPvarGetUbLocal(vars[i]);
144 else if( !SCIPisGT(masterprob, solval, SCIPvarGetLbLocal(vars[i])) )
145 solval = SCIPvarGetLbLocal(vars[i]);
146
147 verifyobj -= solval*vals[i];
148 }
149
150 (*valid) = SCIPisFeasEQ(masterprob, checkobj, verifyobj);
151
152 return SCIP_OKAY;
153}
154
155/** when solving NLP subproblems, numerical issues are addressed by tightening the feasibility tolerance */
156static
158 SCIP* subproblem, /**< the SCIP data structure */
159 SCIP_Real multiplier, /**< the amount by which to decrease the tolerance */
160 SCIP_Bool* success /**< TRUE is the resolving of the LP was successful */
161 )
162{
164#ifdef SCIP_DEBUG
166#endif
168#ifdef SCIP_MOREDEBUG
169 SCIP_SOL* nlpsol;
170#endif
171
174
175 (*success) = FALSE;
176
177 /* reduce the default feasibility and optimality tolerance by given factor (typically 0.01) */
178 nlpparam.feastol *= multiplier;
179 nlpparam.opttol *= multiplier;
180
182
184#ifdef SCIP_DEBUG
186 SCIPdebugMsg(subproblem, "NLP solstat %d termstat %d\n", nlpsolstat, nlptermstat);
187#endif
188
191 {
192#ifdef SCIP_MOREDEBUG
195 SCIP_CALL( SCIPfreeSol(subproblem, &nlpsol) );
196#endif
197
198 (*success) = TRUE;
199 }
200
201 return SCIP_OKAY;
202}
203
204/** adds a variable and value to the constraint/row arrays */
205static
207 SCIP* masterprob, /**< the SCIP instance of the master problem */
208 SCIP_VAR*** vars, /**< pointer to the array of variables in the generated cut with non-zero coefficient */
209 SCIP_Real** vals, /**< pointer to the array of coefficients of the variables in the generated cut */
210 SCIP_VAR* addvar, /**< the variable that will be added to the array */
211 SCIP_Real addval, /**< the value that will be added to the array */
212 int* nvars, /**< the number of variables in the variable array */
213 int* varssize /**< the length of the variable size */
214 )
215{
217 assert(vars != NULL);
218 assert(*vars != NULL);
219 assert(vals != NULL);
220 assert(*vals != NULL);
221 assert(addvar != NULL);
222 assert(nvars != NULL);
223 assert(varssize != NULL);
224
225 if( *nvars >= *varssize )
226 {
227 *varssize = SCIPcalcMemGrowSize(masterprob, *varssize + 1);
229 SCIP_CALL( SCIPreallocBufferArray(masterprob, vals, *varssize) );
230 }
231 assert(*nvars < *varssize);
232
233 (*vars)[*nvars] = addvar;
234 (*vals)[*nvars] = addval;
235 (*nvars)++;
236
237 return SCIP_OKAY;
238}
239
240/** returns the variable solution either from the NLP or from the primal vals array */
241static
242SCIP_Real getNlpVarSol(
243 SCIP_VAR* var, /**< the variable for which the solution is requested */
244 SCIP_Real* primalvals, /**< the primal solutions for the NLP, can be NULL */
245 SCIP_HASHMAP* var2idx /**< mapping from variable of the subproblem to the index in the dual arrays, can be NULL */
246 )
247{
248 SCIP_Real varsol;
249 int idx;
250
251 assert(var != NULL);
252 assert((primalvals == NULL && var2idx == NULL) || (primalvals != NULL && var2idx != NULL));
253
254 if( var2idx != NULL && primalvals != NULL )
255 {
256 assert(SCIPhashmapExists(var2idx, (void*)var) );
257 idx = SCIPhashmapGetImageInt(var2idx, (void*)var);
258 varsol = primalvals[idx];
259 }
260 else
262
263 return varsol;
264}
265
266/** calculates a MIR cut from the coefficients of the standard optimality cut */
267static
269 SCIP* masterprob, /**< the SCIP instance of the master problem */
270 SCIP_SOL* sol, /**< primal CIP solution */
271 SCIP_VAR** vars, /**< pointer to array of variables in the generated cut with non-zero coefficient */
272 SCIP_Real* vals, /**< pointer to array of coefficients of the variables in the generated cut */
273 SCIP_Real lhs, /**< the left hand side of the cut */
274 SCIP_Real rhs, /**< the right hand side of the cut */
275 int nvars, /**< the number of variables in the cut */
276 SCIP_Real* cutcoefs, /**< the coefficients of the MIR cut */
277 int* cutinds, /**< the variable indices of the MIR cut */
278 SCIP_Real* cutrhs, /**< the RHS of the MIR cut */
279 int* cutnnz, /**< the number of non-zeros in the cut */
280 SCIP_Bool* success /**< was the MIR cut successfully computed? */
281 )
282{
283 SCIP_AGGRROW* aggrrow;
284 SCIP_Real* rowvals;
285 int* rowinds;
286
287 SCIP_Real cutefficacy;
288 int cutrank;
289 SCIP_Bool cutislocal;
290
291 SCIP_Bool cutsuccess;
292
293 int i;
294
295 /* creating the aggregation row. There will be only a single row in this aggregation, since it is only used to
296 * compute the MIR coefficients
297 */
299
300 /* retrieving the indices for the variables in the optimality cut. All of the values must be negated, since the
301 * aggregation row requires a RHS, where the optimality cut is computed with an LHS
302 */
305
308 for( i = 0; i < nvars; i++ )
309 {
310 rowinds[i] = SCIPvarGetProbindex(vars[i]);
311 rowvals[i] = -vals[i];
312 }
313
314 /* adding the optimality cut to the aggregation row */
315 SCIP_CALL( SCIPaggrRowAddCustomCons(masterprob, aggrrow, rowinds, rowvals, nvars, -lhs, 1.0, 1, FALSE) );
316
317 /* calculating a flow cover for the optimality cut */
320 (*success) = cutsuccess;
321
322 /* calculating the MIR coefficients for the optimality cut */
323 SCIP_CALL( SCIPcalcMIR(masterprob, sol, TRUE, 0.9999, TRUE, FALSE, FALSE, NULL, NULL, 0.001, 0.999, 1.0, aggrrow,
325 (*success) = ((*success) || cutsuccess);
326
327 /* the cut is only successful if the efficacy is high enough */
328 (*success) = (*success) && SCIPisEfficacious(masterprob, cutefficacy);
329
330 /* try to tighten the coefficients of the cut */
331 if( (*success) )
332 {
333 SCIP_Bool redundant;
334 int nchgcoefs;
335
337
338 (*success) = !redundant;
339 }
340
341 /* freeing the local memory */
344 SCIPaggrRowFree(masterprob, &aggrrow);
345
346 return SCIP_OKAY;
347}
348
349/** computes a standard Benders' optimality cut from the dual solutions of the LP */
350static
352 SCIP* masterprob, /**< the SCIP instance of the master problem */
353 SCIP* subproblem, /**< the SCIP instance of the subproblem */
354 SCIP_BENDERS* benders, /**< the benders' decomposition structure */
355 SCIP_VAR*** vars, /**< pointer to array of variables in the generated cut with non-zero coefficient */
356 SCIP_Real** vals, /**< pointer to array of coefficients of the variables in the generated cut */
357 SCIP_Real* lhs, /**< the left hand side of the cut */
358 SCIP_Real* rhs, /**< the right hand side of the cut */
359 int* nvars, /**< the number of variables in the cut */
360 int* varssize, /**< the number of variables in the array */
361 SCIP_Real* checkobj, /**< stores the objective function computed from the dual solution */
362 SCIP_Bool* success /**< was the cut generation successful? */
363 )
364{
365 SCIP_VAR** subvars;
366 SCIP_VAR** fixedvars;
367 int nsubvars;
368 int nfixedvars;
369 SCIP_Real dualsol;
370 SCIP_Real addval;
371 int nrows;
372 int i;
373
374 (*checkobj) = 0;
375
378 assert(benders != NULL);
379 assert(vars != NULL);
380 assert(*vars != NULL);
381 assert(vals != NULL);
382 assert(*vals != NULL);
383
384 (*success) = FALSE;
385
386 /* looping over all LP rows and setting the coefficients of the cut */
387 nrows = SCIPgetNLPRows(subproblem);
388 for( i = 0; i < nrows; i++ )
389 {
391
393 assert(lprow != NULL);
394
395 dualsol = SCIProwGetDualsol(lprow);
396 assert( !SCIPisInfinity(subproblem, dualsol) && !SCIPisInfinity(subproblem, -dualsol) );
397
398 if( SCIPisZero(subproblem, dualsol) )
399 continue;
400
401 if( dualsol > 0.0 )
402 addval = dualsol*SCIProwGetLhs(lprow);
403 else
404 addval = dualsol*SCIProwGetRhs(lprow);
405
406 (*lhs) += addval;
407
408 /* if the bound becomes infinite, then the cut generation terminates. */
409 if( SCIPisInfinity(masterprob, (*lhs)) || SCIPisInfinity(masterprob, -(*lhs))
411 {
412 (*success) = FALSE;
413 SCIPdebugMsg(masterprob, "Infinite bound when generating optimality cut. lhs = %g addval = %g.\n", (*lhs), addval);
414 return SCIP_OKAY;
415 }
416 }
417
418 nsubvars = SCIPgetNVars(subproblem);
419 subvars = SCIPgetVars(subproblem);
420 nfixedvars = SCIPgetNFixedVars(subproblem);
421 fixedvars = SCIPgetFixedVars(subproblem);
422
423 /* looping over all variables to update the coefficients in the computed cut. */
424 for( i = 0; i < nsubvars + nfixedvars; i++ )
425 {
426 SCIP_VAR* var;
428 SCIP_Real redcost;
429
430 if( i < nsubvars )
431 var = subvars[i];
432 else
433 var = fixedvars[i - nsubvars];
434
435 /* retrieving the master problem variable for the given subproblem variable. */
437
438 redcost = SCIPgetVarRedcost(subproblem, var);
439
441
442 /* checking whether the subproblem variable has a corresponding master variable. */
443 if( mastervar != NULL )
444 {
445 SCIP_Real coef;
446
447 coef = -1.0*(SCIPvarGetObj(var) + redcost);
448
449 if( !SCIPisZero(masterprob, coef) )
450 {
451 /* adding the variable to the storage */
452 SCIP_CALL( addVariableToArray(masterprob, vars, vals, mastervar, coef, nvars, varssize) );
453 }
454 }
455 else
456 {
457 if( !SCIPisZero(subproblem, redcost) )
458 {
459 addval = 0;
460
461 if( SCIPisPositive(subproblem, redcost) )
462 addval = redcost*SCIPvarGetLbLocal(var);
463 else if( SCIPisNegative(subproblem, redcost) )
464 addval = redcost*SCIPvarGetUbLocal(var);
465
466 (*lhs) += addval;
467
468 /* if the bound becomes infinite, then the cut generation terminates. */
469 if( SCIPisInfinity(masterprob, (*lhs)) || SCIPisInfinity(masterprob, -(*lhs))
471 {
472 (*success) = FALSE;
473 SCIPdebugMsg(masterprob, "Infinite bound when generating optimality cut.\n");
474 return SCIP_OKAY;
475 }
476 }
477 }
478 }
479
481 /* the rhs should be infinite. If it changes, then there is an error */
482 if( !SCIPisInfinity(masterprob, (*rhs)) )
483 {
484 (*success) = FALSE;
485 SCIPdebugMsg(masterprob, "RHS is not infinite. rhs = %g.\n", (*rhs));
486 return SCIP_OKAY;
487 }
488
489 (*success) = TRUE;
490
491 return SCIP_OKAY;
492}
493
494/** computes a standard Benders' optimality cut from the dual solutions of the NLP */
495static
497 SCIP* masterprob, /**< the SCIP instance of the master problem */
498 SCIP* subproblem, /**< the SCIP instance of the subproblem */
499 SCIP_BENDERS* benders, /**< the benders' decomposition structure */
500 SCIP_VAR*** vars, /**< pointer to array of variables in the generated cut with non-zero coefficient */
501 SCIP_Real** vals, /**< pointer to array of coefficients of the variables in the generated cut */
502 SCIP_Real* lhs, /**< the left hand side of the cut */
503 SCIP_Real* rhs, /**< the right hand side of the cut */
504 int* nvars, /**< the number of variables in the cut */
505 int* varssize, /**< the number of variables in the array */
506 SCIP_Real objective, /**< the objective function of the subproblem */
507 SCIP_Real* primalvals, /**< the primal solutions for the NLP, can be NULL */
508 SCIP_Real* consdualvals, /**< dual variables for the constraints, can be NULL */
509 SCIP_Real* varlbdualvals, /**< the dual variables for the variable lower bounds, can be NULL */
510 SCIP_Real* varubdualvals, /**< the dual variables for the variable upper bounds, can be NULL */
511 SCIP_HASHMAP* row2idx, /**< mapping between the row in the subproblem to the index in the dual array, can be NULL */
512 SCIP_HASHMAP* var2idx, /**< mapping from variable of the subproblem to the index in the dual arrays, can be NULL */
513 SCIP_Real* checkobj, /**< stores the objective function computed from the dual solution */
514 SCIP_Bool* success /**< was the cut generation successful? */
515 )
516{
517 SCIP_VAR** subvars;
518 SCIP_VAR** fixedvars;
519 int nsubvars;
520 int nfixedvars;
521 SCIP_Real dirderiv;
522 SCIP_Real dualsol;
523 int nrows;
524 int idx;
525 int i;
526
527 (*checkobj) = 0;
528
531 assert(benders != NULL);
535
536 (*success) = FALSE;
537
538 if( !(primalvals == NULL && consdualvals == NULL && varlbdualvals == NULL && varubdualvals == NULL && row2idx == NULL && var2idx == NULL)
539 && !(primalvals != NULL && consdualvals != NULL && varlbdualvals != NULL && varubdualvals != NULL && row2idx != NULL && var2idx != NULL) ) /*lint !e845*/
540 {
541 SCIPerrorMessage("The optimality cut must generated from either a SCIP instance or all of the dual solutions and indices must be supplied");
542 (*success) = FALSE;
543
544 return SCIP_ERROR;
545 }
546
547 nsubvars = SCIPgetNNLPVars(subproblem);
548 subvars = SCIPgetNLPVars(subproblem);
549 nfixedvars = SCIPgetNFixedVars(subproblem);
550 fixedvars = SCIPgetFixedVars(subproblem);
551
552 /* our optimality cut implementation assumes that SCIP did not modify the objective function and sense,
553 * that is, that the objective function value of the NLP corresponds to the value of the auxiliary variable
554 * if that wouldn't be the case, then the scaling and offset may have to be considered when adding the
555 * auxiliary variable to the cut (cons/row)?
556 */
560
561 (*lhs) = objective;
563
564 (*rhs) = SCIPinfinity(masterprob);
565
566 dirderiv = 0.0;
567
568 /* looping over all NLP rows and setting the corresponding coefficients of the cut */
570 for( i = 0; i < nrows; i++ )
571 {
572 SCIP_NLROW* nlrow;
573
574 nlrow = SCIPgetNLPNlRows(subproblem)[i];
575 assert(nlrow != NULL);
576
577 if( row2idx != NULL && consdualvals != NULL )
578 {
579 assert(SCIPhashmapExists(row2idx, (void*)nlrow) );
580 idx = SCIPhashmapGetImageInt(row2idx, (void*)nlrow);
581 dualsol = consdualvals[idx];
582 }
583 else
584 dualsol = SCIPnlrowGetDualsol(nlrow);
585 assert( !SCIPisInfinity(subproblem, dualsol) && !SCIPisInfinity(subproblem, -dualsol) );
586
587 if( SCIPisZero(subproblem, dualsol) )
588 continue;
589
591 -dualsol, primalvals, var2idx, &dirderiv, vars, vals, nvars, varssize) );
592 }
593
594 /* looping over sub- and fixed variables to compute checkobj */
595 for( i = 0; i < nsubvars; i++ )
596 (*checkobj) += SCIPvarGetObj(subvars[i]) * getNlpVarSol(subvars[i], primalvals, var2idx);
597
598 for( i = 0; i < nfixedvars; i++ )
599 *checkobj += SCIPvarGetUnchangedObj(fixedvars[i]) * getNlpVarSol(fixedvars[i], primalvals, var2idx);
600
601 *lhs += dirderiv;
602
603 /* if the side became infinite or dirderiv was infinite, then the cut generation terminates. */
606 {
607 (*success) = FALSE;
608 SCIPdebugMsg(masterprob, "Infinite bound when generating optimality cut. lhs = %g dirderiv = %g.\n", *lhs, dirderiv);
609 return SCIP_OKAY;
610 }
611
612 (*success) = TRUE;
613
614 return SCIP_OKAY;
615}
616
617
618/** Adds the auxiliary variable to the generated cut. If this is the first optimality cut for the subproblem, then the
619 * auxiliary variable is first created and added to the master problem.
620 */
621static
623 SCIP* masterprob, /**< the SCIP instance of the master problem */
624 SCIP_BENDERS* benders, /**< the benders' decomposition structure */
625 SCIP_VAR** vars, /**< the variables in the generated cut with non-zero coefficient */
626 SCIP_Real* vals, /**< the coefficients of the variables in the generated cut */
627 int* nvars, /**< the number of variables in the cut */
628 int probnumber /**< the number of the pricing problem */
629 )
630{
632
634 assert(benders != NULL);
635 assert(vars != NULL);
636 assert(vals != NULL);
637
639
640 vars[(*nvars)] = auxiliaryvar;
641 vals[(*nvars)] = 1.0;
642 (*nvars)++;
643
644 return SCIP_OKAY;
645}
646
647
648/*
649 * Callback methods of Benders' decomposition cuts
650 */
651
652/** destructor of Benders' decomposition cuts to free user data (called when SCIP is exiting) */
653static
655{ /*lint --e{715}*/
656 SCIP_BENDERSCUTDATA* benderscutdata;
657
658 assert( benderscut != NULL );
660
661 /* free Benders' cut data */
662 benderscutdata = SCIPbenderscutGetData(benderscut);
663 assert( benderscutdata != NULL );
664
665 SCIPfreeBlockMemory(scip, &benderscutdata);
666
668
669 return SCIP_OKAY;
670}
671
672
673/** execution method of Benders' decomposition cuts */
674static
676{ /*lint --e{715}*/
678 SCIP_BENDERSCUTDATA* benderscutdata;
679 SCIP_Bool nlprelaxation;
680 SCIP_Bool addcut;
682
683 assert(scip != NULL);
684 assert(benders != NULL);
686 assert(result != NULL);
688
689 /* retrieving the Benders' cut data */
690 benderscutdata = SCIPbenderscutGetData(benderscut);
691
692 /* if the cuts are generated prior to the solving stage, then rows can not be generated. So constraints must be
693 * added to the master problem.
694 */
696 addcut = FALSE;
697 else
698 addcut = benderscutdata->addcuts;
699
700 /* setting the name of the generated cut */
703
705
706 if( subproblem == NULL )
707 {
708 SCIPdebugMsg(scip, "The subproblem %d is set to NULL. The <%s> Benders' decomposition cut can not be executed.\n",
710
711 (*result) = SCIP_DIDNOTRUN;
712 return SCIP_OKAY;
713 }
714
715 /* setting a flag to indicate whether the NLP relaxation should be used to generate cuts */
717
718 /* only generate optimality cuts if the subproblem LP or NLP is optimal,
719 * since we use the dual solution of the LP/NLP to construct the optimality cut
720 */
724 {
725 /* generating a cut for a given subproblem */
728 FALSE, result) );
729
730 /* if it was not possible to generate a cut, this could be due to numerical issues. So the solution to the LP is
731 * resolved and the generation of the cut is reattempted. For NLPs, we do not have such a polishing yet.
732 */
733 if( (*result) == SCIP_DIDNOTFIND )
734 {
735 SCIP_Bool success;
736
737 SCIPdebugMsg(scip, "Numerical trouble generating optimality cut for subproblem %d.\n", probnumber);
738
739 if( !nlprelaxation )
740 {
741 SCIPdebugMsg(scip, "Attempting to polish the LP solution to find an alternative dual extreme point.\n");
742
744
745 /* only attempt to generate a cut if the solution polishing was successful */
746 if( success )
747 {
750 FALSE, result) );
751 }
752 }
753 else
754 {
755 SCIP_Real multiplier = 0.01;
756
757 SCIPdebugMsg(scip, "Attempting to resolve the NLP with a tighter feasibility tolerance to find an "
758 "alternative dual extreme point.\n");
759
760 while( multiplier > 1e-06 && (*result) == SCIP_DIDNOTFIND )
761 {
763
764 if( success )
765 {
768 FALSE, result) );
769 }
770
771 multiplier *= 0.1;
772 }
773 }
774 }
775 }
776
777 return SCIP_OKAY;
778}
779
780
781/*
782 * Benders' decomposition cuts specific interface methods
783 */
784
785/** creates the opt Benders' decomposition cuts and includes it in SCIP */
787 SCIP* scip, /**< SCIP data structure */
788 SCIP_BENDERS* benders /**< Benders' decomposition */
789 )
790{
791 SCIP_BENDERSCUTDATA* benderscutdata;
794
795 assert(benders != NULL);
796
797 /* create opt Benders' decomposition cuts data */
798 SCIP_CALL( SCIPallocBlockMemory(scip, &benderscutdata) );
799
801
802 /* include Benders' decomposition cuts */
805
807
808 /* setting the non fundamental callbacks via setter functions */
810
811 /* add opt Benders' decomposition cuts parameters */
812 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/benderscut/%s/addcuts",
815 "should cuts be generated and added to the cutpool instead of global constraints directly added to the problem.",
816 &benderscutdata->addcuts, FALSE, SCIP_DEFAULT_ADDCUTS, NULL, NULL) );
817
818 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "benders/%s/benderscut/%s/mir",
821 "should the mixed integer rounding procedure be applied to cuts",
822 &benderscutdata->calcmir, FALSE, SCIP_DEFAULT_CALCMIR, NULL, NULL) );
823
824 return SCIP_OKAY;
825}
826
827/** Generates a classical Benders' optimality cut using the dual solutions from the subproblem or the input arrays. If
828 * the dual solutions are input as arrays, then a mapping between the array indices and the rows/variables is required.
829 * As a cut strengthening approach, when an optimality cut is being generated (i.e. not for feasibility cuts) a MIR
830 * procedure is performed on the row. This procedure attempts to find a stronger constraint, if this doesn't happen,
831 * then the original constraint is added to SCIP.
832 *
833 * This method can also be used to generate a feasibility cut, if a problem to minimise the infeasibilities has been solved
834 * to generate the dual solutions
835 */
837 SCIP* masterprob, /**< the SCIP instance of the master problem */
838 SCIP* subproblem, /**< the SCIP instance of the pricing problem */
839 SCIP_BENDERS* benders, /**< the benders' decomposition */
840 SCIP_BENDERSCUT* benderscut, /**< the benders' decomposition cut method */
841 SCIP_SOL* sol, /**< primal CIP solution */
842 int probnumber, /**< the number of the pricing problem */
843 char* cutname, /**< the name for the cut to be generated */
844 SCIP_Real objective, /**< the objective function of the subproblem */
845 SCIP_Real* primalvals, /**< the primal solutions for the NLP, can be NULL */
846 SCIP_Real* consdualvals, /**< dual variables for the constraints, can be NULL */
847 SCIP_Real* varlbdualvals, /**< the dual variables for the variable lower bounds, can be NULL */
848 SCIP_Real* varubdualvals, /**< the dual variables for the variable upper bounds, can be NULL */
849 SCIP_HASHMAP* row2idx, /**< mapping between the row in the subproblem to the index in the dual array, can be NULL */
850 SCIP_HASHMAP* var2idx, /**< mapping from variable of the subproblem to the index in the dual arrays, can be NULL */
851 SCIP_BENDERSENFOTYPE type, /**< the enforcement type calling this function */
852 SCIP_Bool addcut, /**< should the Benders' cut be added as a cut or constraint */
853 SCIP_Bool feasibilitycut, /**< is this called for the generation of a feasibility cut */
854 SCIP_RESULT* result /**< the result from solving the subproblems */
855 )
856{
858 SCIP_CONS* cons;
859 SCIP_ROW* row;
860 SCIP_VAR** vars;
861 SCIP_Real* vals;
862 SCIP_Real lhs;
863 SCIP_Real rhs;
864 int nvars;
865 int varssize;
866 int nmastervars;
867 SCIP_Bool calcmir;
868 SCIP_Bool optimal;
869 SCIP_Bool success;
870 SCIP_Bool mirsuccess;
871
872 SCIP_Real checkobj;
873 SCIP_Real verifyobj;
874
877 assert(benders != NULL);
879 assert(result != NULL);
880 assert((primalvals == NULL && consdualvals == NULL && varlbdualvals == NULL && varubdualvals == NULL
881 && row2idx == NULL && var2idx == NULL)
882 || (primalvals != NULL && consdualvals != NULL && varlbdualvals != NULL && varubdualvals != NULL
883 && row2idx != NULL && var2idx != NULL));
884
885 row = NULL;
886 cons = NULL;
887
889 success = FALSE;
891
892 /* retrieving the Benders' decomposition constraint handler */
894
895 /* checking the optimality of the original problem with a comparison between the auxiliary variable and the
896 * objective value of the subproblem */
897 if( feasibilitycut )
898 optimal = FALSE;
899 else
900 {
902 }
903
904 if( optimal )
905 {
906 (*result) = SCIP_FEASIBLE;
907 SCIPdebugMsg(masterprob, "No cut added for subproblem %d\n", probnumber);
908 return SCIP_OKAY;
909 }
910
911 /* allocating memory for the variable and values arrays */
914 SCIP_CALL( SCIPallocClearBufferArray(masterprob, &vals, nmastervars) );
915 lhs = 0.0;
917 nvars = 0;
918 varssize = nmastervars;
919
921 {
922 /* computing the coefficients of the optimality cut */
924 &varssize, objective, primalvals, consdualvals, varlbdualvals, varubdualvals, row2idx,
925 var2idx, &checkobj, &success) );
926 }
927 else
928 {
929 /* computing the coefficients of the optimality cut */
931 &varssize, &checkobj, &success) );
932 }
933
934 /* if success is FALSE, then there was an error in generating the optimality cut. No cut will be added to the master
935 * problem. Otherwise, the constraint is added to the master problem.
936 */
937 if( !success )
938 {
939 (*result) = SCIP_DIDNOTFIND;
940 SCIPdebugMsg(masterprob, "Error in generating Benders' optimality cut for problem %d.\n", probnumber);
941 }
942 else
943 {
944 /* initially a row/constraint is created for the optimality cut using the master variables and coefficients
945 * computed in computeStandardLPOptimalityCut. At this stage, the auxiliary variable is not added since the
946 * activity of the row/constraint in its current form is used to determine the validity of the optimality cut.
947 */
948 if( addcut )
949 {
952 }
953 else
954 {
955 SCIP_CALL( SCIPcreateConsBasicLinear(masterprob, &cons, cutname, nvars, vars, vals, lhs, rhs) );
958 }
959
960 /* computing the objective function from the cut activity to verify the accuracy of the constraint */
961 verifyobj = 0.0;
962 if( addcut )
963 {
965 }
966 else
967 {
969 }
970
972 {
973 success = FALSE;
974 SCIPdebugMsg(masterprob, "The violation of the feasibility cut (%g) is too small. Skipping feasibility cut.\n", verifyobj);
975 }
976
977 /* it is possible that numerics will cause the generated cut to be invalid. This cut should not be added to the
978 * master problem, since its addition could cut off feasible solutions. The success flag is set of false, indicating
979 * that the Benders' cut could not find a valid cut.
980 */
981 if( !feasibilitycut && !SCIPisFeasEQ(masterprob, checkobj, verifyobj) )
982 {
983 SCIP_Bool valid;
984
985 /* the difference in the checkobj and verifyobj could be due to the setup tolerances. This is checked, and if
986 * so, then the generated cut is still valid
987 */
988 SCIP_CALL( checkSetupTolerances(masterprob, sol, vars, vals, lhs, checkobj, nvars, &valid) );
989
990 if( !valid )
991 {
992 success = FALSE;
993 SCIPdebugMsg(masterprob, "The objective function and cut activity are not equal (%g != %g).\n", checkobj,
994 verifyobj);
995
996#ifdef SCIP_DEBUG
997 /* we only need to abort if cut strengthen is not used. If cut strengthen has been used in this round and the
998 * cut could not be generated, then another subproblem solving round will be executed
999 */
1000 if( !SCIPbendersInStrengthenRound(benders) )
1001 {
1002#ifdef SCIP_MOREDEBUG
1003 int i;
1004
1005 for( i = 0; i < nvars; i++ )
1006 printf("<%s> %g %g\n", SCIPvarGetName(vars[i]), vals[i], SCIPgetSolVal(masterprob, sol, vars[i]));
1007#endif
1008 SCIPABORT();
1009 }
1010#endif
1011 }
1012 }
1013
1014 if( success )
1015 {
1016 /* adding the auxiliary variable to the optimality cut. The auxiliary variable is added to the vars and vals
1017 * arrays prior to the execution of the MIR procedure. This is necessary because the MIR procedure must be
1018 * executed on the complete cut, not just the row/constraint without the auxiliary variable.
1019 */
1020 if( !feasibilitycut )
1021 {
1023 }
1024
1025 /* performing the MIR procedure. If the procedure is successful, then the vars and vals arrays are no longer
1026 * needed for creating the optimality cut. These are superseeded with the cutcoefs and cutinds arrays. In the
1027 * case that the MIR procedure is successful, the row/constraint that has been created previously is destroyed
1028 * and the MIR cut is added in its place
1029 */
1030 if( calcmir )
1031 {
1032 SCIP_Real* cutcoefs;
1033 int* cutinds;
1034 SCIP_Real cutrhs;
1035 int cutnnz;
1036
1037 /* allocating memory to compute the MIR cut */
1040
1043
1044 /* if the MIR cut was computed successfully, then the current row/constraint needs to be destroyed and
1045 * replaced with the updated coefficients
1046 */
1047 if( mirsuccess )
1048 {
1050 int i;
1051
1053
1054 if( addcut )
1055 {
1057
1060
1061 for( i = 0; i < cutnnz; i++)
1062 {
1064 }
1065 }
1066 else
1067 {
1069
1074
1075 for( i = 0; i < cutnnz; i++ )
1076 {
1078 }
1079 }
1080 }
1081
1082 /* freeing the memory required to compute the MIR cut */
1085 }
1086
1087 /* adding the constraint to the master problem */
1088 if( addcut )
1089 {
1090 SCIP_Bool infeasible;
1091
1092 /* adding the auxiliary variable coefficient to the row. This is only added if the MIR procedure is not
1093 * successful. If the MIR procedure was successful, then the auxiliary variable is already included in the
1094 * row
1095 */
1096 if( !feasibilitycut && !mirsuccess )
1097 {
1098 SCIP_CALL( SCIPaddVarToRow(masterprob, row, vars[nvars - 1], vals[nvars - 1]) );
1099 }
1100
1102 {
1103 SCIP_CALL( SCIPaddRow(masterprob, row, FALSE, &infeasible) );
1104 assert(!infeasible);
1105 }
1106 else
1107 {
1110 }
1111
1112 (*result) = SCIP_SEPARATED;
1113 }
1114 else
1115 {
1116 /* adding the auxiliary variable coefficient to the row. This is only added if the MIR procedure is not
1117 * successful. If the MIR procedure was successful, then the auxiliary variable is already included in the
1118 * constraint.
1119 */
1120 if( !feasibilitycut && !mirsuccess )
1121 {
1122 SCIP_CALL( SCIPaddCoefLinear(masterprob, cons, vars[nvars - 1], vals[nvars - 1]) );
1123 }
1124
1126
1128
1129 (*result) = SCIP_CONSADDED;
1130 }
1131
1132 /* storing the data that is used to create the cut */
1133 SCIP_CALL( SCIPstoreBendersCut(masterprob, benders, vars, vals, lhs, rhs, nvars) );
1134 }
1135 else
1136 {
1137 (*result) = SCIP_DIDNOTFIND;
1138 SCIPdebugMsg(masterprob, "Error in generating Benders' %s cut for problem %d.\n", feasibilitycut ? "feasibility" : "optimality", probnumber);
1139 }
1140
1141 /* releasing the row or constraint */
1142 if( addcut )
1143 {
1144 /* release the row */
1146 }
1147 else
1148 {
1149 /* release the constraint */
1151 }
1152 }
1153
1156
1157 return SCIP_OKAY;
1158}
1159
1160
1161/** adds the gradient of a nonlinear row in the current NLP solution of a subproblem to a linear row or constraint in the master problem
1162 *
1163 * Only computes gradient w.r.t. master problem variables.
1164 * Computes also the directional derivative, that is, mult times gradient times solution.
1165 */
1167 SCIP* masterprob, /**< the SCIP instance of the master problem */
1168 SCIP* subproblem, /**< the SCIP instance of the subproblem */
1169 SCIP_BENDERS* benders, /**< the benders' decomposition structure */
1170 SCIP_NLROW* nlrow, /**< nonlinear row */
1171 SCIP_Real mult, /**< multiplier */
1172 SCIP_Real* primalvals, /**< the primal solutions for the NLP, can be NULL */
1173 SCIP_HASHMAP* var2idx, /**< mapping from variable of the subproblem to the index in the dual arrays, can be NULL */
1174 SCIP_Real* dirderiv, /**< storage to add directional derivative */
1175 SCIP_VAR*** vars, /**< pointer to array of variables in the generated cut with non-zero coefficient */
1176 SCIP_Real** vals, /**< pointer to array of coefficients of the variables in the generated cut */
1177 int* nvars, /**< the number of variables in the cut */
1178 int* varssize /**< the number of variables in the array */
1179 )
1180{
1181 SCIP_EXPR* expr;
1182 SCIP_VAR* var;
1184 SCIP_Real coef;
1185 int i;
1186
1189 assert(benders != NULL);
1190 assert(nlrow != NULL);
1191 assert((primalvals == NULL && var2idx == NULL) || (primalvals != NULL && var2idx != NULL));
1192 assert(mult != 0.0);
1193 assert(dirderiv != NULL);
1194 assert(vars != NULL);
1195 assert(vals != NULL);
1196
1197 /* linear part */
1198 for( i = 0; i < SCIPnlrowGetNLinearVars(nlrow); i++ )
1199 {
1200 var = SCIPnlrowGetLinearVars(nlrow)[i];
1201 assert(var != NULL);
1202
1203 /* retrieving the master problem variable for the given subproblem variable. */
1205 if( mastervar == NULL )
1206 continue;
1207
1208 coef = mult * SCIPnlrowGetLinearCoefs(nlrow)[i];
1209
1210 /* adding the variable to the storage */
1211 SCIP_CALL( addVariableToArray(masterprob, vars, vals, mastervar, coef, nvars, varssize) );
1212
1213 *dirderiv += coef * getNlpVarSol(var, primalvals, var2idx);
1214 }
1215
1216 /* expression part */
1217 expr = SCIPnlrowGetExpr(nlrow);
1218 if( expr != NULL )
1219 {
1222
1223 /* create primalsol, either from primalvals, or pointing to NLP solution */
1224 if( primalvals != NULL )
1225 {
1227
1228 /* TODO would be better to change primalvals to a SCIP_SOL and do this once for the whole NLP instead of repeating it for each expr */
1229 for( i = 0; i < SCIPhashmapGetNEntries(var2idx); ++i )
1230 {
1232 entry = SCIPhashmapGetEntry(var2idx, i);
1233 if( entry == NULL )
1234 continue;
1236 }
1237 }
1238 else
1239 {
1241 }
1242
1243 /* eval gradient */
1245
1246 assert(SCIPexprGetDerivative(expr) != SCIP_INVALID); /* TODO this should be a proper check&abort */ /*lint !e777*/
1247
1249
1250 /* update corresponding gradient entry */
1253 for( ; !SCIPexpriterIsEnd(it); expr = SCIPexpriterGetNext(it) ) /*lint !e441*/ /*lint !e440*/
1254 {
1255 if( !SCIPisExprVar(subproblem, expr) )
1256 continue;
1257
1258 var = SCIPgetVarExprVar(expr);
1259 assert(var != NULL);
1260
1261 /* retrieving the master problem variable for the given subproblem variable. */
1263 if( mastervar == NULL )
1264 continue;
1265
1266 assert(SCIPexprGetDerivative(expr) != SCIP_INVALID); /*lint !e777*/
1267 coef = mult * SCIPexprGetDerivative(expr);
1268
1269 /* adding the variable to the storage */
1270 SCIP_CALL( addVariableToArray(masterprob, vars, vals, mastervar, coef, nvars, varssize) );
1271
1272 *dirderiv += coef * getNlpVarSol(var, primalvals, var2idx);
1273 }
1275 }
1276
1277 return SCIP_OKAY;
1278}
static SCIP_RETCODE checkSetupTolerances(SCIP *masterprob, SCIP_SOL *sol, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real checkobj, int nvars, SCIP_Bool *valid)
#define SCIP_DEFAULT_ADDCUTS
static SCIP_RETCODE addVariableToArray(SCIP *masterprob, SCIP_VAR ***vars, SCIP_Real **vals, SCIP_VAR *addvar, SCIP_Real addval, int *nvars, int *varssize)
static SCIP_RETCODE computeStandardLPOptimalityCut(SCIP *masterprob, SCIP *subproblem, SCIP_BENDERS *benders, SCIP_VAR ***vars, SCIP_Real **vals, SCIP_Real *lhs, SCIP_Real *rhs, int *nvars, int *varssize, SCIP_Real *checkobj, SCIP_Bool *success)
#define BENDERSCUT_LPCUT
static SCIP_RETCODE resolveNLPWithTighterFeastol(SCIP *subproblem, SCIP_Real multiplier, SCIP_Bool *success)
static SCIP_RETCODE addAuxiliaryVariableToCut(SCIP *masterprob, SCIP_BENDERS *benders, SCIP_VAR **vars, SCIP_Real *vals, int *nvars, int probnumber)
#define SCIP_DEFAULT_CALCMIR
static SCIP_RETCODE computeStandardNLPOptimalityCut(SCIP *masterprob, SCIP *subproblem, SCIP_BENDERS *benders, SCIP_VAR ***vars, SCIP_Real **vals, SCIP_Real *lhs, SCIP_Real *rhs, int *nvars, int *varssize, SCIP_Real objective, SCIP_Real *primalvals, SCIP_Real *consdualvals, SCIP_Real *varlbdualvals, SCIP_Real *varubdualvals, SCIP_HASHMAP *row2idx, SCIP_HASHMAP *var2idx, SCIP_Real *checkobj, SCIP_Bool *success)
static SCIP_Real getNlpVarSol(SCIP_VAR *var, SCIP_Real *primalvals, SCIP_HASHMAP *var2idx)
#define BENDERSCUT_PRIORITY
#define BENDERSCUT_DESC
#define BENDERSCUT_NAME
static SCIP_RETCODE computeMIRForOptimalityCut(SCIP *masterprob, SCIP_SOL *sol, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, int nvars, SCIP_Real *cutcoefs, int *cutinds, SCIP_Real *cutrhs, int *cutnnz, SCIP_Bool *success)
static SCIP_RETCODE polishSolution(SCIP *subproblem, SCIP_Bool *success)
Generates a standard Benders' decomposition optimality cut.
Constraint handler for linear constraints in their most general form, .
#define SCIP_MAXSTRLEN
Definition def.h:302
#define SCIP_INVALID
Definition def.h:206
#define TRUE
Definition def.h:95
#define FALSE
Definition def.h:96
#define SCIPABORT()
Definition def.h:360
#define REALABS(x)
Definition def.h:210
#define SCIP_CALL(x)
Definition def.h:388
SCIP_RETCODE SCIPgenerateAndApplyBendersOptCut(SCIP *masterprob, SCIP *subproblem, SCIP_BENDERS *benders, SCIP_BENDERSCUT *benderscut, SCIP_SOL *sol, int probnumber, char *cutname, SCIP_Real objective, SCIP_Real *primalvals, SCIP_Real *consdualvals, SCIP_Real *varlbdualvals, SCIP_Real *varubdualvals, SCIP_HASHMAP *row2idx, SCIP_HASHMAP *var2idx, SCIP_BENDERSENFOTYPE type, SCIP_Bool addcut, SCIP_Bool feasibilitycut, SCIP_RESULT *result)
SCIP_RETCODE SCIPaddNlRowGradientBenderscutOpt(SCIP *masterprob, SCIP *subproblem, SCIP_BENDERS *benders, SCIP_NLROW *nlrow, SCIP_Real mult, SCIP_Real *primalvals, SCIP_HASHMAP *var2idx, SCIP_Real *dirderiv, SCIP_VAR ***vars, SCIP_Real **vals, int *nvars, int *varssize)
SCIP_RETCODE SCIPincludeBenderscutOpt(SCIP *scip, SCIP_BENDERS *benders)
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
SCIP_Real SCIPgetLhsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPcreateConsBasicLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs)
SCIP_Real SCIPgetActivityLinear(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol)
int SCIPgetSubscipDepth(SCIP *scip)
Definition scip_copy.c:2605
SCIP_STAGE SCIPgetStage(SCIP *scip)
SCIP_Real SCIPgetTransObjoffset(SCIP *scip)
Definition scip_prob.c:1367
int SCIPgetNVars(SCIP *scip)
Definition scip_prob.c:1992
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition scip_prob.c:2770
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition scip_prob.c:1947
SCIP_OBJSENSE SCIPgetObjsense(SCIP *scip)
Definition scip_prob.c:1225
int SCIPgetNFixedVars(SCIP *scip)
Definition scip_prob.c:2309
SCIP_VAR ** SCIPgetFixedVars(SCIP *scip)
Definition scip_prob.c:2266
SCIP_Real SCIPgetTransObjscale(SCIP *scip)
Definition scip_prob.c:1390
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition misc.c:3231
int SCIPhashmapEntryGetImageInt(SCIP_HASHMAPENTRY *entry)
Definition misc.c:3530
int SCIPhashmapGetNEntries(SCIP_HASHMAP *hashmap)
Definition misc.c:3491
SCIP_HASHMAPENTRY * SCIPhashmapGetEntry(SCIP_HASHMAP *hashmap, int entryidx)
Definition misc.c:3499
void * SCIPhashmapEntryGetOrigin(SCIP_HASHMAPENTRY *entry)
Definition misc.c:3510
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition misc.c:3373
#define SCIPdebugMsg
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition scip_param.c:487
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition scip_param.c:57
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
Definition scip_param.c:269
SCIP_VAR * SCIPbendersGetAuxiliaryVar(SCIP_BENDERS *benders, int probnumber)
Definition benders.c:6138
SCIP_RETCODE SCIPgetBendersMasterVar(SCIP *scip, SCIP_BENDERS *benders, SCIP_VAR *var, SCIP_VAR **mappedvar)
const char * SCIPbendersGetName(SCIP_BENDERS *benders)
Definition benders.c:5902
int SCIPbendersGetNSubproblems(SCIP_BENDERS *benders)
Definition benders.c:5946
SCIP * SCIPbendersSubproblem(SCIP_BENDERS *benders, int probnumber)
Definition benders.c:5956
SCIP_RETCODE SCIPcheckBendersSubproblemOptimality(SCIP *scip, SCIP_BENDERS *benders, SCIP_SOL *sol, int probnumber, SCIP_Bool *optimal)
SCIP_Real SCIPbendersGetSubproblemObjval(SCIP_BENDERS *benders, int probnumber)
Definition benders.c:6177
SCIP_Bool SCIPbendersInStrengthenRound(SCIP_BENDERS *benders)
Definition benders.c:6425
SCIP_RETCODE SCIPincludeBenderscutBasic(SCIP *scip, SCIP_BENDERS *benders, SCIP_BENDERSCUT **benderscutptr, const char *name, const char *desc, int priority, SCIP_Bool islpcut, SCIP_DECL_BENDERSCUTEXEC((*benderscutexec)), SCIP_BENDERSCUTDATA *benderscutdata)
SCIP_RETCODE SCIPsetBenderscutFree(SCIP *scip, SCIP_BENDERSCUT *benderscut,)
void SCIPbenderscutSetData(SCIP_BENDERSCUT *benderscut, SCIP_BENDERSCUTDATA *benderscutdata)
Definition benderscut.c:413
const char * SCIPbenderscutGetName(SCIP_BENDERSCUT *benderscut)
Definition benderscut.c:492
SCIP_BENDERSCUTDATA * SCIPbenderscutGetData(SCIP_BENDERSCUT *benderscut)
Definition benderscut.c:403
SCIP_RETCODE SCIPstoreBendersCut(SCIP *scip, SCIP_BENDERS *benders, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, int nvars)
SCIP_Longint SCIPbenderscutGetNFound(SCIP_BENDERSCUT *benderscut)
Definition benderscut.c:543
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition scip_cons.c:886
SCIP_RETCODE SCIPsetConsDynamic(SCIP *scip, SCIP_CONS *cons, SCIP_Bool dynamic)
Definition scip_cons.c:1395
SCIP_RETCODE SCIPsetConsRemovable(SCIP *scip, SCIP_CONS *cons, SCIP_Bool removable)
Definition scip_cons.c:1420
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition scip_cons.c:1119
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
Definition scip_cut.c:361
SCIP_Bool SCIPcutsTightenCoefficients(SCIP *scip, SCIP_Bool cutislocal, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, int *nchgcoefs)
Definition cuts.c:1535
SCIP_RETCODE SCIPaggrRowCreate(SCIP *scip, SCIP_AGGRROW **aggrrow)
Definition cuts.c:1731
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
Definition scip_cut.c:135
SCIP_RETCODE SCIPaggrRowAddCustomCons(SCIP *scip, SCIP_AGGRROW *aggrrow, int *inds, SCIP_Real *vals, int len, SCIP_Real rhs, SCIP_Real weight, int rank, SCIP_Bool local)
Definition cuts.c:2088
void SCIPaggrRowFree(SCIP *scip, SCIP_AGGRROW **aggrrow)
Definition cuts.c:1763
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition scip_cut.c:250
SCIP_RETCODE SCIPcalcFlowCover(SCIP *scip, SCIP_SOL *sol, SCIP_Bool postprocess, SCIP_Real boundswitch, SCIP_Bool allowlocal, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, SCIP_Real *cutefficacy, int *cutrank, SCIP_Bool *cutislocal, SCIP_Bool *success)
Definition cuts.c:7428
SCIP_RETCODE SCIPcalcMIR(SCIP *scip, SCIP_SOL *sol, SCIP_Bool postprocess, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Bool fixintegralrhs, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_Real scale, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, SCIP_Real *cutefficacy, int *cutrank, SCIP_Bool *cutislocal, SCIP_Bool *success)
Definition cuts.c:3879
SCIP_RETCODE SCIPevalExprGradient(SCIP *scip, SCIP_EXPR *expr, SCIP_SOL *sol, SCIP_Longint soltag)
Definition scip_expr.c:1657
SCIP_Bool SCIPexpriterIsEnd(SCIP_EXPRITER *iterator)
Definition expriter.c:968
SCIP_Real SCIPexprGetDerivative(SCIP_EXPR *expr)
Definition expr.c:3901
SCIP_Bool SCIPisExprVar(SCIP *scip, SCIP_EXPR *expr)
Definition scip_expr.c:1421
SCIP_RETCODE SCIPcreateExpriter(SCIP *scip, SCIP_EXPRITER **iterator)
Definition scip_expr.c:2296
SCIP_EXPR * SCIPexpriterGetNext(SCIP_EXPRITER *iterator)
Definition expriter.c:857
SCIP_VAR * SCIPgetVarExprVar(SCIP_EXPR *expr)
Definition expr_var.c:416
void SCIPfreeExpriter(SCIP_EXPRITER **iterator)
Definition scip_expr.c:2310
SCIP_RETCODE SCIPexpriterInit(SCIP_EXPRITER *iterator, SCIP_EXPR *expr, SCIP_EXPRITER_TYPE type, SCIP_Bool allowrevisit)
Definition expriter.c:500
SCIP_ROW ** SCIPgetLPRows(SCIP *scip)
Definition scip_lp.c:605
int SCIPgetNLPRows(SCIP *scip)
Definition scip_lp.c:626
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition scip_lp.c:168
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition scip_mem.h:126
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition scip_mem.c:139
#define SCIPallocBufferArray(scip, ptr, num)
Definition scip_mem.h:124
#define SCIPreallocBufferArray(scip, ptr, num)
Definition scip_mem.h:128
#define SCIPfreeBufferArray(scip, ptr)
Definition scip_mem.h:136
#define SCIPfreeBlockMemory(scip, ptr)
Definition scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition scip_mem.h:89
int SCIPgetNNlpis(SCIP *scip)
Definition scip_nlpi.c:199
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
Definition scip_nlp.c:110
SCIP_NLPSOLSTAT SCIPgetNLPSolstat(SCIP *scip)
Definition scip_nlp.c:541
SCIP_RETCODE SCIPsolveNLPParam(SCIP *scip, SCIP_NLPPARAM param)
Definition scip_nlp.c:512
int SCIPgetNNLPVars(SCIP *scip)
Definition scip_nlp.c:201
int SCIPgetNNLPNlRows(SCIP *scip)
Definition scip_nlp.c:341
SCIP_VAR ** SCIPgetNLPVars(SCIP *scip)
Definition scip_nlp.c:179
SCIP_Bool SCIPhasNLPSolution(SCIP *scip)
Definition scip_nlp.c:638
SCIP_NLROW ** SCIPgetNLPNlRows(SCIP *scip)
Definition scip_nlp.c:319
SCIP_NLPTERMSTAT SCIPgetNLPTermstat(SCIP *scip)
Definition scip_nlp.c:563
int SCIPnlrowGetNLinearVars(SCIP_NLROW *nlrow)
Definition nlp.c:1773
SCIP_VAR ** SCIPnlrowGetLinearVars(SCIP_NLROW *nlrow)
Definition nlp.c:1783
SCIP_Real SCIPnlrowGetDualsol(SCIP_NLROW *nlrow)
Definition nlp.c:1885
SCIP_EXPR * SCIPnlrowGetExpr(SCIP_NLROW *nlrow)
Definition nlp.c:1803
SCIP_Real * SCIPnlrowGetLinearCoefs(SCIP_NLROW *nlrow)
Definition nlp.c:1793
SCIP_Bool SCIPinProbing(SCIP *scip)
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition lp.c:17292
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition lp.c:17302
SCIP_RETCODE SCIPcreateEmptyRowConshdlr(SCIP *scip, SCIP_ROW **row, SCIP_CONSHDLR *conshdlr, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition scip_lp.c:1391
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition scip_lp.c:1701
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition scip_lp.c:1562
SCIP_RETCODE SCIPaddVarsToRow(SCIP *scip, SCIP_ROW *row, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition scip_lp.c:1727
SCIP_Real SCIProwGetDualsol(SCIP_ROW *row)
Definition lp.c:17312
SCIP_Real SCIPgetRowSolActivity(SCIP *scip, SCIP_ROW *row, SCIP_SOL *sol)
Definition scip_lp.c:2144
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition scip_sol.c:1775
SCIP_RETCODE SCIPcreateNLPSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition scip_sol.c:398
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition scip_sol.c:1221
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition scip_sol.c:1361
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeastol(SCIP *scip)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPvarGetSol(SCIP_VAR *var, SCIP_Bool getlpval)
Definition var.c:13246
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition var.c:17966
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition var.c:17748
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition var.c:17590
const char * SCIPvarGetName(SCIP_VAR *var)
Definition var.c:17241
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition var.c:17956
SCIP_Real SCIPgetVarRedcost(SCIP *scip, SCIP_VAR *var)
Definition scip_var.c:1864
SCIP_Real SCIPvarGetNLPSol(SCIP_VAR *var)
Definition var.c:18287
SCIP_Real SCIPvarGetUnchangedObj(SCIP_VAR *var)
Definition var.c:17758
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition misc.c:10788
return SCIP_OKAY
SCIPfreeSol(scip, &heurdata->sol))
SCIPcreateSol(scip, &heurdata->sol, heur))
SCIP_Bool lperror
SCIP_Bool cutoff
static SCIP_SOL * sol
assert(minobj< SCIPgetCutoffbound(scip))
int nvars
SCIP_VAR * var
static SCIP_VAR ** vars
static const char * paramname[]
Definition lpi_msk.c:5096
#define NULL
Definition lpi_spx1.cpp:161
public methods for Benders' decomposition
public methods for Benders' decomposition cuts
public functions to work with algebraic expressions
public methods for LP management
public methods for message output
#define SCIPerrorMessage
Definition pub_message.h:64
#define SCIPdebugPrintCons(x, y, z)
public data structures and miscellaneous methods
internal miscellaneous methods for linear constraints
public methods for NLP management
public methods for problem variables
SCIP callable library.
@ SCIP_BENDERSENFOTYPE_RELAX
@ SCIP_BENDERSENFOTYPE_LP
@ SCIP_BENDERSENFOTYPE_CHECK
@ SCIP_BENDERSENFOTYPE_PSEUDO
enum SCIP_BendersEnfoType SCIP_BENDERSENFOTYPE
#define SCIP_DECL_BENDERSCUTEXEC(x)
struct SCIP_BenderscutData SCIP_BENDERSCUTDATA
#define SCIP_DECL_BENDERSCUTFREE(x)
@ SCIP_EXPRITER_DFS
Definition type_expr.h:700
@ SCIP_LPSOLSTAT_OPTIMAL
Definition type_lp.h:43
#define SCIP_NLPPARAM_DEFAULT(scip)
Definition type_nlpi.h:126
enum SCIP_NlpSolStat SCIP_NLPSOLSTAT
Definition type_nlpi.h:168
@ SCIP_NLPSOLSTAT_FEASIBLE
Definition type_nlpi.h:162
@ SCIP_NLPSOLSTAT_LOCOPT
Definition type_nlpi.h:161
@ SCIP_NLPSOLSTAT_GLOBOPT
Definition type_nlpi.h:160
enum SCIP_NlpTermStat SCIP_NLPTERMSTAT
Definition type_nlpi.h:194
@ SCIP_OBJSENSE_MINIMIZE
Definition type_prob.h:48
@ SCIP_DIDNOTRUN
Definition type_result.h:42
@ SCIP_FEASIBLE
Definition type_result.h:45
@ SCIP_DIDNOTFIND
Definition type_result.h:44
@ SCIP_CONSADDED
Definition type_result.h:52
@ SCIP_SEPARATED
Definition type_result.h:49
enum SCIP_Result SCIP_RESULT
Definition type_result.h:61
@ SCIP_ERROR
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_STAGE_INITSOLVE
Definition type_set.h:52
@ SCIP_STAGE_SOLVING
Definition type_set.h:53