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 */ 69 SCIP_CALL( SCIPincludeConshdlrIntegral(scip) ); 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 */ 96 if( SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_UNBOUNDEDRAY ) 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 ) 209 SCIPupdateSolIntegralityViolation(scip, sol, EPSFRAC(solval, SCIPfeastol(scip))); 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 */ 300 SCIP_CALL( SCIPaddDiveBoundChange(scip, vars[bestcandidx], SCIP_BRANCHDIR_UPWARDS, 301 SCIPceil(scip, solval), bestroundup) ); 302 SCIP_CALL( SCIPaddDiveBoundChange(scip, vars[bestcandidx], SCIP_BRANCHDIR_DOWNWARDS, 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 */ 314 SCIP_RETCODE SCIPincludeConshdlrIntegral( 315 SCIP* scip /**< SCIP data structure */ 316 ) 317 { 318 SCIP_CONSHDLR* conshdlr; 319 320 /* include constraint handler */ 321 SCIP_CALL( SCIPincludeConshdlrBasic(scip, &conshdlr, CONSHDLR_NAME, CONSHDLR_DESC, 322 CONSHDLR_ENFOPRIORITY, CONSHDLR_CHECKPRIORITY, CONSHDLR_EAGERFREQ, CONSHDLR_NEEDSCONS, 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 } 334