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