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