Scippy

SCIP

Solving Constraint Integer Programs

cons_benderslp.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 2002-2022 Zuse Institute Berlin */
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 cons_benderslp.c
26  * @ingroup DEFPLUGINS_CONS
27  * @brief constraint handler for benderslp decomposition
28  * @author Stephen J. Maher
29  *
30  * Two constraint handlers are implemented for the generation of Benders' decomposition cuts. When included in a
31  * problem, the Benders' decomposition constraint handlers generate cuts during the enforcement of LP and relaxation
32  * solutions. Additionally, Benders' decomposition cuts can be generated when checking the feasibility of solutions with
33  * respect to the subproblem constraints.
34  *
35  * This constraint handler has an enforcement priority that is greater than the integer constraint handler. This means
36  * that all LP solutions will be first checked for feasibility with respect to the Benders' decomposition second stage
37  * constraints before performing an integrality check. This is part of a multi-phase approach for solving mixed integer
38  * programs by Benders' decomposition.
39  *
40  * A parameter is available to control the depth at which the non-integer LP solution are enforced by solving the
41  * Benders' decomposition subproblems. This parameter is set to 0 by default, indicating that non-integer LP solutions
42  * are enforced only at the root node.
43  */
44 
45 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
46 
47 #include <assert.h>
48 
49 #include "scip/scip.h"
50 #include "scip/cons_benderslp.h"
51 #include "scip/cons_benders.h"
52 
53 
54 /* fundamental constraint handler properties */
55 #define CONSHDLR_NAME "benderslp"
56 #define CONSHDLR_DESC "constraint handler for Benders' Decomposition to separate LP solutions"
57 #define CONSHDLR_ENFOPRIORITY 10000000 /**< priority of the constraint handler for constraint enforcing */
58 #define CONSHDLR_CHECKPRIORITY 10000000 /**< priority of the constraint handler for checking feasibility */
59 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
60  * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
61 #define CONSHDLR_NEEDSCONS FALSE /**< should the constraint handler be skipped, if no constraints are available? */
62 
63 
64 #define DEFAULT_CONSBENDERSLP_MAXDEPTH 0/**< depth at which Benders' decomposition cuts are generated from the LP
65  * solution (-1: always, 0: only at root) */
66 #define DEFAULT_CONSBENDERSLP_FREQ 0/**< the depth frequency for generating LP cuts after the max depth is reached (0: never, 1: all nodes, ...) */
67 #define DEFAULT_CONSBENDERSLP_STALLLIMIT 100/**< the number of nodes processed without a dual bound improvement before enforcing the LP relaxation, 0: no stall count applied */
68 #define DEFAULT_CONSBENDERSLP_ITERLIMIT 100 /**< after the root node, only iterlimit fractional LP solutions are used at each node to generate Benders' decomposition cuts. */
69 #define DEFAULT_ACTIVE FALSE /**< is the constraint handler active? */
70 
71 /*
72  * Data structures
73  */
74 
75 /** constraint handler data */
76 struct SCIP_ConshdlrData
77 {
78  /* parameters for controlling the two-phase method for Benders' decomposition */
79  int maxdepth; /**< the maximum depth at which Benders' cuts are generated from the LP */
80  int freq; /**< the depth frequency of generating LP cuts after the max depth is reached */
81  SCIP_Bool active; /**< is the constraint handler active? */
82 
83  /* variable used to control the behaviour of the two-phase method for Benders' decomposition */
84  SCIP_Longint ncallsnode; /**< the number of calls at the current node */
85  SCIP_NODE* currnode; /**< the current node */
86  SCIP_Real prevbound; /**< the previous dual bound */
87  int iterlimit; /**< the iteration limit for the first phase of the two-phase method at a node lower than the root. */
88  int stallcount; /**< the number of nodes processed since the last lower bound increase */
89  int stalllimit; /**< the number of nodes processed without bound improvement before enforcing the LP relaxation */
90 };
91 
92 
93 /*
94  * Local methods
95  */
96 
97 
98 /*
99  * Callback methods of constraint handler
100  */
101 
102 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
103 static
104 SCIP_DECL_CONSHDLRCOPY(conshdlrCopyBenderslp)
105 { /*lint --e{715}*/
106  assert(scip != NULL);
107 
109 
110  *valid = TRUE;
111 
112  return SCIP_OKAY;
113 }
114 
115 
116 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
117 static
118 SCIP_DECL_CONSFREE(consFreeBenderslp)
119 { /*lint --e{715}*/
120  SCIP_CONSHDLRDATA* conshdlrdata;
121 
122  assert(scip != NULL);
123  assert(conshdlr != NULL);
124 
125  conshdlrdata = SCIPconshdlrGetData(conshdlr);
126  assert(conshdlrdata != NULL);
127 
128  /* freeing the constraint handler data */
129  SCIPfreeMemory(scip, &conshdlrdata);
130 
131  return SCIP_OKAY;
132 }
133 
134 
135 
136 /** constraint enforcing method of constraint handler for LP solutions */
137 static
138 SCIP_DECL_CONSENFOLP(consEnfolpBenderslp)
139 { /*lint --e{715}*/
140  SCIP_CONSHDLRDATA* conshdlrdata;
141 
142  assert(conshdlr != NULL);
143 
144  conshdlrdata = SCIPconshdlrGetData(conshdlr);
145 
146  /* updating the stall count. If the bound has improved since the last call, then the stall count is set to zero */
147  conshdlrdata->stallcount++;
148  if( SCIPisLT(scip, conshdlrdata->prevbound, SCIPgetLowerbound(scip)) )
149  conshdlrdata->stallcount = 0;
150 
151  conshdlrdata->prevbound = SCIPgetLowerbound(scip);
152  conshdlrdata->ncallsnode++;
153 
154  /* if a new node is being processed, then the iteration counts are reset. */
155  if( conshdlrdata->currnode != SCIPgetCurrentNode(scip) )
156  {
157  conshdlrdata->currnode = SCIPgetCurrentNode(scip);
158  conshdlrdata->ncallsnode = 0;
159  }
160 
161  /* the result is initially set to FEASIBLE. If the two-phase method is not executed, then the result will remain as
162  * FEASIBLE. The actual feasibility of the Benders' decomposition subproblems is checked in cons_benders.
163  */
164  (*result) = SCIP_FEASIBLE;
165 
166  /* only check the Benders' decomposition subproblems for fractional LP solutions if the two-phase method is activated */
167  if( !conshdlrdata->active )
168  return SCIP_OKAY;
169 
170  /* checking whether the two-phase method is performed.
171  * - If a maxdepth is specified
172  * - current depth is checked
173  * - the frequency is checked, if a frequency is specified
174  * - the stalllimit is checked if a stalllimit is specified.
175  */
176  if( conshdlrdata->maxdepth >= 0 && SCIPgetDepth(scip) > conshdlrdata->maxdepth
177  && (conshdlrdata->freq == 0 || SCIPgetDepth(scip) % conshdlrdata->freq != 0)
178  && (conshdlrdata->stalllimit == 0 || conshdlrdata->stallcount < conshdlrdata->stalllimit) )
179  return SCIP_OKAY;
180 
181  /* if an iteration limit is specified, then this is imposed at nodes after the root node */
182  if( SCIPgetDepth(scip) > 0 && conshdlrdata->ncallsnode >= conshdlrdata->iterlimit )
183  return SCIP_OKAY;
184 
185  /* the two phase method is only performed at the root node for sub-SCIPs */
186  if( SCIPgetSubscipDepth(scip) > 0 && SCIPgetDepth(scip) > 0 )
187  return SCIP_OKAY;
188 
189  /* checking the Benders' decomposition subproblems for feasibility. */
191 
192  /* if the stalllimit is exceeded and the subproblem were checked, then the stall count is reset to zero */
193  if( conshdlrdata->stallcount >= conshdlrdata->stalllimit )
194  conshdlrdata->stallcount = 0;
195 
196  return SCIP_OKAY;
197 }
198 
199 
200 /** constraint enforcing method of constraint handler for relaxation solutions */
201 static
202 SCIP_DECL_CONSENFORELAX(consEnforelaxBenderslp)
203 { /*lint --e{715}*/
204  SCIP_CONSHDLRDATA* conshdlrdata;
205 
206  assert(conshdlr != NULL);
207 
208  conshdlrdata = SCIPconshdlrGetData(conshdlr);
209 
210  if( !conshdlrdata->active || (conshdlrdata->maxdepth >= 0 && SCIPgetDepth(scip) > conshdlrdata->maxdepth) )
211  (*result) = SCIP_FEASIBLE;
212  else
214 
215  return SCIP_OKAY;
216 }
217 
218 
219 /** constraint enforcing method of constraint handler for pseudo solutions */
220 static
221 SCIP_DECL_CONSENFOPS(consEnfopsBenderslp)
222 { /*lint --e{715}*/
223  SCIP_CONSHDLRDATA* conshdlrdata;
224 
225  assert(conshdlr != NULL);
226 
227  conshdlrdata = SCIPconshdlrGetData(conshdlr);
228 
229  if( !conshdlrdata->active || (conshdlrdata->maxdepth >= 0 && SCIPgetDepth(scip) > conshdlrdata->maxdepth) )
230  (*result) = SCIP_FEASIBLE;
231  else
233 
234  return SCIP_OKAY;
235 }
236 
237 
238 /** feasibility check method of constraint handler for integral solutions.
239  * The feasibility check for Benders' decomposition is performed in cons_benders. As such, it is redundant to perform
240  * the feasibility check here. As such, the solution is flagged as feasible, which will then be corrected in
241  * cons_benders if the solution is infeasible with respect to the second stage constraints
242  */
243 static
244 SCIP_DECL_CONSCHECK(consCheckBenderslp)
245 { /*lint --e{715}*/
246  (*result) = SCIP_FEASIBLE;
247 
248  return SCIP_OKAY;
249 }
250 
251 
252 /** variable rounding lock method of constraint handler */
253 static
254 SCIP_DECL_CONSLOCK(consLockBenderslp)
255 { /*lint --e{715}*/
256  return SCIP_OKAY;
257 }
258 
259 
260 
261 /*
262  * constraint specific interface methods
263  */
264 
265 /** creates the handler for executing the Benders' decomposition subproblem solve on fractional LP solution and
266  * includes it in SCIP */
268  SCIP* scip /**< SCIP data structure */
269  )
270 {
271  SCIP_CONSHDLRDATA* conshdlrdata = NULL;
272  SCIP_CONSHDLR* conshdlr;
273 
274  /* create benderslp constraint handler data */
275  SCIP_CALL( SCIPallocMemory(scip, &conshdlrdata) );
276  BMSclearMemory(conshdlrdata);
277  conshdlrdata->prevbound = -SCIPinfinity(scip);
278 
279  conshdlr = NULL;
280 
281  /* include constraint handler */
284  consEnfolpBenderslp, consEnfopsBenderslp, consCheckBenderslp, consLockBenderslp,
285  conshdlrdata) );
286  assert(conshdlr != NULL);
287 
288  /* set non-fundamental callbacks via specific setter functions */
289  SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyBenderslp, NULL) );
290  SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeBenderslp) );
291  SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxBenderslp) );
292 
293  /* add Benders' decomposition LP constraint handler parameters */
295  "constraints/" CONSHDLR_NAME "/maxdepth",
296  "depth at which Benders' decomposition cuts are generated from the LP solution (-1: always, 0: only at root)",
297  &conshdlrdata->maxdepth, TRUE, DEFAULT_CONSBENDERSLP_MAXDEPTH, -1, SCIP_MAXTREEDEPTH, NULL, NULL) );
298 
300  "constraints/" CONSHDLR_NAME "/depthfreq",
301  "the depth frequency for generating LP cuts after the max depth is reached (0: never, 1: all nodes, ...)",
302  &conshdlrdata->freq, TRUE, DEFAULT_CONSBENDERSLP_FREQ, 0, SCIP_MAXTREEDEPTH, NULL, NULL) );
303 
305  "constraints/" CONSHDLR_NAME "/stalllimit",
306  "the number of nodes processed without a dual bound improvement before enforcing the LP relaxation, 0: no stall count applied",
307  &conshdlrdata->stalllimit, TRUE, DEFAULT_CONSBENDERSLP_STALLLIMIT, 0, INT_MAX, NULL, NULL) );
308 
310  "constraints/" CONSHDLR_NAME "/iterlimit",
311  "after the root node, only iterlimit fractional LP solutions are used at each node to generate Benders' decomposition cuts.",
312  &conshdlrdata->iterlimit, TRUE, DEFAULT_CONSBENDERSLP_ITERLIMIT, 0, INT_MAX, NULL, NULL) );
313 
315  "constraints/" CONSHDLR_NAME "/active", "is the Benders' decomposition LP cut constraint handler active?",
316  &conshdlrdata->active, FALSE, DEFAULT_ACTIVE, NULL, NULL));
317 
318  conshdlrdata->stallcount = 0;
319  return SCIP_OKAY;
320 }
constraint handler for Benders&#39; decomposition
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:91
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENFORELAX((*consenforelax)))
Definition: scip_cons.c:317
#define CONSHDLR_NEEDSCONS
SCIP_RETCODE SCIPconsBendersEnforceSolution(SCIP *scip, SCIP_SOL *sol, SCIP_CONSHDLR *conshdlr, SCIP_RESULT *result, SCIP_BENDERSENFOTYPE type, SCIP_Bool checkint)
Definition: cons_benders.c:261
#define FALSE
Definition: def.h:96
int SCIPgetSubscipDepth(SCIP *scip)
Definition: scip_copy.c:2600
SCIP_RETCODE SCIPincludeConshdlrBasic(SCIP *scip, SCIP_CONSHDLR **conshdlrptr, const char *name, const char *desc, int enfopriority, int chckpriority, int eagerfreq, SCIP_Bool needscons, SCIP_DECL_CONSENFOLP((*consenfolp)), SCIP_DECL_CONSENFOPS((*consenfops)), SCIP_DECL_CONSCHECK((*conscheck)), SCIP_DECL_CONSLOCK((*conslock)), SCIP_CONSHDLRDATA *conshdlrdata)
Definition: scip_cons.c:175
#define CONSHDLR_EAGERFREQ
SCIP_Real SCIPinfinity(SCIP *scip)
#define TRUE
Definition: def.h:95
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
#define CONSHDLR_ENFOPRIORITY
static GRAPHNODE ** active
static SCIP_DECL_CONSHDLRCOPY(conshdlrCopyBenderslp)
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:83
#define CONSHDLR_DESC
static SCIP_DECL_CONSFREE(consFreeBenderslp)
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy)))
Definition: scip_cons.c:341
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip_cons.c:366
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4204
#define NULL
Definition: lpi_spx1.cpp:164
#define SCIP_CALL(x)
Definition: def.h:393
SCIP_Real SCIPgetLowerbound(SCIP *scip)
static SCIP_DECL_CONSENFORELAX(consEnforelaxBenderslp)
#define SCIP_Bool
Definition: def.h:93
static SCIP_DECL_CONSCHECK(consCheckBenderslp)
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:670
#define CONSHDLR_CHECKPRIORITY
#define DEFAULT_ACTIVE
#define BMSclearMemory(ptr)
Definition: memory.h:131
#define SCIP_MAXTREEDEPTH
Definition: def.h:329
#define SCIPfreeMemory(scip, ptr)
Definition: scip_mem.h:78
#define CONSHDLR_NAME
static SCIP_DECL_CONSENFOPS(consEnfopsBenderslp)
#define DEFAULT_CONSBENDERSLP_STALLLIMIT
constraint handler for benderslp decomposition
#define SCIP_Real
Definition: def.h:186
#define DEFAULT_CONSBENDERSLP_MAXDEPTH
#define DEFAULT_CONSBENDERSLP_FREQ
static SCIP_DECL_CONSENFOLP(consEnfolpBenderslp)
#define SCIP_Longint
Definition: def.h:171
#define SCIPallocMemory(scip, ptr)
Definition: scip_mem.h:60
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
Definition: type_cons.h:64
SCIP_RETCODE SCIPincludeConshdlrBenderslp(SCIP *scip)
#define DEFAULT_CONSBENDERSLP_ITERLIMIT
SCIP callable library.
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
static SCIP_DECL_CONSLOCK(consLockBenderslp)