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-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 )
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 */
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
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 */
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
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 */
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
Definition: cons_integral.c:76
#define CONSHDLR_NEEDSCONS
Definition: cons_integral.c:54
static SCIP_DECL_CONSCHECK(consCheckIntegral)
#define CONSHDLR_CHECKPRIORITY
Definition: cons_integral.c:51
#define CONSHDLR_DESC
Definition: cons_integral.c:49
static SCIP_DECL_CONSENFORELAX(consEnforelaxIntegral)
static SCIP_DECL_CONSLOCK(consLockIntegral)
static SCIP_DECL_CONSGETDIVEBDCHGS(consGetDiveBdChgsIntegral)
static SCIP_DECL_CONSENFOLP(consEnfolpIntegral)
Definition: cons_integral.c:82
#define CONSHDLR_EAGERFREQ
Definition: cons_integral.c:52
#define CONSHDLR_ENFOPRIORITY
Definition: cons_integral.c:50
static SCIP_DECL_CONSHDLRCOPY(conshdlrCopyIntegral)
Definition: cons_integral.c:62
#define CONSHDLR_NAME
Definition: cons_integral.c:48
#define consEnfopsIntegral
Definition: cons_integral.c:78
constraint handler for the integrality constraint
#define NULL
Definition: def.h:267
#define SCIP_Bool
Definition: def.h:91
#define SCIP_Real
Definition: def.h:173
#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,...)
Definition: scip_message.c:208
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_RETCODE SCIPaddExternBranchCand(SCIP *scip, SCIP_VAR *var, SCIP_Real score, SCIP_Real solval)
Definition: scip_branch.c:665
SCIP_RETCODE SCIPbranchExtern(SCIP *scip, SCIP_RESULT *result)
Definition: scip_branch.c:1258
int SCIPgetNLPBranchCands(SCIP *scip)
Definition: scip_branch.c:428
SCIP_RETCODE SCIPbranchLP(SCIP *scip, SCIP_RESULT *result)
Definition: scip_branch.c:1234
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 SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENFORELAX((*consenforelax)))
Definition: scip_cons.c:323
SCIP_RETCODE SCIPsetConshdlrGetDiveBdChgs(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETDIVEBDCHGS((*consgetdivebdchgs)))
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)), SCIP_DECL_CONSCOPY((*conscopy)))
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
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_DIVETYPE_INTEGRALITY
Definition: type_heur.h:60
@ SCIP_BRANCHDIR_DOWNWARDS
Definition: type_history.h:43
@ SCIP_BRANCHDIR_UPWARDS
Definition: type_history.h:44
@ 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
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63