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