Scippy

SCIP

Solving Constraint Integer Programs

cons_integral.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-2017 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 email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file cons_integral.c
17  * @brief constraint handler for the integrality constraint
18  * @author Tobias Achterberg
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #include <assert.h>
24 #include <string.h>
25 #include <limits.h>
26 
27 #include "scip/cons_integral.h"
28 
29 
30 #define CONSHDLR_NAME "integral"
31 #define CONSHDLR_DESC "integrality constraint"
32 #define CONSHDLR_ENFOPRIORITY 0 /**< priority of the constraint handler for constraint enforcing */
33 #define CONSHDLR_CHECKPRIORITY 0 /**< priority of the constraint handler for checking feasibility */
34 #define CONSHDLR_EAGERFREQ -1 /**< frequency for using all instead of only the useful constraints in separation,
35  * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
36 #define CONSHDLR_NEEDSCONS FALSE /**< should the constraint handler be skipped, if no constraints are available? */
37 
38 /*
39  * Callback methods
40  */
41 
42 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
43 static
44 SCIP_DECL_CONSHDLRCOPY(conshdlrCopyIntegral)
45 { /*lint --e{715}*/
46  assert(scip != NULL);
47  assert(conshdlr != NULL);
48  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
49 
50  /* call inclusion method of constraint handler */
52 
53  *valid = TRUE;
54 
55  return SCIP_OKAY;
56 }
57 
58 #define consCopyIntegral NULL
59 
60 #define consEnfopsIntegral NULL
61 
62 /** constraint enforcing method of constraint handler for LP solutions */
63 static
64 SCIP_DECL_CONSENFOLP(consEnfolpIntegral)
65 { /*lint --e{715}*/
66  assert(conshdlr != NULL);
67  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
68  assert(scip != NULL);
69  assert(conss == NULL);
70  assert(nconss == 0);
71  assert(result != NULL);
72 
73  SCIPdebugMsg(scip, "Enfolp method of integrality constraint: %d fractional variables\n", SCIPgetNLPBranchCands(scip));
74 
75  /* if the root LP is unbounded, we want to terminate with UNBOUNDED or INFORUNBOUNDED,
76  * depending on whether we are able to construct an integral solution; in any case we do not want to branch
77  */
79  {
80  if( SCIPgetNLPBranchCands(scip) == 0 )
81  *result = SCIP_FEASIBLE;
82  else
83  *result = SCIP_INFEASIBLE;
84  return SCIP_OKAY;
85  }
86 
87  /* call branching methods */
88  SCIP_CALL( SCIPbranchLP(scip, result) );
89 
90  /* if no branching was done, the LP solution was not fractional */
91  if( *result == SCIP_DIDNOTRUN )
92  *result = SCIP_FEASIBLE;
93 
94  return SCIP_OKAY;
95 }
96 
97 /** constraint enforcing method of constraint handler for relaxation solutions */
98 static
99 SCIP_DECL_CONSENFORELAX(consEnforelaxIntegral)
100 { /*lint --e{715}*/
101  SCIP_VAR** vars;
102  int nbinvars;
103  int nintvars;
104  int i;
105 
106  assert(conshdlr != NULL);
107  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
108  assert(scip != NULL);
109  assert(conss == NULL);
110  assert(nconss == 0);
111  assert(result != NULL);
112 
113  SCIPdebugMsg(scip, "Enforelax method of integrality constraint\n");
114 
115  *result = SCIP_FEASIBLE;
116 
117  SCIP_CALL( SCIPgetVarsData(scip, &vars, NULL, &nbinvars, &nintvars, NULL, NULL) );
118 
119  for( i = 0; i < nbinvars + nintvars; ++i )
120  {
121  assert(vars[i] != NULL);
122  assert(SCIPvarIsIntegral(vars[i]));
123 
124  if( !SCIPisFeasIntegral(scip, SCIPgetSolVal(scip, sol, vars[i])) )
125  {
126  if( SCIPisFeasEQ(scip, SCIPvarGetLbLocal(vars[i]), SCIPvarGetUbLocal(vars[i])) )
127  {
128  SCIPdebugMsg(scip, "Cutoff for integral variable %s with bounds [%f, %f] and value %f\n", SCIPvarGetName(vars[i]),
129  SCIPvarGetLbLocal(vars[i]), SCIPvarGetUbLocal(vars[i]), SCIPgetSolVal(scip, sol, vars[i]));
130  *result = SCIP_CUTOFF;
131  return SCIP_OKAY;
132  }
133  else
134  {
135  /* @todo better way to handle this would be a BRANCHEXECRELAX callback that could also implement pseudo costs for
136  * relaxation solutions instead of using the enforelaxcallback which is mainly intended for spatial branching
137  */
138  SCIP_CALL( SCIPaddExternBranchCand(scip, vars[i], 0.2, SCIPgetSolVal(scip, sol, vars[i])) );
139  *result = SCIP_INFEASIBLE;
140  }
141  }
142  }
143 
144  /* if we have found a branching candidate, immediately branch to be able to return SCIP_BRANCHED and stop the
145  * enforcement loop
146  */
147  if( *result == SCIP_INFEASIBLE )
148  {
149  /* call branching methods for external candidates */
150  SCIP_CALL( SCIPbranchExtern(scip, result) );
151 
152  /* since we only call it if we added external candidates, the branching rule should always be able to branch */
153  assert(*result != SCIP_DIDNOTRUN);
154  }
155 
156  return SCIP_OKAY;
157 }
158 
159 /** feasibility check method of constraint handler for integral solutions */
160 static
161 SCIP_DECL_CONSCHECK(consCheckIntegral)
162 { /*lint --e{715}*/
163  SCIP_VAR** vars;
164  SCIP_Real solval;
165  int nallinteger;
166  int ninteger;
167  int nbin;
168  int nint;
169  int nimpl;
170  int v;
171 
172  assert(conshdlr != NULL);
173  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
174  assert(scip != NULL);
175 
176  SCIPdebugMsg(scip, "Check method of integrality constraint (checkintegrality=%u)\n", checkintegrality);
177 
178  SCIP_CALL( SCIPgetSolVarsData(scip, sol, &vars, NULL, &nbin, &nint, &nimpl, NULL) );
179 
180  *result = SCIP_FEASIBLE;
181 
182  ninteger = nbin + nint;
183 
184  if( checkintegrality )
185  {
186  for( v = 0; v < ninteger; ++v )
187  {
188  solval = SCIPgetSolVal(scip, sol, vars[v]);
189 
190  if( sol != NULL )
192 
193  if( !SCIPisFeasIntegral(scip, solval) )
194  {
195  *result = SCIP_INFEASIBLE;
196 
197  if( printreason )
198  {
199  SCIPinfoMessage(scip, NULL, "violation: integrality condition of variable <%s> = %.15g\n",
200  SCIPvarGetName(vars[v]), solval);
201  }
202  if( !completely )
203  break;
204  }
205  }
206  }
207 #ifndef NDEBUG
208  else
209  {
210  for( v = 0; v < ninteger; ++v )
211  {
212  solval = SCIPgetSolVal(scip, sol, vars[v]);
213  assert(SCIPisFeasIntegral(scip, solval));
214  }
215  }
216 #endif
217 
218  nallinteger = ninteger + nimpl;
219  for( v = ninteger; v < nallinteger; ++v )
220  {
221  solval = SCIPgetSolVal(scip, sol, vars[v]);
222  if( !SCIPisFeasIntegral(scip, solval) )
223  {
224  *result = SCIP_INFEASIBLE;
225 
226  if( printreason )
227  {
228  SCIPinfoMessage(scip, NULL, "violation: integrality condition of implicit integral variable <%s> = %.15g\n",
229  SCIPvarGetName(vars[v]), solval);
230  }
231  if( !completely )
232  break;
233  }
234  }
235 
236  return SCIP_OKAY;
237 }
238 
239 /** variable rounding lock method of constraint handler */
240 static
241 SCIP_DECL_CONSLOCK(consLockIntegral)
242 { /*lint --e{715}*/
243  return SCIP_OKAY;
244 }
245 
246 /** constraint handler method to suggest dive bound changes during the generic diving algorithm */
247 static
248 SCIP_DECL_CONSGETDIVEBDCHGS(consGetDiveBdChgsIntegral)
249 { /*lint --e{715}*/
250  SCIP_VAR** vars;
251  SCIP_Real solval;
252  SCIP_Real score;
253  SCIP_Real bestscore;
254  SCIP_Bool roundup;
255  int ninteger;
256  int nbin;
257  int nint;
258  int nimpl;
259  int v;
260  int bestcandidx;
261 
262  assert(scip != NULL);
263  assert(sol != NULL);
264  assert(diveset != NULL);
265 
266  assert(conshdlr != NULL);
267  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
268  assert(scip != NULL);
269 
270  SCIPdebugMsg(scip, "integral constraint handler: determine diving bound changes\n");
271 
272  SCIP_CALL( SCIPgetSolVarsData(scip, sol, &vars, NULL, &nbin, &nint, &nimpl, NULL) );
273 
274  ninteger = nbin + nint + nimpl;
275  bestscore = SCIP_REAL_MIN;
276  bestcandidx = -1;
277  *success = FALSE;
278  roundup = FALSE; /* only for lint */
279 
280  /* loop over solution values and get score of fractional variables */
281  for( v = 0; v < ninteger; ++v )
282  {
283  solval = SCIPgetSolVal(scip, sol, vars[v]);
284 
285  /* skip variable if solution value disagrees with the local bounds */
286  if( ! SCIPisFeasIntegral(scip, solval) && SCIPisGE(scip, solval, SCIPvarGetLbLocal(vars[v])) && SCIPisLE(scip, solval, SCIPvarGetUbLocal(vars[v])) )
287  {
288  SCIP_CALL( SCIPgetDivesetScore(scip, diveset, SCIP_DIVETYPE_INTEGRALITY, vars[v], solval,
289  solval - SCIPfloor(scip, solval), &score, &roundup) );
290 
291  /* we search for candidates with maximum score */
292  if( score > bestscore )
293  {
294  bestcandidx = v;
295  bestscore = score;
296  *success = TRUE;
297  }
298  }
299  }
300 
301  assert(!(*success) || bestcandidx >= 0);
302 
303  if( *success )
304  {
305  solval = SCIPgetSolVal(scip, sol, vars[bestcandidx]);
306 
307  /* if we want to round up the best candidate, it is added as the preferred bound change */
309  SCIPceil(scip, solval), roundup) );
311  SCIPfloor(scip, solval), ! roundup) );
312  }
313 
314  return SCIP_OKAY;
315 
316 }
317 
318 /*
319  * constraint specific interface methods
320  */
321 
322 /** creates the handler for integrality constraint and includes it in SCIP */
324  SCIP* scip /**< SCIP data structure */
325  )
326 {
327  SCIP_CONSHDLR* conshdlr;
328 
329  /* include constraint handler */
332  consEnfolpIntegral, consEnfopsIntegral, consCheckIntegral, consLockIntegral, NULL) );
333 
334  assert(conshdlr != NULL);
335 
336  /* set non-fundamental callbacks via specific setter functions */
337  SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyIntegral, consCopyIntegral) );
338  SCIP_CALL( SCIPsetConshdlrGetDiveBdChgs(scip, conshdlr, consGetDiveBdChgsIntegral) );
339  SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxIntegral) );
340 
341  return SCIP_OKAY;
342 }
SCIP_Real SCIPfeastol(SCIP *scip)
Definition: scip.c:46437
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47292
static SCIP_DECL_CONSLOCK(consLockIntegral)
SCIP_RETCODE SCIPgetSolVarsData(SCIP *scip, SCIP_SOL *sol, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip.c:12435
#define consCopyIntegral
Definition: cons_integral.c:59
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENFORELAX((*consenforelax)))
Definition: scip.c:6036
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17332
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47009
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip.c:11680
#define FALSE
Definition: def.h:64
static SCIP_DECL_CONSHDLRCOPY(conshdlrCopyIntegral)
Definition: cons_integral.c:45
#define CONSHDLR_NAME
Definition: cons_integral.c:30
#define CONSHDLR_EAGERFREQ
Definition: cons_integral.c:34
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.c:5894
#define TRUE
Definition: def.h:63
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_RETCODE SCIPaddDiveBoundChange(SCIP *scip, SCIP_VAR *var, SCIP_BRANCHDIR dir, SCIP_Real value, SCIP_Bool preferred)
Definition: scip.c:36909
#define EPSFRAC(x, eps)
Definition: def.h:185
int SCIPgetNLPBranchCands(SCIP *scip)
Definition: scip.c:37028
#define SCIPdebugMsg
Definition: scip.h:455
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip.c:1343
#define consEnfopsIntegral
Definition: cons_integral.c:61
SCIP_RETCODE SCIPsetConshdlrGetDiveBdChgs(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETDIVEBDCHGS((*consgetdivebdchgs)))
Definition: scip.c:6590
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy)))
Definition: scip.c:6060
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4113
#define CONSHDLR_ENFOPRIORITY
Definition: cons_integral.c:32
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16662
void SCIPupdateSolIntegralityViolation(SCIP *scip, SCIP_SOL *sol, SCIP_Real absviol)
Definition: scip.c:13749
static SCIP_DECL_CONSGETDIVEBDCHGS(consGetDiveBdChgsIntegral)
#define SCIP_CALL(x)
Definition: def.h:350
static SCIP_DECL_CONSENFORELAX(consEnforelaxIntegral)
#define SCIP_Bool
Definition: def.h:61
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip.c:29287
#define CONSHDLR_NEEDSCONS
Definition: cons_integral.c:37
static SCIP_DECL_CONSCHECK(consCheckIntegral)
SCIP_RETCODE SCIPaddExternBranchCand(SCIP *scip, SCIP_VAR *var, SCIP_Real score, SCIP_Real solval)
Definition: scip.c:37266
#define SCIP_REAL_MIN
Definition: def.h:151
static SCIP_DECL_CONSENFOLP(consEnfolpIntegral)
Definition: cons_integral.c:65
constraint handler for the integrality constraint
#define SCIP_Real
Definition: def.h:149
SCIP_RETCODE SCIPbranchLP(SCIP *scip, SCIP_RESULT *result)
Definition: scip.c:37788
SCIP_RETCODE SCIPbranchExtern(SCIP *scip, SCIP_RESULT *result)
Definition: scip.c:37812
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46983
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17342
SCIP_RETCODE SCIPgetDivesetScore(SCIP *scip, SCIP_DIVESET *diveset, SCIP_DIVETYPE divetype, SCIP_VAR *divecand, SCIP_Real divecandsol, SCIP_Real divecandfrac, SCIP_Real *candscore, SCIP_Bool *roundup)
Definition: scip.c:36769
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip.c:47393
#define CONSHDLR_DESC
Definition: cons_integral.c:31
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
Definition: scip.c:47155
#define SCIP_DIVETYPE_INTEGRALITY
Definition: type_heur.h:45
#define CONSHDLR_CHECKPRIORITY
Definition: cons_integral.c:33
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:16853
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip.c:38905
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
Definition: scip.c:47143
SCIP_RETCODE SCIPincludeConshdlrIntegral(SCIP *scip)