SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
pub_benders.h
Go to the documentation of this file.
1/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2/* */
3/* This file is part of the program and library */
4/* SCIP --- Solving Constraint Integer Programs */
5/* */
6/* Copyright (c) 2002-2024 Zuse Institute Berlin (ZIB) */
7/* */
8/* Licensed under the Apache License, Version 2.0 (the "License"); */
9/* you may not use this file except in compliance with the License. */
10/* You may obtain a copy of the License at */
11/* */
12/* http://www.apache.org/licenses/LICENSE-2.0 */
13/* */
14/* Unless required by applicable law or agreed to in writing, software */
15/* distributed under the License is distributed on an "AS IS" BASIS, */
16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17/* See the License for the specific language governing permissions and */
18/* limitations under the License. */
19/* */
20/* You should have received a copy of the Apache-2.0 license */
21/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22/* */
23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
25/**@file pub_benders.h
26 * @ingroup PUBLICCOREAPI
27 * @brief public 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#ifndef __SCIP_PUB_BENDERS_H__
34#define __SCIP_PUB_BENDERS_H__
35
36#include "scip/def.h"
37#include "scip/type_benders.h"
39#include "scip/type_misc.h"
40#include "scip/type_retcode.h"
41#include "scip/type_scip.h"
42#include "scip/type_var.h"
43#include "scip/type_stat.h"
44#include "scip/type_nlpi.h"
45
46#ifdef __cplusplus
47extern "C" {
48#endif
49
50/**@addtogroup PublicBendersMethods
51 *
52 * @{
53 */
54
55/** compares two benderss w. r. to their priority */
58
59/** comparison method for sorting benderss w.r.t. to their name */
62
63/** gets user data of Benders' decomposition */
66 SCIP_BENDERS* benders /**< Benders' decomposition */
67 );
68
69/** sets user data of Benders' decomposition; user has to free old data in advance! */
72 SCIP_BENDERS* benders, /**< Benders' decomposition */
73 SCIP_BENDERSDATA* bendersdata /**< new Benders' decomposition user data */
74 );
75
76/** gets name of Benders' decomposition */
78const char* SCIPbendersGetName(
79 SCIP_BENDERS* benders /**< Benders' decomposition */
80 );
81
82/** gets description of Benders' decomposition */
84const char* SCIPbendersGetDesc(
85 SCIP_BENDERS* benders /**< Benders' decomposition */
86 );
87
88/** gets priority of Benders' decomposition */
91 SCIP_BENDERS* benders /**< Benders' decomposition */
92 );
93
94/** gets the number of subproblems for the Benders' decomposition */
97 SCIP_BENDERS* benders /**< the Benders' decomposition data structure */
98 );
99
100/** returns the SCIP instance for a given subproblem */
103 SCIP_BENDERS* benders, /**< the Benders' decomposition data structure */
104 int probnumber /**< the subproblem number */
105 );
106
107/** gets the number of times, the Bender' decomposition was called and tried to find a violated second stage constraint */
110 SCIP_BENDERS* benders /**< Benders' decomposition */
111 );
112
113/** gets the number of optimality cuts found by the collection of Benders' decomposition subproblems */
116 SCIP_BENDERS* benders /**< Benders' decomposition */
117 );
118
119/** gets the number of cuts found from the strengthening round */
122 SCIP_BENDERS* benders /**< Benders' decomposition */
123 );
124
125/** gets the number of calls to the strengthening round */
128 SCIP_BENDERS* benders /**< Benders' decomposition */
129 );
130
131/** gets the number of calls to the strengthening round that fail */
134 SCIP_BENDERS* benders /**< Benders' decomposition */
135 );
136
137/** gets time in seconds used in this Benders' decomposition for setting up for next stages */
140 SCIP_BENDERS* benders /**< Benders' decomposition */
141 );
142
143/** gets execution time in seconds used in this Benders' decomposition */
145SCIP_Real SCIPbendersGetTime(
146 SCIP_BENDERS* benders /**< Benders' decomposition */
147 );
148
149/** Is Benders' decomposition initialized? */
152 SCIP_BENDERS* benders /**< Benders' decomposition */
153 );
154
155/** returns whether the given Benders' decomposition is in use in the current problem */
157SCIP_Bool SCIPbendersIsActive(
158 SCIP_BENDERS* benders /**< the Benders' decomposition structure */
159 );
160
161/** Returns whether only the convex relaxations will be checked in this solve loop
162 * when Benders' is used in the LNS heuristics, only the convex relaxations of the master/subproblems are checked,
163 * i.e. no integer cuts are generated. In this case, then Benders' decomposition is performed under the assumption
164 * that all subproblems are convex relaxations.
165 */
168 SCIP_BENDERS* benders, /**< Benders' decomposition */
169 SCIP_Bool subscipsoff /**< flag indicating whether plugins using sub-SCIPs are deactivated */
170 );
171
172/** returns NLP solver parameters used for solving NLP subproblems */
175 SCIP_BENDERS* benders /**< Benders' decomposition */
176);
177
178/** Are Benders' cuts generated from the LP solutions? */
180SCIP_Bool SCIPbendersCutLP(
181 SCIP_BENDERS* benders /**< Benders' decomposition */
182 );
183
184/** Are Benders' cuts generated from the pseudo solutions? */
186SCIP_Bool SCIPbendersCutPseudo(
187 SCIP_BENDERS* benders /**< Benders' decomposition */
188 );
189
190/** Are Benders' cuts generated from the relaxation solutions? */
193 SCIP_BENDERS* benders /**< Benders' decomposition */
194 );
195
196/** Should this Benders' use the auxiliary variables from the highest priority Benders'? */
199 SCIP_BENDERS* benders /**< Benders' decomposition */
200 );
201
202/** sets the subproblem setup flag */
205 SCIP_BENDERS* benders, /**< Benders' decomposition */
206 int probnumber, /**< the subproblem number */
207 SCIP_Bool issetup /**< flag to indicate whether the subproblem has been setup */
208 );
209
210/** returns the subproblem setup flag */
213 SCIP_BENDERS* benders, /**< Benders' decomposition */
214 int probnumber /**< the subproblem number */
215 );
216
217/** returns the auxiliary variable for the given subproblem */
220 SCIP_BENDERS* benders, /**< Benders' decomposition */
221 int probnumber /**< the subproblem number */
222 );
223
224/** returns all auxiliary variables */
227 SCIP_BENDERS* benders /**< Benders' decomposition */
228 );
229
230/** stores the objective function value of the subproblem for use in cut generation */
233 SCIP_BENDERS* benders, /**< Benders' decomposition */
234 int probnumber, /**< the subproblem number */
235 SCIP_Real objval /**< the objective function value for the subproblem */
236 );
237
238/** returns the objective function value of the subproblem for use in cut generation */
241 SCIP_BENDERS* benders, /**< Benders' decomposition */
242 int probnumber /**< the subproblem number */
243 );
244
245/** returns the number of cuts that have been added for storage */
248 SCIP_BENDERS* benders /**< Benders' decomposition cut */
249 );
250
251/** returns the data for the cuts that have been added by the Benders' cut plugin */
254 SCIP_BENDERS* benders, /**< Benders' decomposition cut */
255 int cutidx, /**< the index for the cut data that is requested */
256 SCIP_VAR*** vars, /**< the variables that have non-zero coefficients in the cut */
257 SCIP_Real** vals, /**< the coefficients of the variables in the cut */
258 SCIP_Real* lhs, /**< the left hand side of the cut */
259 SCIP_Real* rhs, /**< the right hand side of the cut */
260 int* nvars /**< the number of variables with non-zero coefficients in the cut */
261 );
262
263/** returns the original problem data for the cuts that have been added by the Benders' cut plugin. The stored
264 * variables and values will populate the input vars and vals arrays. Thus, memory must be allocated for the vars and
265 * vals arrays
266 */
269 SCIP_BENDERS* benders, /**< Benders' decomposition cut */
270 int cutidx, /**< the index for the cut data that is requested */
271 SCIP_VAR*** vars, /**< the variables that have non-zero coefficients in the cut */
272 SCIP_Real** vals, /**< the coefficients of the variables in the 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 with non-zero coefficients in the cut */
276 int varssize /**< the available slots in the array */
277 );
278
279/*
280 * Public functions associated with Benders' cuts
281 */
282
283/** returns the Benders' cut of the given name, or NULL if not existing */
286 SCIP_BENDERS* benders, /**< Benders' decomposition */
287 const char* name /**< name of Benderscut' decomposition */
288 );
289
290
291/** returns the array of currently available Benders' cuts; active Benders' decomposition are in the first slots of
292 * the array
293 */
296 SCIP_BENDERS* benders /**< Benders' decomposition */
297 );
298
299
300/** returns the number of currently available Benders' cuts */
303 SCIP_BENDERS* benders /**< Benders' decomposition */
304 );
305
306/** sets the priority of a Benders' decomposition */
309 SCIP_BENDERS* benders, /**< Benders' decomposition */
310 SCIP_BENDERSCUT* benderscut, /**< Benders' cut */
311 int priority /**< new priority of the Benders' decomposition */
312 );
313
314/** returns whether the solution has non-zero slack variables */
317 SCIP_BENDERS* benders, /**< Benders' decomposition */
318 SCIP_Bool* activeslack /**< flag to indicate whether a slack variable is active */
319 );
320
321/** sets the subproblem type
322 *
323 * The subproblem types are:
324 * - Convex constraints with continuous variables
325 * - Convex constraints with discrete variables
326 * - Non-convex constraints with continuous variables
327 * - Non-convex constraints with discrete variables
328 */
331 SCIP_BENDERS* benders, /**< Benders' decomposition */
332 int probnumber, /**< the subproblem number */
333 SCIP_BENDERSSUBTYPE subprobtype /**< the subproblem type */
334 );
335
336/** returns the type of the subproblem
337 *
338 * This type is used to determine whether the duals of the problem can be used to generate cuts
339 */
342 SCIP_BENDERS* benders, /**< Benders' decomposition */
343 int probnumber /**< the subproblem number */
344 );
345
346/** sets the flag indicating whether a subproblem is convex
347 *
348 * It is possible that this can change during the solving process. One example is when the three-phase method is
349 * employed, where the first phase solves the convex relaxation of both the master and subproblems, the second phase
350 * reintroduces the integrality constraints to the master problem and the third phase then reintroduces integrality
351 * constraints to the subproblems.
352 */
355 SCIP_BENDERS* benders, /**< Benders' decomposition */
356 int probnumber, /**< the subproblem number */
357 SCIP_Bool isconvex /**< flag to indicate whether the subproblem is convex */
358 );
359
360/** returns whether the subproblem is convex
361 *
362 * This means that the dual solution can be used to generate cuts.
363 */
366 SCIP_BENDERS* benders, /**< Benders' decomposition */
367 int probnumber /**< the subproblem number */
368 );
369
370/** returns the number of subproblems that are convex */
373 SCIP_BENDERS* benders /**< Benders' decomposition */
374 );
375
376/** sets the flag indicating whether a subproblem contains non-linear constraints */
379 SCIP_BENDERS* benders, /**< Benders' decomposition */
380 int probnumber, /**< the subproblem number */
381 SCIP_Bool isnonlinear /**< flag to indicate whether the subproblem contains non-linear constraints */
382 );
383
384/** returns whether the subproblem contains non-linear constraints. */
387 SCIP_BENDERS* benders, /**< Benders' decomposition */
388 int probnumber /**< the subproblem number */
389 );
390
391/** returns the number of subproblems that contain non-linear constraints */
394 SCIP_BENDERS* benders /**< Benders' decomposition */
395 );
396
397/** sets the flag indicating whether the master problem contains non-linear constraints */
400 SCIP_BENDERS* benders, /**< Benders' decomposition */
401 SCIP_Bool isnonlinear /**< flag to indicate whether the subproblem contains non-linear constraints */
402 );
403
404/** returns whether the master problem contains non-linear constraints. */
407 SCIP_BENDERS* benders /**< Benders' decomposition */
408 );
409
410/** returns the flag indicating that Benders' decomposition is in a cut strengthening round */
413 SCIP_BENDERS* benders /**< Benders' decomposition */
414 );
415
416/** solves the LP of the Benders' decomposition subproblem
417 *
418 * This requires that the subproblem is in probing mode.
419 */
422 SCIP* scip, /**< the SCIP data structure */
423 SCIP_BENDERS* benders, /**< the Benders' decomposition data structure */
424 int probnumber, /**< the subproblem number */
425 SCIP_STATUS* solvestatus, /**< status of subproblem solve */
426 SCIP_Real* objective /**< optimal value of subproblem, if solved to optimality */
427 );
428
429/** solves the Benders' decomposition subproblem */
432 SCIP* scip, /**< the SCIP data structure */
433 SCIP_BENDERS* benders, /**< the Benders' decomposition data structure */
434 int probnumber, /**< the subproblem number */
435 SCIP_STATUS* solvestatus, /**< status of subproblem solve */
436 SCIP_Bool solvecip /**< directly solve the CIP subproblem */
437 );
438
439/** returns the number of cuts that have been transferred from sub SCIPs to the master SCIP */
442 SCIP_BENDERS* benders /**< the Benders' decomposition data structure */
443 );
444
445/** updates the lower bound for the subproblem. If the lower bound is not greater than the previously stored lowerbound,
446 * then no update occurs.
447 */
450 SCIP_BENDERS* benders, /**< Benders' decomposition */
451 int probnumber, /**< the subproblem number */
452 SCIP_Real lowerbound /**< the lower bound */
453 );
454
455/** returns the stored lower bound for the given subproblem */
458 SCIP_BENDERS* benders, /**< Benders' decomposition */
459 int probnumber /**< the subproblem number */
460 );
461
462/** sets the independent subproblem flag */
465 SCIP_BENDERS* benders, /**< Benders' decomposition */
466 int probnumber, /**< the subproblem number */
467 SCIP_Bool isindep /**< flag to indicate whether the subproblem is independent */
468 );
469
470/** returns whether the subproblem is independent */
473 SCIP_BENDERS* benders, /**< Benders' decomposition */
474 int probnumber /**< the subproblem number */
475 );
476
477/** returns whether the subproblem is enabled, i.e. the subproblem is still solved in the solving loop. */
480 SCIP_BENDERS* benders, /**< Benders' decomposition */
481 int probnumber /**< the subproblem number */
482 );
483
484/** @} */
485
486#ifdef __cplusplus
487}
488#endif
489
490#endif
common defines and data types used in all packages of SCIP
SCIP_Real SCIPbendersGetSetupTime(SCIP_BENDERS *benders)
Definition benders.c:6040
void SCIPbendersSetSubproblemObjval(SCIP_BENDERS *benders, int probnumber, SCIP_Real objval)
Definition benders.c:6182
SCIP_RETCODE SCIPbendersSolSlackVarsActive(SCIP_BENDERS *benders, SCIP_Bool *activeslack)
Definition benders.c:6211
SCIP_Bool SCIPbendersCutRelaxation(SCIP_BENDERS *benders)
Definition benders.c:6102
int SCIPbendersGetNTransferredCuts(SCIP_BENDERS *benders)
Definition benders.c:6701
SCIP_Bool SCIPbendersSubproblemIsConvex(SCIP_BENDERS *benders, int probnumber)
Definition benders.c:6362
int SCIPbendersGetNStrengthenFails(SCIP_BENDERS *benders)
Definition benders.c:6030
SCIP_RETCODE SCIPbendersGetStoredCutOrigData(SCIP_BENDERS *benders, int cutidx, SCIP_VAR ***vars, SCIP_Real **vals, SCIP_Real *lhs, SCIP_Real *rhs, int *nvars, int varssize)
Definition benders.c:6785
void SCIPbendersSetSubproblemIsNonlinear(SCIP_BENDERS *benders, int probnumber, SCIP_Bool isnonlinear)
Definition benders.c:6384
void SCIPbendersSetMasterIsNonlinear(SCIP_BENDERS *benders, SCIP_Bool isnonlinear)
Definition benders.c:6426
void SCIPbendersSetData(SCIP_BENDERS *benders, SCIP_BENDERSDATA *bendersdata)
Definition benders.c:5759
SCIP_Bool SCIPbendersOnlyCheckConvexRelax(SCIP_BENDERS *benders, SCIP_Bool subscipsoff)
Definition benders.c:2988
SCIP_Bool SCIPbendersSubproblemIsNonlinear(SCIP_BENDERS *benders, int probnumber)
Definition benders.c:6404
int SCIPbendersGetPriority(SCIP_BENDERS *benders)
Definition benders.c:5944
SCIP_VAR * SCIPbendersGetAuxiliaryVar(SCIP_BENDERS *benders, int probnumber)
Definition benders.c:6160
SCIP_BENDERSCUT * SCIPfindBenderscut(SCIP_BENDERS *benders, const char *name)
Definition benders.c:6917
const char * SCIPbendersGetDesc(SCIP_BENDERS *benders)
Definition benders.c:5934
int SCIPbendersGetNConvexSubproblems(SCIP_BENDERS *benders)
Definition benders.c:6374
SCIP_BENDERSSUBTYPE SCIPbendersGetSubproblemType(SCIP_BENDERS *benders, int probnumber)
Definition benders.c:6321
SCIP_RETCODE SCIPbendersSolveSubproblemCIP(SCIP *scip, SCIP_BENDERS *benders, int probnumber, SCIP_STATUS *solvestatus, SCIP_Bool solvecip)
Definition benders.c:4938
int SCIPbendersGetNNonlinearSubproblems(SCIP_BENDERS *benders)
Definition benders.c:6416
SCIP_NLPPARAM SCIPbendersGetNLPParam(SCIP_BENDERS *benders)
Definition benders.c:4755
SCIP_Bool SCIPbendersSubproblemIsEnabled(SCIP_BENDERS *benders, int probnumber)
Definition benders.c:6642
int SCIPbendersGetNStrengthenCalls(SCIP_BENDERS *benders)
Definition benders.c:6020
int SCIPbendersGetNStoredCuts(SCIP_BENDERS *benders)
Definition benders.c:6744
SCIP_RETCODE SCIPbendersSolveSubproblemLP(SCIP *scip, SCIP_BENDERS *benders, int probnumber, SCIP_STATUS *solvestatus, SCIP_Real *objective)
Definition benders.c:4768
int SCIPbendersGetNBenderscuts(SCIP_BENDERS *benders)
Definition benders.c:6956
void SCIPbendersSetSubproblemIsConvex(SCIP_BENDERS *benders, int probnumber, SCIP_Bool isconvex)
Definition benders.c:6339
SCIP_Bool SCIPbendersIsActive(SCIP_BENDERS *benders)
Definition benders.c:2675
void SCIPbendersSetSubproblemIsSetup(SCIP_BENDERS *benders, int probnumber, SCIP_Bool issetup)
Definition benders.c:6537
SCIP_BENDERSDATA * SCIPbendersGetData(SCIP_BENDERS *benders)
Definition benders.c:5749
const char * SCIPbendersGetName(SCIP_BENDERS *benders)
Definition benders.c:5924
SCIP_Bool SCIPbendersCutPseudo(SCIP_BENDERS *benders)
Definition benders.c:6092
SCIP_VAR ** SCIPbendersGetAuxiliaryVars(SCIP_BENDERS *benders)
Definition benders.c:6172
int SCIPbendersGetNSubproblems(SCIP_BENDERS *benders)
Definition benders.c:5968
void SCIPbendersSetSubproblemType(SCIP_BENDERS *benders, int probnumber, SCIP_BENDERSSUBTYPE subprobtype)
Definition benders.c:6296
int SCIPbendersGetNStrengthenCutsFound(SCIP_BENDERS *benders)
Definition benders.c:6010
void SCIPbendersUpdateSubproblemLowerbound(SCIP_BENDERS *benders, int probnumber, SCIP_Real lowerbound)
Definition benders.c:6713
SCIP * SCIPbendersSubproblem(SCIP_BENDERS *benders, int probnumber)
Definition benders.c:5978
SCIP_Bool SCIPbendersMasterIsNonlinear(SCIP_BENDERS *benders)
Definition benders.c:6437
SCIP_RETCODE SCIPbendersGetStoredCutData(SCIP_BENDERS *benders, int cutidx, SCIP_VAR ***vars, SCIP_Real **vals, SCIP_Real *lhs, SCIP_Real *rhs, int *nvars)
Definition benders.c:6754
int SCIPbendersGetNCalls(SCIP_BENDERS *benders)
Definition benders.c:5990
SCIP_Bool SCIPbendersIsInitialized(SCIP_BENDERS *benders)
Definition benders.c:6072
int SCIPbendersGetNCutsFound(SCIP_BENDERS *benders)
Definition benders.c:6000
SCIP_Bool SCIPbendersShareAuxVars(SCIP_BENDERS *benders)
Definition benders.c:6112
SCIP_Bool SCIPbendersCutLP(SCIP_BENDERS *benders)
Definition benders.c:6082
SCIP_RETCODE SCIPbendersSetBenderscutPriority(SCIP_BENDERS *benders, SCIP_BENDERSCUT *benderscut, int priority)
Definition benders.c:6966
SCIP_Real SCIPbendersGetTime(SCIP_BENDERS *benders)
Definition benders.c:6050
SCIP_Bool SCIPbendersSubproblemIsIndependent(SCIP_BENDERS *benders, int probnumber)
Definition benders.c:6602
SCIP_BENDERSCUT ** SCIPbendersGetBenderscuts(SCIP_BENDERS *benders)
Definition benders.c:6939
SCIP_Real SCIPbendersGetSubproblemObjval(SCIP_BENDERS *benders, int probnumber)
Definition benders.c:6199
void SCIPbendersSetSubproblemIsIndependent(SCIP_BENDERS *benders, int probnumber, SCIP_Bool isindep)
Definition benders.c:6562
SCIP_Bool SCIPbendersInStrengthenRound(SCIP_BENDERS *benders)
Definition benders.c:6447
SCIP_Bool SCIPbendersSubproblemIsSetup(SCIP_BENDERS *benders, int probnumber)
Definition benders.c:6550
SCIP_Real SCIPbendersGetSubproblemLowerbound(SCIP_BENDERS *benders, int probnumber)
Definition benders.c:6732
SCIP_Real objval
int nvars
static SCIP_VAR ** vars
type definitions for Benders' decomposition methods
enum SCIP_BendersSubType SCIP_BENDERSSUBTYPE
struct SCIP_BendersData SCIP_BENDERSDATA
type definitions for Benders' decomposition cut
type definitions for miscellaneous datastructures
#define SCIP_DECL_SORTPTRCOMP(x)
Definition type_misc.h:188
type definitions for NLP solver interfaces
type definitions for return codes for SCIP methods
enum SCIP_Retcode SCIP_RETCODE
type definitions for SCIP's main datastructure
type definitions for problem statistics
enum SCIP_Status SCIP_STATUS
Definition type_stat.h:67
type definitions for problem variables