Scippy

SCIP

Solving Constraint Integer Programs

benderscut_feas.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 benderscut_feas.c
17  * @brief Standard feasibility cuts for Benders' decomposition
18  * @author Stephen J. Maher
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #include "scip/benderscut_feas.h"
24 #include "scip/cons_linear.h"
25 #include "scip/pub_benderscut.h"
26 #include "scip/pub_benders.h"
27 #include "scip/pub_message.h"
28 #include "scip/pub_misc.h"
29 #include "scip/pub_misc_linear.h"
30 #include "scip/pub_var.h"
31 #include "scip/scip_benders.h"
32 #include "scip/scip_cons.h"
33 #include "scip/scip_general.h"
34 #include "scip/scip_lp.h"
35 #include "scip/scip_message.h"
36 #include "scip/scip_numerics.h"
37 #include "scip/scip_prob.h"
38 #include "scip/scip_solvingstats.h"
39 #include "scip/scip_var.h"
40 
41 #define BENDERSCUT_NAME "feas"
42 #define BENDERSCUT_DESC "Standard feasibility cuts for Benders' decomposition"
43 #define BENDERSCUT_PRIORITY 10000
44 #define BENDERSCUT_LPCUT TRUE
45 
46 /*
47  * Local methods
48  */
49 
50 /** computing as standard Benders' feasibility cut from the dual solutions of the LP
51  *
52  * NOTE: The cut must be created before being passed to this function
53  */
54 static
56  SCIP* masterprob, /**< the SCIP instance of the master problem */
57  SCIP* subproblem, /**< the SCIP instance of the pricing problem */
58  SCIP_BENDERS* benders, /**< the benders' decomposition structure */
59  SCIP_SOL* sol, /**< primal CIP solution */
60  SCIP_CONS* cut, /**< the cut that is generated from the pricing problem */
61  SCIP_Bool* success /**< was the cut generation successful? */
62  )
63 {
64  SCIP_VAR** vars;
65  SCIP_VAR** fixedvars;
66  SCIP_CONS** conss;
67  int nvars;
68  int nfixedvars;
69  int nconss;
70  SCIP_Real dualsol;
71  SCIP_Real lhs; /* the left hand side of the cut */
72  SCIP_Real addval; /* the value that must be added to the lhs */
73  SCIP_Real activity;
74  int i;
75 
76  assert(masterprob != NULL);
77  assert(subproblem != NULL);
78  assert(benders != NULL);
79  assert(cut != NULL);
80 
81  (*success) = FALSE;
82 
83  nvars = SCIPgetNVars(subproblem);
84  vars = SCIPgetVars(subproblem);
85  nfixedvars = SCIPgetNFixedVars(subproblem);
86  fixedvars = SCIPgetFixedVars(subproblem);
87 
88  nconss = SCIPgetNConss(subproblem);
89  conss = SCIPgetConss(subproblem);
90 
91  /* looping over all constraints and setting the coefficients of the cut */
92  for( i = 0; i < nconss; i++ )
93  {
94  SCIP_Bool conssuccess;
95 
96  addval = 0;
97  SCIPconsGetDualfarkas(subproblem, conss[i], &dualsol, &conssuccess);
98  if( !conssuccess )
99  {
100  (*success) = FALSE;
101  SCIPdebugMsg(masterprob, "Error when generating feasibility cut.\n");
102  return SCIP_OKAY;
103  }
104 
105  if( SCIPisDualfeasZero(subproblem, dualsol) )
106  continue;
107 
108  lhs = SCIPgetLhsLinear(masterprob, cut);
109 
110  if( SCIPisPositive(subproblem, dualsol) )
111  addval = dualsol*SCIPconsGetLhs(subproblem, conss[i], &conssuccess);
112  else if( SCIPisNegative(subproblem, dualsol) )
113  addval = dualsol*SCIPconsGetRhs(subproblem, conss[i], &conssuccess);
114 
115  if( !conssuccess )
116  {
117  (*success) = FALSE;
118  SCIPdebugMsg(masterprob, "Error when generating feasibility cut.\n");
119  return SCIP_OKAY;
120  }
121 
122  lhs += addval;
123 
124  /* if the bound becomes infinite, then the cut generation terminates. */
125  if( SCIPisInfinity(masterprob, lhs) || SCIPisInfinity(masterprob, -lhs)
126  || SCIPisInfinity(masterprob, addval) || SCIPisInfinity(masterprob, -addval))
127  {
128  (*success) = FALSE;
129  SCIPdebugMsg(masterprob, "Infinite bound when generating feasibility cut.\n");
130  return SCIP_OKAY;
131  }
132 
133  /* Update the lhs of the cut */
134  SCIP_CALL( SCIPchgLhsLinear(masterprob, cut, lhs) );
135  }
136 
137  /* looping over all variables to update the coefficients in the computed cut. */
138  for( i = 0; i < nvars + nfixedvars; i++ )
139  {
140  SCIP_VAR* var;
141  SCIP_VAR* mastervar;
142 
143  if( i < nvars )
144  var = vars[i];
145  else
146  var = fixedvars[i - nvars];
147 
148  /* retreiving the master problem variable for the given subproblem variable. */
149  SCIP_CALL( SCIPgetBendersMasterVar(masterprob, benders, var, &mastervar) );
150 
151  dualsol = SCIPgetVarFarkasCoef(subproblem, var);
152 
153  if( SCIPisZero(subproblem, dualsol) )
154  continue;
155 
156  /* checking whether the original variable is a linking variable.
157  * If this is the case, then the corresponding master variable is added to the generated cut.
158  * If the pricing variable is not a linking variable, then the farkas dual value is added to the lhs
159  */
160  if( mastervar != NULL )
161  {
162  SCIPdebugMsg(masterprob ,"Adding coeffs to feasibility cut: <%s> dualsol %g\n", SCIPvarGetName(mastervar), dualsol);
163 
164  SCIP_CALL( SCIPaddCoefLinear(masterprob, cut, mastervar, dualsol) );
165  }
166  else
167  {
168  addval = 0;
169 
170  /* get current lhs of the subproblem cut */
171  lhs = SCIPgetLhsLinear(masterprob, cut);
172 
173  if( SCIPisPositive(subproblem, dualsol) )
174  addval = dualsol*SCIPvarGetUbGlobal(var);
175  else if( SCIPisNegative(subproblem, dualsol) )
176  addval = dualsol*SCIPvarGetLbGlobal(var);
177 
178  lhs -= addval;
179 
180  /* if the bound becomes infinite, then the cut generation terminates. */
181  if( SCIPisInfinity(masterprob, lhs) || SCIPisInfinity(masterprob, -lhs)
182  || SCIPisInfinity(masterprob, addval) || SCIPisInfinity(masterprob, -addval))
183  {
184  (*success) = FALSE;
185  SCIPdebugMsg(masterprob, "Infinite bound when generating feasibility cut.\n");
186  return SCIP_OKAY;
187  }
188 
189  /* Update lhs */
190  SCIP_CALL( SCIPchgLhsLinear(masterprob, cut, lhs) );
191  }
192  }
193 
194  assert(SCIPisInfinity(masterprob, SCIPgetRhsLinear(masterprob, cut)));
195 
196  /* the activity of the cut should be less than the lhs. This will ensure that the evaluated solution will be cut off.
197  * It is possible that the activity is greater than the lhs. This could be caused by numerical difficulties. In this
198  * case, no cut will be generated.
199  */
200  lhs = SCIPgetLhsLinear(masterprob, cut);
201  activity = SCIPgetActivityLinear(masterprob, cut, sol);
202  if( SCIPisGE(masterprob, activity, lhs) )
203  {
204  (*success) = FALSE;
205  SCIPdebugMsg(masterprob ,"Invalid feasibility cut - activity is greater than lhs %g >= %g.\n", activity, lhs);
206  return SCIP_OKAY;
207  }
208 
209  assert(cut != NULL);
210 
211  SCIPdebugPrintCons(masterprob, cut, NULL);
212 
213  (*success) = TRUE;
214 
215  return SCIP_OKAY;
216 }
217 
218 
219 /** generates and applies Benders' cuts */
220 static
222  SCIP* masterprob, /**< the SCIP instance of the master problem */
223  SCIP* subproblem, /**< the SCIP instance of the pricing problem */
224  SCIP_BENDERS* benders, /**< the benders' decomposition */
225  SCIP_BENDERSCUT* benderscut, /**< the benders' decomposition cut method */
226  SCIP_SOL* sol, /**< primal CIP solution */
227  int probnumber, /**< the number of the pricing problem */
228  SCIP_RESULT* result /**< the result from solving the subproblems */
229  )
230 {
231  SCIP_CONS* cut;
232  char cutname[SCIP_MAXSTRLEN];
233  SCIP_Bool success;
234 
235  assert(masterprob != NULL);
236  assert(subproblem != NULL);
237  assert(benders != NULL);
238  assert(result != NULL);
239  assert(SCIPgetStatus(subproblem) == SCIP_STATUS_INFEASIBLE
240  || SCIPgetLPSolstat(subproblem) == SCIP_LPSOLSTAT_INFEASIBLE);
241 
242  /* setting the name of the generated cut */
243  (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "feasibilitycut_%d_%d", probnumber,
244  SCIPbenderscutGetNFound(benderscut) );
245 
246  /* creating the constraint for the cut */
247  SCIP_CALL( SCIPcreateConsBasicLinear(masterprob, &cut, cutname, 0, NULL, NULL, 0.0, SCIPinfinity(masterprob)) );
248 
249  if( SCIPgetNLPIterations(subproblem) == 0 )
250  {
251  SCIPverbMessage(masterprob, SCIP_VERBLEVEL_FULL, NULL, "There were no iterations in pricing problem %d. "
252  "A Benders' decomposition feasibility cut will be generated from the presolved LP data.\n", probnumber);
253  }
254 
255  /* computing the coefficients of the feasibility cut */
256  SCIP_CALL( computeStandardFeasibilityCut(masterprob, subproblem, benders, sol, cut, &success) );
257 
258  /* if success is FALSE, then there was an error in generating the feasibility cut. No cut will be added to the master
259  * problem. Otherwise, the constraint is added to the master problem.
260  */
261  if( !success )
262  {
263  (*result) = SCIP_DIDNOTFIND;
264  SCIPdebugMsg(masterprob, "Error in generating Benders' feasibility cut for problem %d.\n", probnumber);
265  }
266  else
267  {
268  /* adding the constraint to the master problem */
269  SCIP_CALL( SCIPaddCons(masterprob, cut) );
270 
271  (*result) = SCIP_CONSADDED;
272  }
273 
274  SCIP_CALL( SCIPreleaseCons(masterprob, &cut) );
275 
276  return SCIP_OKAY;
277 }
278 
279 /*
280  * Callback methods of Benders' decomposition cuts
281  */
282 
283 /** execution method of Benders' decomposition cuts */
284 static
285 SCIP_DECL_BENDERSCUTEXEC(benderscutExecFeas)
286 { /*lint --e{715}*/
287  SCIP* subproblem;
288 
289  assert(scip != NULL);
290  assert(benders != NULL);
291  assert(benderscut != NULL);
292  assert(result != NULL);
293  assert(probnumber >= 0 && probnumber < SCIPbendersGetNSubproblems(benders));
294 
295  subproblem = SCIPbendersSubproblem(benders, probnumber);
296 
297  /* only generate feasibility cuts if the subproblem is infeasible */
298  if( SCIPgetStatus(subproblem) == SCIP_STATUS_INFEASIBLE ||
300  {
301  /* generating a cut for a given subproblem */
302  SCIP_CALL( generateAndApplyBendersCuts(scip, subproblem, benders, benderscut,
303  sol, probnumber, result) );
304  }
305 
306  return SCIP_OKAY;
307 }
308 
309 
310 /*
311  * Benders' decomposition cuts specific interface methods
312  */
313 
314 /** creates the Standard Feasibility Benders' decomposition cuts and includes it in SCIP */
316  SCIP* scip, /**< SCIP data structure */
317  SCIP_BENDERS* benders /**< Benders' decomposition */
318  )
319 {
320  SCIP_BENDERSCUT* benderscut;
321 
322  assert(benders != NULL);
323 
324  benderscut = NULL;
325 
326  /* include Benders' decomposition cuts */
328  BENDERSCUT_PRIORITY, BENDERSCUT_LPCUT, benderscutExecFeas, NULL) );
329 
330  assert(benderscut != NULL);
331 
332  return SCIP_OKAY;
333 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
SCIP_Real SCIPgetActivityLinear(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol)
SCIP_Real SCIPconsGetLhs(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
Definition: misc_linear.c:102
#define NULL
Definition: def.h:246
SCIP_RETCODE SCIPincludeBenderscutBasic(SCIP *scip, SCIP_BENDERS *benders, SCIP_BENDERSCUT **benderscutptr, const char *name, const char *desc, int priority, SCIP_Bool islpcut, SCIP_DECL_BENDERSCUTEXEC((*benderscutexec)), SCIP_BENDERSCUTDATA *benderscutdata)
internal miscellaneous methods for linear constraints
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:411
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
SCIP_RETCODE SCIPcreateConsBasicLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs)
SCIP_RETCODE SCIPgetBendersMasterVar(SCIP *scip, SCIP_BENDERS *benders, SCIP_VAR *var, SCIP_VAR **mappedvar)
Definition: scip_benders.c:703
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17344
#define SCIP_MAXSTRLEN
Definition: def.h:267
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPconsGetRhs(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
Definition: misc_linear.c:38
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_RETCODE computeStandardFeasibilityCut(SCIP *masterprob, SCIP *subproblem, SCIP_BENDERS *benders, SCIP_SOL *sol, SCIP_CONS *cut, SCIP_Bool *success)
#define FALSE
Definition: def.h:72
public methods for Benders&#39; decomposition
#define BENDERSCUT_LPCUT
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10253
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
#define TRUE
Definition: def.h:71
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_Bool SCIPisDualfeasZero(SCIP *scip, SCIP_Real val)
public methods for problem variables
SCIP_CONS ** SCIPgetConss(SCIP *scip)
Definition: scip_prob.c:3140
#define SCIPdebugPrintCons(x, y, z)
Definition: pub_message.h:83
public methods for SCIP variables
#define SCIPdebugMsg
Definition: scip_message.h:88
SCIP_Real SCIPgetRhsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_Longint SCIPbenderscutGetNFound(SCIP_BENDERSCUT *benderscut)
Definition: benderscut.c:559
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
#define BENDERSCUT_DESC
public methods for numerical tolerances
public methods for querying solving statistics
int SCIPgetNFixedVars(SCIP *scip)
Definition: scip_prob.c:2361
SCIP_VAR ** SCIPgetFixedVars(SCIP *scip)
Definition: scip_prob.c:2318
Standard feasibility cuts for Benders&#39; decomposition.
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17354
public methods for Benders decomposition
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2822
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip_general.c:518
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16730
#define SCIP_CALL(x)
Definition: def.h:358
SCIP_RETCODE SCIPincludeBenderscutFeas(SCIP *scip, SCIP_BENDERS *benders)
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:296
public methods for constraint handler plugins and constraints
public data structures and miscellaneous methods
#define SCIP_Bool
Definition: def.h:69
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:226
SCIP * SCIPbendersSubproblem(SCIP_BENDERS *benders, int probnumber)
Definition: benders.c:4245
Constraint handler for linear constraints in their most general form, .
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
int SCIPbendersGetNSubproblems(SCIP_BENDERS *benders)
Definition: benders.c:4235
public methods for the LP relaxation, rows and columns
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:2044
public methods for Benders&#39; decomposition cuts
general public methods
static SCIP_RETCODE generateAndApplyBendersCuts(SCIP *masterprob, SCIP *subproblem, SCIP_BENDERS *benders, SCIP_BENDERSCUT *benderscut, SCIP_SOL *sol, int probnumber, SCIP_RESULT *result)
int SCIPgetNConss(SCIP *scip)
Definition: scip_prob.c:3094
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1187
public methods for message output
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1999
#define SCIP_Real
Definition: def.h:157
public methods for message handling
#define BENDERSCUT_NAME
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPchgLhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real lhs)
void SCIPconsGetDualfarkas(SCIP *scip, SCIP_CONS *cons, SCIP_Real *dualfarkas, SCIP_Bool *success)
Definition: misc_linear.c:291
static SCIP_DECL_BENDERSCUTEXEC(benderscutExecFeas)
#define BENDERSCUT_PRIORITY
SCIP_Real SCIPgetVarFarkasCoef(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1956
public methods for global and local (sub)problems
SCIP_Real SCIPgetLhsLinear(SCIP *scip, SCIP_CONS *cons)