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-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 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
45#ifdef __cplusplus
46extern "C" {
47#endif
48
49/**@addtogroup PublicBendersMethods
50 *
51 * @{
52 */
53
54/** compares two benderss w. r. to their priority */
57
58/** comparison method for sorting benderss w.r.t. to their name */
61
62/** gets user data of Benders' decomposition */
65 SCIP_BENDERS* benders /**< Benders' decomposition */
66 );
67
68/** sets user data of Benders' decomposition; user has to free old data in advance! */
71 SCIP_BENDERS* benders, /**< Benders' decomposition */
72 SCIP_BENDERSDATA* bendersdata /**< new Benders' decomposition user data */
73 );
74
75/** gets name of Benders' decomposition */
77const char* SCIPbendersGetName(
78 SCIP_BENDERS* benders /**< Benders' decomposition */
79 );
80
81/** gets description of Benders' decomposition */
83const char* SCIPbendersGetDesc(
84 SCIP_BENDERS* benders /**< Benders' decomposition */
85 );
86
87/** gets priority of Benders' decomposition */
90 SCIP_BENDERS* benders /**< Benders' decomposition */
91 );
92
93/** gets the number of subproblems for the Benders' decomposition */
96 SCIP_BENDERS* benders /**< the Benders' decomposition data structure */
97 );
98
99/** returns the SCIP instance for a given subproblem */
102 SCIP_BENDERS* benders, /**< the Benders' decomposition data structure */
103 int probnumber /**< the subproblem number */
104 );
105
106/** gets the number of times, the Bender' decomposition was called and tried to find a violated second stage constraint */
109 SCIP_BENDERS* benders /**< Benders' decomposition */
110 );
111
112/** gets the number of optimality cuts found by the collection of Benders' decomposition subproblems */
115 SCIP_BENDERS* benders /**< Benders' decomposition */
116 );
117
118/** gets the number of cuts found from the strengthening round */
121 SCIP_BENDERS* benders /**< Benders' decomposition */
122 );
123
124/** gets the number of calls to the strengthening round */
127 SCIP_BENDERS* benders /**< Benders' decomposition */
128 );
129
130/** gets the number of calls to the strengthening round that fail */
133 SCIP_BENDERS* benders /**< Benders' decomposition */
134 );
135
136/** gets time in seconds used in this Benders' decomposition for setting up for next stages */
139 SCIP_BENDERS* benders /**< Benders' decomposition */
140 );
141
142/** gets execution time in seconds used in this Benders' decomposition */
144SCIP_Real SCIPbendersGetTime(
145 SCIP_BENDERS* benders /**< Benders' decomposition */
146 );
147
148/** Is Benders' decomposition initialized? */
151 SCIP_BENDERS* benders /**< Benders' decomposition */
152 );
153
154/** returns whether the given Benders' decomposition is in use in the current problem */
156SCIP_Bool SCIPbendersIsActive(
157 SCIP_BENDERS* benders /**< the Benders' decomposition structure */
158 );
159
160/** Returns whether only the convex relaxations will be checked in this solve loop
161 * when Benders' is used in the LNS heuristics, only the convex relaxations of the master/subproblems are checked,
162 * i.e. no integer cuts are generated. In this case, then Benders' decomposition is performed under the assumption
163 * that all subproblems are convex relaxations.
164 */
167 SCIP_BENDERS* benders, /**< Benders' decomposition */
168 SCIP_Bool subscipsoff /**< flag indicating whether plugins using sub-SCIPs are deactivated */
169 );
170
171/** Are Benders' cuts generated from the LP solutions? */
173SCIP_Bool SCIPbendersCutLP(
174 SCIP_BENDERS* benders /**< Benders' decomposition */
175 );
176
177/** Are Benders' cuts generated from the pseudo solutions? */
179SCIP_Bool SCIPbendersCutPseudo(
180 SCIP_BENDERS* benders /**< Benders' decomposition */
181 );
182
183/** Are Benders' cuts generated from the relaxation solutions? */
186 SCIP_BENDERS* benders /**< Benders' decomposition */
187 );
188
189/** Should this Benders' use the auxiliary variables from the highest priority Benders'? */
192 SCIP_BENDERS* benders /**< Benders' decomposition */
193 );
194
195/** sets the subproblem setup flag */
198 SCIP_BENDERS* benders, /**< Benders' decomposition */
199 int probnumber, /**< the subproblem number */
200 SCIP_Bool issetup /**< flag to indicate whether the subproblem has been setup */
201 );
202
203/** returns the subproblem setup flag */
206 SCIP_BENDERS* benders, /**< Benders' decomposition */
207 int probnumber /**< the subproblem number */
208 );
209
210/** returns the auxiliary variable for the given subproblem */
213 SCIP_BENDERS* benders, /**< Benders' decomposition */
214 int probnumber /**< the subproblem number */
215 );
216
217/** returns all auxiliary variables */
220 SCIP_BENDERS* benders /**< Benders' decomposition */
221 );
222
223/** stores the objective function value of the subproblem for use in cut generation */
226 SCIP_BENDERS* benders, /**< Benders' decomposition */
227 int probnumber, /**< the subproblem number */
228 SCIP_Real objval /**< the objective function value for the subproblem */
229 );
230
231/** returns the objective function value of the subproblem for use in cut generation */
234 SCIP_BENDERS* benders, /**< Benders' decomposition */
235 int probnumber /**< the subproblem number */
236 );
237
238/** returns the number of cuts that have been added for storage */
241 SCIP_BENDERS* benders /**< Benders' decomposition cut */
242 );
243
244/** returns the data for the cuts that have been added by the Benders' cut plugin */
247 SCIP_BENDERS* benders, /**< Benders' decomposition cut */
248 int cutidx, /**< the index for the cut data that is requested */
249 SCIP_VAR*** vars, /**< the variables that have non-zero coefficients in the cut */
250 SCIP_Real** vals, /**< the coefficients of the variables in the cut */
251 SCIP_Real* lhs, /**< the left hand side of the cut */
252 SCIP_Real* rhs, /**< the right hand side of the cut */
253 int* nvars /**< the number of variables with non-zero coefficients in the cut */
254 );
255
256/** returns the original problem data for the cuts that have been added by the Benders' cut plugin. The stored
257 * variables and values will populate the input vars and vals arrays. Thus, memory must be allocated for the vars and
258 * vals arrays
259 */
262 SCIP_BENDERS* benders, /**< Benders' decomposition cut */
263 int cutidx, /**< the index for the cut data that is requested */
264 SCIP_VAR*** vars, /**< the variables that have non-zero coefficients in the cut */
265 SCIP_Real** vals, /**< the coefficients of the variables in the cut */
266 SCIP_Real* lhs, /**< the left hand side of the cut */
267 SCIP_Real* rhs, /**< the right hand side of the cut */
268 int* nvars, /**< the number of variables with non-zero coefficients in the cut */
269 int varssize /**< the available slots in the array */
270 );
271
272/*
273 * Public functions associated with Benders' cuts
274 */
275
276/** returns the Benders' cut of the given name, or NULL if not existing */
279 SCIP_BENDERS* benders, /**< Benders' decomposition */
280 const char* name /**< name of Benderscut' decomposition */
281 );
282
283
284/** returns the array of currently available Benders' cuts; active Benders' decomposition are in the first slots of
285 * the array
286 */
289 SCIP_BENDERS* benders /**< Benders' decomposition */
290 );
291
292
293/** returns the number of currently available Benders' cuts */
296 SCIP_BENDERS* benders /**< Benders' decomposition */
297 );
298
299/** sets the priority of a Benders' decomposition */
302 SCIP_BENDERS* benders, /**< Benders' decomposition */
303 SCIP_BENDERSCUT* benderscut, /**< Benders' cut */
304 int priority /**< new priority of the Benders' decomposition */
305 );
306
307/** returns whether the solution has non-zero slack variables */
310 SCIP_BENDERS* benders, /**< Benders' decomposition */
311 SCIP_Bool* activeslack /**< flag to indicate whether a slack variable is active */
312 );
313
314/** sets the subproblem type
315 *
316 * The subproblem types are:
317 * - Convex constraints with continuous variables
318 * - Convex constraints with discrete variables
319 * - Non-convex constraints with continuous variables
320 * - Non-convex constraints with discrete variables
321 */
324 SCIP_BENDERS* benders, /**< Benders' decomposition */
325 int probnumber, /**< the subproblem number */
326 SCIP_BENDERSSUBTYPE subprobtype /**< the subproblem type */
327 );
328
329/** returns the type of the subproblem
330 *
331 * This type is used to determine whether the duals of the problem can be used to generate cuts
332 */
335 SCIP_BENDERS* benders, /**< Benders' decomposition */
336 int probnumber /**< the subproblem number */
337 );
338
339/** sets the flag indicating whether a subproblem is convex
340 *
341 * It is possible that this can change during the solving process. One example is when the three-phase method is
342 * employed, where the first phase solves the convex relaxation of both the master and subproblems, the second phase
343 * reintroduces the integrality constraints to the master problem and the third phase then reintroduces integrality
344 * constraints to the subproblems.
345 */
348 SCIP_BENDERS* benders, /**< Benders' decomposition */
349 int probnumber, /**< the subproblem number */
350 SCIP_Bool isconvex /**< flag to indicate whether the subproblem is convex */
351 );
352
353/** returns whether the subproblem is convex
354 *
355 * This means that the dual solution can be used to generate cuts.
356 */
359 SCIP_BENDERS* benders, /**< Benders' decomposition */
360 int probnumber /**< the subproblem number */
361 );
362
363/** returns the number of subproblems that are convex */
366 SCIP_BENDERS* benders /**< Benders' decomposition */
367 );
368
369/** sets the flag indicating whether a subproblem contains non-linear constraints */
372 SCIP_BENDERS* benders, /**< Benders' decomposition */
373 int probnumber, /**< the subproblem number */
374 SCIP_Bool isnonlinear /**< flag to indicate whether the subproblem contains non-linear constraints */
375 );
376
377/** returns whether the subproblem contains non-linear constraints. */
380 SCIP_BENDERS* benders, /**< Benders' decomposition */
381 int probnumber /**< the subproblem number */
382 );
383
384/** returns the number of subproblems that contain non-linear constraints */
387 SCIP_BENDERS* benders /**< Benders' decomposition */
388 );
389
390/** sets the flag indicating whether the master problem contains non-linear constraints */
393 SCIP_BENDERS* benders, /**< Benders' decomposition */
394 SCIP_Bool isnonlinear /**< flag to indicate whether the subproblem contains non-linear constraints */
395 );
396
397/** returns whether the master problem contains non-linear constraints. */
400 SCIP_BENDERS* benders /**< Benders' decomposition */
401 );
402
403/** returns the flag indicating that Benders' decomposition is in a cut strengthening round */
406 SCIP_BENDERS* benders /**< Benders' decomposition */
407 );
408
409/** solves the LP of the Benders' decomposition subproblem
410 *
411 * This requires that the subproblem is in probing mode.
412 */
415 SCIP* scip, /**< the SCIP data structure */
416 SCIP_BENDERS* benders, /**< the Benders' decomposition data structure */
417 int probnumber, /**< the subproblem number */
418 SCIP_STATUS* solvestatus, /**< status of subproblem solve */
419 SCIP_Real* objective /**< optimal value of subproblem, if solved to optimality */
420 );
421
422/** solves the Benders' decomposition subproblem */
425 SCIP* scip, /**< the SCIP data structure */
426 SCIP_BENDERS* benders, /**< the Benders' decomposition data structure */
427 int probnumber, /**< the subproblem number */
428 SCIP_STATUS* solvestatus, /**< status of subproblem solve */
429 SCIP_Bool solvecip /**< directly solve the CIP subproblem */
430 );
431
432/** returns the number of cuts that have been transferred from sub SCIPs to the master SCIP */
435 SCIP_BENDERS* benders /**< the Benders' decomposition data structure */
436 );
437
438/** updates the lower bound for the subproblem. If the lower bound is not greater than the previously stored lowerbound,
439 * then no update occurs.
440 */
443 SCIP_BENDERS* benders, /**< Benders' decomposition */
444 int probnumber, /**< the subproblem number */
445 SCIP_Real lowerbound /**< the lower bound */
446 );
447
448/** returns the stored lower bound for the given subproblem */
451 SCIP_BENDERS* benders, /**< Benders' decomposition */
452 int probnumber /**< the subproblem number */
453 );
454
455/** sets the independent subproblem flag */
458 SCIP_BENDERS* benders, /**< Benders' decomposition */
459 int probnumber, /**< the subproblem number */
460 SCIP_Bool isindep /**< flag to indicate whether the subproblem is independent */
461 );
462
463/** returns whether the subproblem is independent */
466 SCIP_BENDERS* benders, /**< Benders' decomposition */
467 int probnumber /**< the subproblem number */
468 );
469
470/** returns whether the subproblem is enabled, i.e. the subproblem is still solved in the solving loop. */
473 SCIP_BENDERS* benders, /**< Benders' decomposition */
474 int probnumber /**< the subproblem number */
475 );
476
477/** @} */
478
479#ifdef __cplusplus
480}
481#endif
482
483#endif
common defines and data types used in all packages of SCIP
SCIP_Real SCIPbendersGetSetupTime(SCIP_BENDERS *benders)
Definition benders.c:6018
void SCIPbendersSetSubproblemObjval(SCIP_BENDERS *benders, int probnumber, SCIP_Real objval)
Definition benders.c:6160
SCIP_RETCODE SCIPbendersSolSlackVarsActive(SCIP_BENDERS *benders, SCIP_Bool *activeslack)
Definition benders.c:6189
SCIP_Bool SCIPbendersCutRelaxation(SCIP_BENDERS *benders)
Definition benders.c:6080
int SCIPbendersGetNTransferredCuts(SCIP_BENDERS *benders)
Definition benders.c:6679
SCIP_Bool SCIPbendersSubproblemIsConvex(SCIP_BENDERS *benders, int probnumber)
Definition benders.c:6340
int SCIPbendersGetNStrengthenFails(SCIP_BENDERS *benders)
Definition benders.c:6008
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:6763
void SCIPbendersSetSubproblemIsNonlinear(SCIP_BENDERS *benders, int probnumber, SCIP_Bool isnonlinear)
Definition benders.c:6362
void SCIPbendersSetMasterIsNonlinear(SCIP_BENDERS *benders, SCIP_Bool isnonlinear)
Definition benders.c:6404
void SCIPbendersSetData(SCIP_BENDERS *benders, SCIP_BENDERSDATA *bendersdata)
Definition benders.c:5737
SCIP_Bool SCIPbendersOnlyCheckConvexRelax(SCIP_BENDERS *benders, SCIP_Bool subscipsoff)
Definition benders.c:2981
SCIP_Bool SCIPbendersSubproblemIsNonlinear(SCIP_BENDERS *benders, int probnumber)
Definition benders.c:6382
int SCIPbendersGetPriority(SCIP_BENDERS *benders)
Definition benders.c:5922
SCIP_VAR * SCIPbendersGetAuxiliaryVar(SCIP_BENDERS *benders, int probnumber)
Definition benders.c:6138
SCIP_BENDERSCUT * SCIPfindBenderscut(SCIP_BENDERS *benders, const char *name)
Definition benders.c:6895
const char * SCIPbendersGetDesc(SCIP_BENDERS *benders)
Definition benders.c:5912
int SCIPbendersGetNConvexSubproblems(SCIP_BENDERS *benders)
Definition benders.c:6352
SCIP_BENDERSSUBTYPE SCIPbendersGetSubproblemType(SCIP_BENDERS *benders, int probnumber)
Definition benders.c:6299
SCIP_RETCODE SCIPbendersSolveSubproblemCIP(SCIP *scip, SCIP_BENDERS *benders, int probnumber, SCIP_STATUS *solvestatus, SCIP_Bool solvecip)
Definition benders.c:4915
int SCIPbendersGetNNonlinearSubproblems(SCIP_BENDERS *benders)
Definition benders.c:6394
SCIP_Bool SCIPbendersSubproblemIsEnabled(SCIP_BENDERS *benders, int probnumber)
Definition benders.c:6620
int SCIPbendersGetNStrengthenCalls(SCIP_BENDERS *benders)
Definition benders.c:5998
int SCIPbendersGetNStoredCuts(SCIP_BENDERS *benders)
Definition benders.c:6722
SCIP_RETCODE SCIPbendersSolveSubproblemLP(SCIP *scip, SCIP_BENDERS *benders, int probnumber, SCIP_STATUS *solvestatus, SCIP_Real *objective)
Definition benders.c:4751
int SCIPbendersGetNBenderscuts(SCIP_BENDERS *benders)
Definition benders.c:6934
void SCIPbendersSetSubproblemIsConvex(SCIP_BENDERS *benders, int probnumber, SCIP_Bool isconvex)
Definition benders.c:6317
SCIP_Bool SCIPbendersIsActive(SCIP_BENDERS *benders)
Definition benders.c:2668
void SCIPbendersSetSubproblemIsSetup(SCIP_BENDERS *benders, int probnumber, SCIP_Bool issetup)
Definition benders.c:6515
SCIP_BENDERSDATA * SCIPbendersGetData(SCIP_BENDERS *benders)
Definition benders.c:5727
const char * SCIPbendersGetName(SCIP_BENDERS *benders)
Definition benders.c:5902
SCIP_Bool SCIPbendersCutPseudo(SCIP_BENDERS *benders)
Definition benders.c:6070
SCIP_VAR ** SCIPbendersGetAuxiliaryVars(SCIP_BENDERS *benders)
Definition benders.c:6150
int SCIPbendersGetNSubproblems(SCIP_BENDERS *benders)
Definition benders.c:5946
void SCIPbendersSetSubproblemType(SCIP_BENDERS *benders, int probnumber, SCIP_BENDERSSUBTYPE subprobtype)
Definition benders.c:6274
int SCIPbendersGetNStrengthenCutsFound(SCIP_BENDERS *benders)
Definition benders.c:5988
void SCIPbendersUpdateSubproblemLowerbound(SCIP_BENDERS *benders, int probnumber, SCIP_Real lowerbound)
Definition benders.c:6691
SCIP * SCIPbendersSubproblem(SCIP_BENDERS *benders, int probnumber)
Definition benders.c:5956
SCIP_Bool SCIPbendersMasterIsNonlinear(SCIP_BENDERS *benders)
Definition benders.c:6415
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:6732
int SCIPbendersGetNCalls(SCIP_BENDERS *benders)
Definition benders.c:5968
SCIP_Bool SCIPbendersIsInitialized(SCIP_BENDERS *benders)
Definition benders.c:6050
int SCIPbendersGetNCutsFound(SCIP_BENDERS *benders)
Definition benders.c:5978
SCIP_Bool SCIPbendersShareAuxVars(SCIP_BENDERS *benders)
Definition benders.c:6090
SCIP_Bool SCIPbendersCutLP(SCIP_BENDERS *benders)
Definition benders.c:6060
SCIP_RETCODE SCIPbendersSetBenderscutPriority(SCIP_BENDERS *benders, SCIP_BENDERSCUT *benderscut, int priority)
Definition benders.c:6944
SCIP_Real SCIPbendersGetTime(SCIP_BENDERS *benders)
Definition benders.c:6028
SCIP_Bool SCIPbendersSubproblemIsIndependent(SCIP_BENDERS *benders, int probnumber)
Definition benders.c:6580
SCIP_BENDERSCUT ** SCIPbendersGetBenderscuts(SCIP_BENDERS *benders)
Definition benders.c:6917
SCIP_Real SCIPbendersGetSubproblemObjval(SCIP_BENDERS *benders, int probnumber)
Definition benders.c:6177
void SCIPbendersSetSubproblemIsIndependent(SCIP_BENDERS *benders, int probnumber, SCIP_Bool isindep)
Definition benders.c:6540
SCIP_Bool SCIPbendersInStrengthenRound(SCIP_BENDERS *benders)
Definition benders.c:6425
SCIP_Bool SCIPbendersSubproblemIsSetup(SCIP_BENDERS *benders, int probnumber)
Definition benders.c:6528
SCIP_Real SCIPbendersGetSubproblemLowerbound(SCIP_BENDERS *benders, int probnumber)
Definition benders.c:6710
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 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