SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
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-2024 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) */
61static
62SCIP_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 */
81static
82SCIP_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 )
100 else
102 return SCIP_OKAY;
103 }
104
105 /* call branching methods */
107
108 /* if no branching was done, the LP solution was not fractional */
109 if( *result == SCIP_DIDNOTRUN )
111
112 return SCIP_OKAY;
113}
114
115/** constraint enforcing method of constraint handler for relaxation solutions */
116static
117SCIP_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
134
136
137 for( i = 0; i < nbinvars + nintvars; ++i )
138 {
139 assert(vars[i] != NULL);
141
143 {
145 {
146 SCIPdebugMsg(scip, "Cutoff for integral variable %s with bounds [%f, %f] and value %f\n", SCIPvarGetName(vars[i]),
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 */
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 */
169
170 /* since we only call it if we added external candidates, the branching rule should always be able to branch */
172 }
173
174 return SCIP_OKAY;
175}
176
177/** feasibility check method of constraint handler for integral solutions */
178static
179SCIP_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
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 {
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 */
229static
230SCIP_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 */
236static
237SCIP_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
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}
#define consCopyIntegral
#define CONSHDLR_NEEDSCONS
#define CONSHDLR_CHECKPRIORITY
#define CONSHDLR_DESC
#define CONSHDLR_EAGERFREQ
#define CONSHDLR_ENFOPRIORITY
#define CONSHDLR_NAME
#define consEnfopsIntegral
constraint handler for the integrality constraint
#define NULL
Definition def.h:267
#define EPSFRAC(x, eps)
Definition def.h:209
#define TRUE
Definition def.h:93
#define FALSE
Definition def.h:94
#define SCIP_REAL_MIN
Definition def.h:175
#define SCIP_CALL(x)
Definition def.h:374
SCIP_RETCODE SCIPincludeConshdlrIntegral(SCIP *scip)
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
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition scip_prob.c:1866
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
#define SCIPdebugMsg
SCIP_RETCODE SCIPaddExternBranchCand(SCIP *scip, SCIP_VAR *var, SCIP_Real score, SCIP_Real solval)
SCIP_RETCODE SCIPbranchExtern(SCIP *scip, SCIP_RESULT *result)
int SCIPgetNLPBranchCands(SCIP *scip)
SCIP_RETCODE SCIPbranchLP(SCIP *scip, SCIP_RESULT *result)
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:323
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:181
SCIP_RETCODE SCIPsetConshdlrGetDiveBdChgs(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:877
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition cons.c:4197
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)),)
Definition scip_cons.c:347
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition scip_lp.c:168
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_RETCODE SCIPaddDiveBoundChange(SCIP *scip, SCIP_VAR *var, SCIP_BRANCHDIR dir, SCIP_Real value, SCIP_Bool preferred)
void SCIPupdateSolIntegralityViolation(SCIP *scip, SCIP_SOL *sol, SCIP_Real absviol)
Definition scip_sol.c:94
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition scip_sol.c:1217
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeastol(SCIP *scip)
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition var.c:18144
const char * SCIPvarGetName(SCIP_VAR *var)
Definition var.c:17419
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition var.c:17610
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition var.c:18134
return SCIP_OKAY
static SCIP_DIVESET * diveset
static SCIP_SOL * sol
assert(minobj< SCIPgetCutoffbound(scip))
SCIP_Bool roundup
static SCIP_VAR ** vars
int nbinvars
int nintvars
public methods for managing constraints
public methods for message output
public methods for problem variables
public methods for branching rule plugins and branching
public methods for constraint handler plugins and constraints
public methods for the LP relaxation, rows and columns
public methods for message handling
public methods for numerical tolerances
public methods for global and local (sub)problems
public methods for the probing mode
public methods for solutions
#define SCIP_DECL_CONSENFOLP(x)
Definition type_cons.h:363
#define SCIP_DECL_CONSENFORELAX(x)
Definition type_cons.h:388
#define SCIP_DECL_CONSGETDIVEBDCHGS(x)
Definition type_cons.h:919
#define SCIP_DECL_CONSLOCK(x)
Definition type_cons.h:675
#define SCIP_DECL_CONSCHECK(x)
Definition type_cons.h:474
#define SCIP_DECL_CONSHDLRCOPY(x)
Definition type_cons.h:108
#define SCIP_DIVETYPE_INTEGRALITY
Definition type_heur.h:60
@ SCIP_BRANCHDIR_DOWNWARDS
@ SCIP_BRANCHDIR_UPWARDS
@ SCIP_LPSOLSTAT_UNBOUNDEDRAY
Definition type_lp.h:45
@ SCIP_DIDNOTRUN
Definition type_result.h:42
@ SCIP_CUTOFF
Definition type_result.h:48
@ SCIP_FEASIBLE
Definition type_result.h:45
@ SCIP_INFEASIBLE
Definition type_result.h:46
enum SCIP_Retcode SCIP_RETCODE