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-2019 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 scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file cons_benderslp.c
17  * @brief constraint handler for benderslp decomposition
18  * @author Stephen J. Maher
19  *
20  * Two constraint handlers are implemented for the generation of Benders' decomposition cuts. When included in a
21  * problem, the Benders' decomposition constraint handlers generate cuts during the enforcement of LP and relaxation
22  * solutions. Additionally, Benders' decomposition cuts can be generated when checking the feasibility of solutions with
23  * respect to the subproblem constraints.
24  *
25  * This constraint handler has an enforcement priority that is greater than the integer constraint handler. This means
26  * that all LP solutions will be first checked for feasibility with respect to the Benders' decomposition second stage
27  * constraints before performing an integrality check. This is part of a multi-phase approach for solving mixed integer
28  * programs by Benders' decomposition.
29  *
30  * A parameter is available to control the depth at which the non-integer LP solution are enforced by solving the
31  * Benders' decomposition subproblems. This parameter is set to 0 by default, indicating that non-integer LP solutions
32  * are enforced only at the root node.
33  */
34 
35 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
36 
37 #include <assert.h>
38 
39 #include "scip/scip.h"
40 #include "scip/cons_benderslp.h"
41 #include "scip/cons_benders.h"
42 
43 
44 /* fundamental constraint handler properties */
45 #define CONSHDLR_NAME "benderslp"
46 #define CONSHDLR_DESC "constraint handler for Benders' Decomposition to separate LP solutions"
47 #define CONSHDLR_ENFOPRIORITY 10000000 /**< priority of the constraint handler for constraint enforcing */
48 #define CONSHDLR_CHECKPRIORITY 10000000 /**< priority of the constraint handler for checking feasibility */
49 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
50  * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
51 #define CONSHDLR_NEEDSCONS FALSE /**< should the constraint handler be skipped, if no constraints are available? */
52 
53 
54 #define DEFAULT_CONSBENDERSLP_MAXDEPTH 0/**< depth at which Benders' decomposition cuts are generated from the LP
55  * solution (-1: always, 0: only at root) */
56 #define DEFAULT_ACTIVE FALSE /**< is the constraint handler active? */
57 
58 /*
59  * Data structures
60  */
61 
62 /** constraint handler data */
63 struct SCIP_ConshdlrData
64 {
65  int maxdepth; /**< the maximum depth at which Benders' cuts are generated from the LP */
66  SCIP_Bool active; /**< is the constraint handler active? */
67 };
68 
69 
70 /*
71  * Local methods
72  */
73 
74 
75 /*
76  * Callback methods of constraint handler
77  */
78 
79 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
80 static
81 SCIP_DECL_CONSHDLRCOPY(conshdlrCopyBenderslp)
82 { /*lint --e{715}*/
83  assert(scip != NULL);
84 
86 
87  *valid = TRUE;
88 
89  return SCIP_OKAY;
90 }
91 
92 
93 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
94 static
95 SCIP_DECL_CONSFREE(consFreeBenderslp)
96 { /*lint --e{715}*/
97  SCIP_CONSHDLRDATA* conshdlrdata;
98 
99  assert(scip != NULL);
100  assert(conshdlr != NULL);
101 
102  conshdlrdata = SCIPconshdlrGetData(conshdlr);
103  assert(conshdlrdata != NULL);
104 
105  /* freeing the constraint handler data */
106  SCIPfreeMemory(scip, &conshdlrdata);
107 
108  return SCIP_OKAY;
109 }
110 
111 
112 
113 /** constraint enforcing method of constraint handler for LP solutions */
114 static
115 SCIP_DECL_CONSENFOLP(consEnfolpBenderslp)
116 { /*lint --e{715}*/
117  SCIP_CONSHDLRDATA* conshdlrdata;
118 
119  assert(conshdlr != NULL);
120 
121  conshdlrdata = SCIPconshdlrGetData(conshdlr);
122 
123  if( !conshdlrdata->active || (conshdlrdata->maxdepth >= 0 && SCIPgetDepth(scip) > conshdlrdata->maxdepth) )
124  (*result) = SCIP_FEASIBLE;
125  else
127 
128  return SCIP_OKAY;
129 }
130 
131 
132 /** constraint enforcing method of constraint handler for relaxation solutions */
133 static
134 SCIP_DECL_CONSENFORELAX(consEnforelaxBenderslp)
135 { /*lint --e{715}*/
136  SCIP_CONSHDLRDATA* conshdlrdata;
137 
138  assert(conshdlr != NULL);
139 
140  conshdlrdata = SCIPconshdlrGetData(conshdlr);
141 
142  if( !conshdlrdata->active || (conshdlrdata->maxdepth >= 0 && SCIPgetDepth(scip) > conshdlrdata->maxdepth) )
143  (*result) = SCIP_FEASIBLE;
144  else
146 
147  return SCIP_OKAY;
148 }
149 
150 
151 /** constraint enforcing method of constraint handler for pseudo solutions */
152 static
153 SCIP_DECL_CONSENFOPS(consEnfopsBenderslp)
154 { /*lint --e{715}*/
155  SCIP_CONSHDLRDATA* conshdlrdata;
156 
157  assert(conshdlr != NULL);
158 
159  conshdlrdata = SCIPconshdlrGetData(conshdlr);
160 
161  if( !conshdlrdata->active || (conshdlrdata->maxdepth >= 0 && SCIPgetDepth(scip) > conshdlrdata->maxdepth) )
162  (*result) = SCIP_FEASIBLE;
163  else
165 
166  return SCIP_OKAY;
167 }
168 
169 
170 /** feasibility check method of constraint handler for integral solutions.
171  * The feasibility check for Benders' decomposition is performed in cons_benders. As such, it is redundant to perform
172  * the feasibility check here. As such, the solution is flagged as feasible, which will then be corrected in
173  * cons_benders if the solution is infeasible with respect to the second stage constraints
174  */
175 static
176 SCIP_DECL_CONSCHECK(consCheckBenderslp)
177 { /*lint --e{715}*/
178  (*result) = SCIP_FEASIBLE;
179 
180  return SCIP_OKAY;
181 }
182 
183 
184 /** variable rounding lock method of constraint handler */
185 static
186 SCIP_DECL_CONSLOCK(consLockBenderslp)
187 { /*lint --e{715}*/
188  return SCIP_OKAY;
189 }
190 
191 
192 
193 /*
194  * constraint specific interface methods
195  */
196 
197 /** creates the handler for executing the Benders' decomposition subproblem solve on fractional LP solution and
198  * includes it in SCIP */
200  SCIP* scip /**< SCIP data structure */
201  )
202 {
203  SCIP_CONSHDLRDATA* conshdlrdata = NULL;
204  SCIP_CONSHDLR* conshdlr;
205 
206  /* create benderslp constraint handler data */
207  SCIP_CALL( SCIPallocMemory(scip, &conshdlrdata) );
208 
209  conshdlr = NULL;
210 
211  /* include constraint handler */
214  consEnfolpBenderslp, consEnfopsBenderslp, consCheckBenderslp, consLockBenderslp,
215  conshdlrdata) );
216  assert(conshdlr != NULL);
217 
218  /* set non-fundamental callbacks via specific setter functions */
219  SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyBenderslp, NULL) );
220  SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeBenderslp) );
221  SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxBenderslp) );
222 
223  /* add Benders' decomposition LP constraint handler parameters */
225  "constraints/" CONSHDLR_NAME "/maxdepth",
226  "depth at which Benders' decomposition cuts are generated from the LP solution (-1: always, 0: only at root)",
227  &conshdlrdata->maxdepth, TRUE, DEFAULT_CONSBENDERSLP_MAXDEPTH, -1, SCIP_MAXTREEDEPTH, NULL, NULL) );
228 
230  "constraints/" CONSHDLR_NAME "/active", "is the Benders' decomposition LP cut constraint handler active?",
231  &conshdlrdata->active, FALSE, DEFAULT_ACTIVE, NULL, NULL));
232 
233  return SCIP_OKAY;
234 }
constraint handler for Benders&#39; decomposition
#define NULL
Definition: def.h:253
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENFORELAX((*consenforelax)))
Definition: scip_cons.c:307
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:165
#define CONSHDLR_NEEDSCONS
#define FALSE
Definition: def.h:73
#define CONSHDLR_EAGERFREQ
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
#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:47
static SCIP_DECL_CONSHDLRCOPY(conshdlrCopyBenderslp)
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip_cons.c:356
#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:222
#define SCIP_CALL(x)
Definition: def.h:365
SCIP_RETCODE SCIPincludeConshdlrBenderslp(SCIP *scip)
static SCIP_DECL_CONSENFORELAX(consEnforelaxBenderslp)
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:637
#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:331
static SCIP_DECL_CONSCHECK(consCheckBenderslp)
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4211
#define CONSHDLR_CHECKPRIORITY
#define DEFAULT_ACTIVE
#define SCIP_MAXTREEDEPTH
Definition: def.h:301
#define SCIPfreeMemory(scip, ptr)
Definition: scip_mem.h:67
#define CONSHDLR_NAME
static SCIP_DECL_CONSENFOPS(consEnfopsBenderslp)
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:73
constraint handler for benderslp decomposition
#define DEFAULT_CONSBENDERSLP_MAXDEPTH
static SCIP_DECL_CONSENFOLP(consEnfolpBenderslp)
#define SCIPallocMemory(scip, ptr)
Definition: scip_mem.h:51
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
Definition: type_cons.h:50
SCIP callable library.
static SCIP_DECL_CONSLOCK(consLockBenderslp)