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