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 ninteger;
184  int nbin;
185  int nint;
186  int nimpl;
187  int v;
188 
189  assert(conshdlr != NULL);
190  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
191  assert(scip != NULL);
192 
193  SCIPdebugMsg(scip, "Check method of integrality constraint (checkintegrality=%u)\n", checkintegrality);
194 
195  SCIP_CALL( SCIPgetSolVarsData(scip, sol, &vars, NULL, &nbin, &nint, &nimpl, NULL) );
196 
197  *result = SCIP_FEASIBLE;
198 
199  if( !checkintegrality )
200  return SCIP_OKAY;
201 
202  ninteger = nbin + nint;
203 
204  for( v = 0; v < ninteger; ++v )
205  {
206  solval = SCIPgetSolVal(scip, sol, vars[v]);
207 
208  if( sol != NULL )
210 
211  if( !SCIPisFeasIntegral(scip, solval) )
212  {
213  *result = SCIP_INFEASIBLE;
214 
215  if( printreason )
216  {
217  SCIPinfoMessage(scip, NULL, "violation: integrality condition of variable <%s> = %.15g\n",
218  SCIPvarGetName(vars[v]), solval);
219  }
220  if( !completely )
221  break;
222  }
223  }
224 
225  return SCIP_OKAY;
226 }
227 
228 /** variable rounding lock method of constraint handler */
229 static
230 SCIP_DECL_CONSLOCK(consLockIntegral)
231 { /*lint --e{715}*/
232  return SCIP_OKAY;
233 }
234 
235 /** constraint handler method to suggest dive bound changes during the generic diving algorithm */
236 static
237 SCIP_DECL_CONSGETDIVEBDCHGS(consGetDiveBdChgsIntegral)
238 { /*lint --e{715}*/
239  SCIP_VAR** vars;
240  SCIP_Real solval;
241  SCIP_Real score;
242  SCIP_Real bestscore;
243  SCIP_Bool bestroundup;
244  int ninteger;
245  int nbin;
246  int nint;
247  int nimpl;
248  int v;
249  int bestcandidx;
250 
251  assert(scip != NULL);
252  assert(sol != NULL);
253  assert(diveset != NULL);
254 
255  assert(conshdlr != NULL);
256  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
257  assert(scip != NULL);
258 
259  SCIPdebugMsg(scip, "integral constraint handler: determine diving bound changes\n");
260 
261  SCIP_CALL( SCIPgetSolVarsData(scip, sol, &vars, NULL, &nbin, &nint, &nimpl, NULL) );
262 
263  ninteger = nbin + nint + nimpl;
264  bestscore = SCIP_REAL_MIN;
265  bestcandidx = -1;
266  *success = FALSE;
267  bestroundup = FALSE; /* only for lint */
268 
269  /* loop over solution values and get score of fractional variables */
270  for( v = 0; v < ninteger; ++v )
271  {
272  solval = SCIPgetSolVal(scip, sol, vars[v]);
273 
274  /* skip variable if solution value disagrees with the local bounds */
275  if( ! SCIPisFeasIntegral(scip, solval) && SCIPisGE(scip, solval, SCIPvarGetLbLocal(vars[v])) && SCIPisLE(scip, solval, SCIPvarGetUbLocal(vars[v])) )
276  {
277  SCIP_Bool roundup;
278 
279  SCIP_CALL( SCIPgetDivesetScore(scip, diveset, SCIP_DIVETYPE_INTEGRALITY, vars[v], solval,
280  solval - SCIPfloor(scip, solval), &score, &roundup) );
281 
282  /* we search for candidates with maximum score */
283  if( score > bestscore )
284  {
285  bestcandidx = v;
286  bestscore = score;
287  bestroundup = roundup;
288  *success = TRUE;
289  }
290  }
291  }
292 
293  assert(!(*success) || bestcandidx >= 0);
294 
295  if( *success )
296  {
297  solval = SCIPgetSolVal(scip, sol, vars[bestcandidx]);
298 
299  /* if we want to round up the best candidate, it is added as the preferred bound change */
301  SCIPceil(scip, solval), bestroundup) );
303  SCIPfloor(scip, solval), ! bestroundup) );
304  }
305 
306  return SCIP_OKAY;
307 }
308 
309 /*
310  * constraint specific interface methods
311  */
312 
313 /** creates the handler for integrality constraint and includes it in SCIP */
315  SCIP* scip /**< SCIP data structure */
316  )
317 {
318  SCIP_CONSHDLR* conshdlr;
319 
320  /* include constraint handler */
323  consEnfolpIntegral, consEnfopsIntegral, consCheckIntegral, consLockIntegral, NULL) );
324 
325  assert(conshdlr != NULL);
326 
327  /* set non-fundamental callbacks via specific setter functions */
328  SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyIntegral, consCopyIntegral) );
329  SCIP_CALL( SCIPsetConshdlrGetDiveBdChgs(scip, conshdlr, consGetDiveBdChgsIntegral) );
330  SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxIntegral) );
331 
332  return SCIP_OKAY;
333 }
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:2620
#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:17957
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:1866
#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:17242
#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)
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:17967
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:17433
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)