Scippy

SCIP

Solving Constraint Integer Programs

struct_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 struct_benders.h
26 * @ingroup INTERNALAPI
27 * @brief data structures required 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_STRUCT_BENDERS_H__
34#define __SCIP_STRUCT_BENDERS_H__
35
36
37#include "scip/def.h"
38#include "scip/type_clock.h"
39#include "scip/type_benders.h"
41
42#ifdef __cplusplus
43extern "C" {
44#endif
45
47{
48 SCIP_VAR** vars; /**< the variables forming the cut */
49 SCIP_Real* vals; /**< the coefficients of the variables in the cut */
50 SCIP_Real lhs; /**< the left hand side of the cut */
51 SCIP_Real rhs; /**< the right hand side of the cut */
52 int nvars; /**< the number of variables in the cut */
53};
55
56/** Benders' decomposition data */
58{
59 char* name; /**< name of Benders' decomposition */
60 char* desc; /**< description of Benders' decomposition */
61 SCIP_DECL_BENDERSCOPY ((*benderscopy)); /**< copy method of Benders' decomposition or NULL if you don't want to copy your plugin into sub-SCIPs */
62 SCIP_DECL_BENDERSFREE ((*bendersfree)); /**< destructor of Benders' decomposition */
63 SCIP_DECL_BENDERSINIT ((*bendersinit)); /**< initialize Benders' decomposition */
64 SCIP_DECL_BENDERSEXIT ((*bendersexit)); /**< deinitialize Benders' decomposition */
65 SCIP_DECL_BENDERSINITPRE((*bendersinitpre));/**< presolving initialization method for Benders' decomposition */
66 SCIP_DECL_BENDERSEXITPRE((*bendersexitpre));/**< presolving deinitialization method for Benders' decomposition */
67 SCIP_DECL_BENDERSINITSOL((*bendersinitsol));/**< solving process initialization method of Benders' decomposition */
68 SCIP_DECL_BENDERSEXITSOL((*bendersexitsol));/**< solving process deinitialization method of Benders' decomposition */
69 SCIP_DECL_BENDERSGETVAR((*bendersgetvar)); /**< returns the corresponding variable from the master or subproblem */
70 SCIP_DECL_BENDERSPRESUBSOLVE((*benderspresubsolve));/**< called prior to the subproblem solving loop */
71 SCIP_DECL_BENDERSCREATESUB((*benderscreatesub));/**< creates the Benders' decomposition subproblems */
72 SCIP_DECL_BENDERSSOLVESUBCONVEX((*benderssolvesubconvex));/**< the solving method for convex Benders' decomposition subproblems */
73 SCIP_DECL_BENDERSSOLVESUB((*benderssolvesub));/**< the solving method for the Benders' decomposition subproblems */
74 SCIP_DECL_BENDERSPOSTSOLVE((*benderspostsolve));/**< called after the subproblems are solved. */
75 SCIP_DECL_BENDERSFREESUB((*bendersfreesub));/**< the freeing method for the Benders' decomposition subproblems */
76 SCIP_DECL_SORTPTRCOMP((*benderssubcomp)); /**< a comparator for defining the solving order of the subproblems */
77 SCIP_BENDERSDATA* bendersdata; /**< Benders' decomposition local data */
78 SCIP_CLOCK* setuptime; /**< time spend for setting up this Benders' decomposition for the next stages */
79 SCIP_CLOCK* bendersclock; /**< Benders' decomposition execution time */
80 int priority; /**< priority of the Benders' decomposition */
81 int ncalls; /**< number of times, this Benders' decomposition was called */
82 int ncutsfound; /**< number of cuts found by the Benders' decomposition */
83 int ntransferred; /**< number of cuts transferred from sub SCIP to the master SCIP */
84 SCIP_Bool active; /**< is the Benders' decomposition active? */
85 SCIP_Bool initialized; /**< is Benders' decomposition initialized? */
86 SCIP_Bool cutlp; /**< should Benders' cuts be generated for LP solutions? */
87 SCIP_Bool cutpseudo; /**< should Benders' cuts be generated for pseudo solutions? */
88 SCIP_Bool cutrelax; /**< should Benders' cuts be generated for relaxation solutions? */
89 SCIP_Bool shareauxvars; /**< should this Benders' share the highest priority Benders' auxiliary vars */
90
91 /* additional Benders' decomposition parameters */
92 SCIP_Bool transfercuts; /**< should Benders' cuts generated in LNS heuristics be transferred to the main SCIP instance? */
93 SCIP_Bool lnscheck; /**< should Benders' decomposition be used in LNS heuristics? */
94 int lnsmaxdepth; /**< maximum depth at which the LNS check is performed */
95 int lnsmaxcalls; /**< maximum number of Benders' decomposition call in LNS heuristics */
96 int lnsmaxcallsroot; /**< maximum number of root node Benders' decomposition call in LNS heuristics */
97 SCIP_Bool cutsasconss; /**< should the transferred cuts be added as constraints? */
98 SCIP_Real subprobfrac; /**< fraction of subproblems that are solved in each iteration */
99 SCIP_Bool updateauxvarbound; /**< should the auxiliary variable lower bound be updated by solving the subproblem? */
100 SCIP_Bool auxvarsimplint; /**< if subproblem objective is integer, then set the auxiliary variables as implint */
101 SCIP_Bool cutcheck; /**< should cuts be generated while checking solutions? */
102 SCIP_Bool threadsafe; /**< has the copy been created requiring thread safety */
103 SCIP_Real solutiontol; /**< storing the tolerance for optimality in Benders' decomposition */
104 int numthreads; /**< the number of threads to use when solving the subproblem */
105 SCIP_Bool execfeasphase; /**< should a feasibility phase be executed during the root node, i.e.
106 adding slack variables to constraints to ensure feasibility */
107 SCIP_Real slackvarcoef; /**< the initial objective coefficient of the slack variables in the subproblem */
108 SCIP_Real maxslackvarcoef; /**< the maximal objective coefficient of the slack variables in the subproblem */
109 SCIP_Bool checkconsconvexity; /**< should the constraints of the subproblems be checked for convexity? */
110 SCIP_NLPPARAM nlpparam; /**< parameters for NLP solves */
111
112 /* information for heuristics */
113 SCIP* sourcescip; /**< the source scip from when the Benders' was copied */
114 SCIP_Bool iscopy; /**< is the Benders' decomposition struct a copy */
115 SCIP_HASHMAP* mastervarsmap; /**< hash map for the master variables from the subscip to the master */
116
117 /* the subproblem information */
118 SCIP** subproblems; /**< the Benders' decomposition subproblems */
119 SCIP_VAR** auxiliaryvars; /**< the auxiliary variables for the Benders' optimality cuts */
120 SCIP_PQUEUE* subprobqueue; /**< the priority queue for the subproblems */
121 SCIP_SUBPROBLEMSOLVESTAT** solvestat; /**< storing the solving statistics of all the subproblems */
122 SCIP_Real* subprobobjval; /**< the objective value of the subproblem in the current iteration */
123 SCIP_Real* bestsubprobobjval; /**< the best objective value of the subproblem */
124 SCIP_Real* subproblowerbound; /**< a lower bound on the subproblem - used for the integer cuts */
125 int naddedsubprobs; /**< subproblems added to the Benders' decomposition data */
126 int nsubproblems; /**< number of subproblems */
127 SCIP_BENDERSSUBTYPE* subprobtype; /**< the convexity type of the subproblem */
128 SCIP_Bool* subprobisconvex; /**< is the subproblem convex? This implies that the dual sol can be used for cuts */
129 SCIP_Bool* subprobisnonlinear; /**< does the subproblem contain non-linear constraints */
130 int nconvexsubprobs; /**< the number of subproblems that are convex */
131 int nnonlinearsubprobs; /**< the number of subproblems that are non-linear */
132 SCIP_Bool subprobscreated; /**< have the subproblems been created for this Benders' decomposition.
133 This flag is used when retransforming the problem.*/
134 SCIP_Bool* mastervarscont; /**< flag to indicate that the master problem variable have been converted
135 to continuous variables. */
136 SCIP_Bool* subprobsetup; /**< flag to indicate whether the subproblem has been set up. */
137 SCIP_Bool* indepsubprob; /**< flag to indicate if a subproblem is independent of the master prob */
138 SCIP_Bool* subprobenabled; /**< flag to indicate whether the subproblem is enabled */
139 int nactivesubprobs; /**< the number of active subproblems */
140 SCIP_Bool freesubprobs; /**< do the subproblems need to be freed by the Benders' decomposition core? */
141 SCIP_Bool masterisnonlinear; /**< flag to indicate whether the master problem contains non-linear constraints */
142
143 /* cut strengthening details */
144 SCIP_SOL* corepoint; /**< the point that is separated for stabilisation */
145 SCIP_SOL* initcorepoint; /**< the point that was used to initialise the core point */
146 SCIP_Real convexmult; /**< the multiplier for the convex comb of the LP and sepa point */
147 SCIP_Real perturbeps; /**< epsilon value to perturb the LP solution */
148 int noimprovecount; /**< count of the iterations without improvement */
149 int noimprovelimit; /**< limit used to change behaviour of stabilitation */
150 SCIP_NODE* prevnode; /**< the previous node where the cut strengthening was performed */
151 SCIP_Longint prevnlpiter; /**< number of LP iters at the previous call of the cut strengthening */
152 SCIP_Real prevlowerbound; /**< the lowerbound from the previous LP enforcement iteration */
153 SCIP_Bool strengthenenabled; /**< is the core point cut strengthening enabled */
154 char strengthenintpoint; /**< where should the strengthening interior point be sourced from ('l'p relaxation, 'f'irst solution, 'i'ncumbent solution, 'r'elative interior point, vector of 'o'nes, vector of 'z'eros) */
155 SCIP_Bool strengthenround; /**< flag to indicate whether a cut strengthening round is being performed */
156 int nstrengthencuts; /**< the number of strengthened cuts found */
157 int nstrengthencalls; /**< the number of calls to the strengthening round */
158 int nstrengthenfails; /**< the number of calls to the strengthening round that fail to find cuts */
159
160 /* solving process information */
161 int npseudosols; /**< the number of pseudo solutions checked since the last generated cut */
162 SCIP_Bool feasibilityphase; /**< is the Benders' decomposition in a feasibility phase, i.e. using slack variables */
163
164 /* Bender's cut information */
165 SCIP_BENDERSCUT** benderscuts; /**< the available Benders' cut algorithms */
166 int nbenderscuts; /**< the number of Benders' cut algorithms */
167 int benderscutssize; /**< the size of the Benders' cuts algorithms array */
168 SCIP_Bool benderscutssorted; /**< are the Benders' cuts algorithms sorted by priority */
169 SCIP_Bool benderscutsnamessorted;/**< are the Benders' cuts algorithms sorted by name */
170
171 /* cut storage information */
172 SCIP_BENDERSCUTCUT** storedcuts; /**< array to store the data required to form a cut/constraint */
173 int storedcutssize; /**< the size of the added cuts array */
174 int nstoredcuts; /**< the number of the added cuts */
175};
176
177/** statistics for solving the subproblems. Used for prioritising the solving of the subproblem */
179{
180 int idx; /**< the index of the subproblem */
181 int ncalls; /**< the number of times this subproblems has been solved */
182 SCIP_Real avgiter; /**< the average number of LP/NLP iterations performed */
183};
184
185/** parameters that are set to solve the subproblem. This will be changed from what the user inputs, so they are stored
186 * and reset after the solving loop. */
188{
202};
204
205#ifdef __cplusplus
206}
207#endif
208
209#endif
common defines and data types used in all packages of SCIP
#define SCIP_Longint
Definition: def.h:158
#define SCIP_Bool
Definition: def.h:91
#define SCIP_Real
Definition: def.h:173
SCIP_DECL_BENDERSCREATESUB((*benderscreatesub))
SCIP_NLPPARAM nlpparam
SCIP_Bool * subprobisconvex
SCIP ** subproblems
SCIP_Bool * subprobenabled
SCIP_Bool transfercuts
SCIP_BENDERSDATA * bendersdata
SCIP_Bool threadsafe
SCIP_DECL_BENDERSGETVAR((*bendersgetvar))
SCIP_DECL_BENDERSEXITSOL((*bendersexitsol))
SCIP_DECL_BENDERSSOLVESUB((*benderssolvesub))
SCIP_SUBPROBLEMSOLVESTAT ** solvestat
SCIP_Real slackvarcoef
SCIP_Bool cutlp
SCIP_DECL_BENDERSINIT((*bendersinit))
SCIP_Bool lnscheck
SCIP_Bool strengthenround
SCIP_Bool cutpseudo
SCIP_DECL_BENDERSINITPRE((*bendersinitpre))
SCIP_Bool freesubprobs
SCIP_Bool * mastervarscont
SCIP_VAR ** auxiliaryvars
SCIP_Real prevlowerbound
SCIP_Bool * subprobsetup
SCIP_Real * subprobobjval
SCIP_Bool active
SCIP_HASHMAP * mastervarsmap
SCIP_Real perturbeps
SCIP_PQUEUE * subprobqueue
SCIP_Bool execfeasphase
SCIP_Real * bestsubprobobjval
SCIP_Bool benderscutssorted
SCIP_Real maxslackvarcoef
SCIP_Bool initialized
SCIP_Bool cutsasconss
SCIP_BENDERSSUBTYPE * subprobtype
SCIP_Real convexmult
SCIP_Bool shareauxvars
SCIP_Longint prevnlpiter
SCIP_DECL_BENDERSFREESUB((*bendersfreesub))
SCIP_DECL_BENDERSPRESUBSOLVE((*benderspresubsolve))
SCIP_Bool * subprobisnonlinear
SCIP_DECL_BENDERSCOPY((*benderscopy))
SCIP_Bool * indepsubprob
SCIP_Bool cutcheck
SCIP_Bool strengthenenabled
SCIP_DECL_SORTPTRCOMP((*benderssubcomp))
SCIP_Bool iscopy
SCIP_DECL_BENDERSEXIT((*bendersexit))
SCIP_Bool benderscutsnamessorted
char strengthenintpoint
SCIP_DECL_BENDERSPOSTSOLVE((*benderspostsolve))
SCIP_Bool masterisnonlinear
SCIP_DECL_BENDERSEXITPRE((*bendersexitpre))
SCIP_BENDERSCUTCUT ** storedcuts
SCIP_Real subprobfrac
SCIP_Bool feasibilityphase
SCIP_BENDERSCUT ** benderscuts
SCIP_CLOCK * setuptime
SCIP_CLOCK * bendersclock
SCIP_Bool cutrelax
SCIP_Bool subprobscreated
SCIP_Bool updateauxvarbound
SCIP_SOL * corepoint
SCIP_Bool checkconsconvexity
SCIP_SOL * initcorepoint
SCIP_NODE * prevnode
SCIP_Bool auxvarsimplint
SCIP_DECL_BENDERSFREE((*bendersfree))
SCIP_Real solutiontol
SCIP_DECL_BENDERSINITSOL((*bendersinitsol))
SCIP_DECL_BENDERSSOLVESUBCONVEX((*benderssolvesubconvex))
SCIP_Real * subproblowerbound
type definitions for Benders' decomposition methods
enum SCIP_BendersSubType SCIP_BENDERSSUBTYPE
Definition: type_benders.h:79
struct SCIP_BendersData SCIP_BENDERSDATA
Definition: type_benders.h:82
type definitions for Benders' decomposition cut
type definitions for clocks and timing issues