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 presol_implics.c 26 * @ingroup DEFPLUGINS_PRESOL 27 * @brief implics presolver 28 * @author Tobias Achterberg 29 */ 30 31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 32 33 #include "blockmemshell/memory.h" 34 #include "scip/presol_implics.h" 35 #include "scip/pub_message.h" 36 #include "scip/pub_presol.h" 37 #include "scip/pub_var.h" 38 #include "scip/scip_mem.h" 39 #include "scip/scip_message.h" 40 #include "scip/scip_numerics.h" 41 #include "scip/scip_presol.h" 42 #include "scip/scip_prob.h" 43 #include "scip/scip_var.h" 44 #include <string.h> 45 46 #define PRESOL_NAME "implics" 47 #define PRESOL_DESC "implication graph aggregator" 48 #define PRESOL_PRIORITY -10000 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers) */ 49 #define PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */ 50 #define PRESOL_TIMING SCIP_PRESOLTIMING_MEDIUM /* timing of the presolver (fast, medium, or exhaustive) */ 51 52 53 /* 54 * Callback methods of presolver 55 */ 56 57 /** copy method for constraint handler plugins (called when SCIP copies plugins) */ 58 static 59 SCIP_DECL_PRESOLCOPY(presolCopyImplics) 60 { /*lint --e{715}*/ 61 assert(scip != NULL); 62 assert(presol != NULL); 63 assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0); 64 65 /* call inclusion method of presolver */ 66 SCIP_CALL( SCIPincludePresolImplics(scip) ); 67 68 return SCIP_OKAY; 69 } 70 71 72 /** execution method of presolver */ 73 static 74 SCIP_DECL_PRESOLEXEC(presolExecImplics) 75 { /*lint --e{715}*/ 76 SCIP_VAR** vars; 77 SCIP_VAR** bdchgvars; 78 SCIP_BOUNDTYPE* bdchgtypes; 79 SCIP_Real* bdchgvals; 80 SCIP_VAR** aggrvars; 81 SCIP_VAR** aggraggvars; 82 SCIP_Real* aggrcoefs; 83 SCIP_Real* aggrconsts; 84 int nbdchgs; 85 int naggregations; 86 int nbinvars; 87 int v; 88 89 assert(result != NULL); 90 91 *result = SCIP_DIDNOTFIND; 92 93 /* initialize fixing and aggregation storages */ 94 bdchgvars = NULL; 95 bdchgtypes = NULL; 96 bdchgvals = NULL; 97 nbdchgs = 0; 98 aggrvars = NULL; 99 aggraggvars = NULL; 100 aggrcoefs = NULL; 101 aggrconsts = NULL; 102 naggregations = 0; 103 104 /* get active binary problem variables */ 105 vars = SCIPgetVars(scip); 106 nbinvars = SCIPgetNBinVars(scip); 107 108 /* look for variable implications in x == 0 and x == 1 with the same implied variable: 109 * x = 0 -> y = lb, and x = 1 -> y = lb: fix y to lb 110 * x = 0 -> y = lb, and x = 1 -> y = ub: aggregate y == lb + (ub-lb)x 111 * x = 0 -> y = ub, and x = 1 -> y = lb: aggregate y == ub - (ub-lb)x 112 * x = 0 -> y = ub, and x = 1 -> y = ub: fix y to ub 113 * the fixings and aggregations are stored in a buffer and applied afterwards, because fixing and aggregation 114 * would modify the vars array and the implication arrays 115 */ 116 for( v = 0; v < nbinvars; ++v ) 117 { 118 SCIP_VAR** implvars[2]; 119 SCIP_BOUNDTYPE* impltypes[2]; 120 SCIP_Real* implbounds[2]; 121 int nimpls[2]; 122 int varfixing; 123 int i0; 124 int i1; 125 126 /* don't perform presolving operations on deleted variables */ 127 if( SCIPvarIsDeleted(vars[v]) ) 128 continue; 129 130 /* get implications for given variable */ 131 for( varfixing = 0; varfixing < 2; ++varfixing ) 132 { 133 implvars[varfixing] = SCIPvarGetImplVars(vars[v], (SCIP_Bool)varfixing); 134 impltypes[varfixing] = SCIPvarGetImplTypes(vars[v], (SCIP_Bool)varfixing); 135 implbounds[varfixing] = SCIPvarGetImplBounds(vars[v], (SCIP_Bool)varfixing); 136 nimpls[varfixing] = SCIPvarGetNImpls(vars[v], (SCIP_Bool)varfixing); 137 } 138 139 /* scan implication arrays for equal variables */ 140 i0 = 0; 141 i1 = 0; 142 while( i0 < nimpls[0] && i1 < nimpls[1] ) 143 { 144 int index0; 145 int index1; 146 147 /* scan the binary or non-binary part of the implication arrays */ 148 index0 = SCIPvarGetIndex(implvars[0][i0]); 149 index1 = SCIPvarGetIndex(implvars[1][i1]); 150 while( index0 < index1 ) 151 { 152 i0++; 153 if( i0 == nimpls[0] ) 154 { 155 index0 = -1; 156 break; 157 } 158 index0 = SCIPvarGetIndex(implvars[0][i0]); /*lint !e838*/ 159 } 160 while( index1 < index0 ) 161 { 162 i1++; 163 if( i1 == nimpls[1] ) 164 { 165 index1 = -1; 166 break; 167 } 168 index1 = SCIPvarGetIndex(implvars[1][i1]); /*lint !e838*/ 169 } 170 /**@todo for all implicit binary variables y, check the cliques of x == !varfixing if y is contained */ 171 172 if( index0 == index1 ) 173 { 174 assert(index0 >= 0); 175 assert(i0 < nimpls[0]); 176 assert(i1 < nimpls[1]); 177 assert(implvars[0][i0] == implvars[1][i1]); 178 179 /* multiaggregated variables cannot be aggregated or their bounds tightened */ 180 if( SCIPvarGetStatus(implvars[0][i0]) != SCIP_VARSTATUS_MULTAGGR ) 181 { 182 if( impltypes[0][i0] == impltypes[1][i1] ) 183 { 184 /* found implication x = 0 -> y >= b / y <= b and x = 1 -> y >= c / y <= c 185 * => change bound y >= min(b,c) / y <= max(b,c) 186 */ 187 SCIP_CALL( SCIPreallocBufferArray(scip, &bdchgvars, nbdchgs+1) ); 188 SCIP_CALL( SCIPreallocBufferArray(scip, &bdchgtypes, nbdchgs+1) ); 189 SCIP_CALL( SCIPreallocBufferArray(scip, &bdchgvals, nbdchgs+1) ); 190 bdchgvars[nbdchgs] = implvars[0][i0]; 191 bdchgtypes[nbdchgs] = impltypes[0][i0]; 192 if( impltypes[0][i0] == SCIP_BOUNDTYPE_LOWER ) 193 bdchgvals[nbdchgs] = MIN(implbounds[0][i0], implbounds[1][i1]); 194 else 195 bdchgvals[nbdchgs] = MAX(implbounds[0][i0], implbounds[1][i1]); 196 197 SCIPdebugMsg(scip, " -> <%s> = 0 -> <%s> %s %g, and <%s> = 1 -> <%s> %s %g: tighten <%s> %s %g\n", 198 SCIPvarGetName(vars[v]), SCIPvarGetName(implvars[0][i0]), 199 impltypes[0][i0] == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", implbounds[0][i0], 200 SCIPvarGetName(vars[v]), SCIPvarGetName(implvars[1][i1]), 201 impltypes[1][i1] == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", implbounds[1][i1], 202 SCIPvarGetName(bdchgvars[nbdchgs]), bdchgtypes[nbdchgs] == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", 203 bdchgvals[nbdchgs]); 204 205 nbdchgs++; 206 } 207 else 208 { 209 SCIP_Real implvarlb; 210 SCIP_Real implvarub; 211 212 implvarlb = SCIPvarGetLbGlobal(implvars[0][i0]); 213 implvarub = SCIPvarGetUbGlobal(implvars[0][i0]); 214 215 if( impltypes[0][i0] == SCIP_BOUNDTYPE_UPPER 216 && SCIPisEQ(scip, implbounds[0][i0], implvarlb) 217 && SCIPisEQ(scip, implbounds[1][i1], implvarub) ) 218 { 219 /* found implication x = 0 -> y = lb and x = 1 -> y = ub => aggregate y = lb + (ub-lb) * x */ 220 SCIP_CALL( SCIPreallocBufferArray(scip, &aggrvars, naggregations+1) ); 221 SCIP_CALL( SCIPreallocBufferArray(scip, &aggraggvars, naggregations+1) ); 222 SCIP_CALL( SCIPreallocBufferArray(scip, &aggrcoefs, naggregations+1) ); 223 SCIP_CALL( SCIPreallocBufferArray(scip, &aggrconsts, naggregations+1) ); 224 aggrvars[naggregations] = implvars[0][i0]; 225 aggraggvars[naggregations] = vars[v]; 226 aggrcoefs[naggregations] = implvarub - implvarlb; 227 aggrconsts[naggregations] = implvarlb; 228 229 SCIPdebugMsg(scip, " -> <%s> = 0 -> <%s> = %g, and <%s> = 1 -> <%s> = %g: aggregate <%s> = %g %+g<%s>\n", 230 SCIPvarGetName(vars[v]), SCIPvarGetName(implvars[0][i0]), implbounds[0][i0], 231 SCIPvarGetName(vars[v]), SCIPvarGetName(implvars[1][i1]), implbounds[1][i1], 232 SCIPvarGetName(aggrvars[naggregations]), aggrconsts[naggregations], aggrcoefs[naggregations], 233 SCIPvarGetName(aggraggvars[naggregations])); 234 235 naggregations++; 236 } 237 else if( impltypes[0][i0] == SCIP_BOUNDTYPE_LOWER 238 && SCIPisEQ(scip, implbounds[0][i0], implvarub) 239 && SCIPisEQ(scip, implbounds[1][i1], implvarlb) ) 240 { 241 /* found implication x = 0 -> y = ub and x = 1 -> y = lb => aggregate y = ub - (ub-lb) * x */ 242 SCIP_CALL( SCIPreallocBufferArray(scip, &aggrvars, naggregations+1) ); 243 SCIP_CALL( SCIPreallocBufferArray(scip, &aggraggvars, naggregations+1) ); 244 SCIP_CALL( SCIPreallocBufferArray(scip, &aggrcoefs, naggregations+1) ); 245 SCIP_CALL( SCIPreallocBufferArray(scip, &aggrconsts, naggregations+1) ); 246 aggrvars[naggregations] = implvars[0][i0]; 247 aggraggvars[naggregations] = vars[v]; 248 aggrcoefs[naggregations] = implvarlb - implvarub; 249 aggrconsts[naggregations] = implvarub; 250 251 SCIPdebugMsg(scip, " -> <%s> = 0 -> <%s> = %g, and <%s> = 1 -> <%s> = %g: aggregate <%s> = %g %+g<%s>\n", 252 SCIPvarGetName(vars[v]), SCIPvarGetName(implvars[0][i0]), implbounds[0][i0], 253 SCIPvarGetName(vars[v]), SCIPvarGetName(implvars[1][i1]), implbounds[1][i1], 254 SCIPvarGetName(aggrvars[naggregations]), aggrconsts[naggregations], aggrcoefs[naggregations], 255 SCIPvarGetName(aggraggvars[naggregations])); 256 257 naggregations++; 258 } 259 } 260 } 261 262 /* process the next implications */ 263 i0++; 264 i1++; 265 } 266 } 267 } 268 269 /**@todo check cliques of x == 0 and x == 1 for equal entries y == b -> fix y == !b */ 270 271 /* perform the bound changes 272 * 273 * Note, that we cannot assume y to be active (see var.c: varRemoveImplicsVbs()), but it should not cause any 274 * troubles as this case seems to be handled correctly in SCIPtightenVarLb/Ub(), unless the variable is 275 * multiaggregated, but this has been excluded above. 276 */ 277 for( v = 0; v < nbdchgs && *result != SCIP_CUTOFF; ++v ) 278 { 279 SCIP_Bool infeasible; 280 SCIP_Bool tightened; 281 282 assert(bdchgtypes != NULL); 283 assert(bdchgvars != NULL); 284 assert(bdchgvals != NULL); 285 286 if( bdchgtypes[v] == SCIP_BOUNDTYPE_LOWER ) 287 { 288 SCIP_CALL( SCIPtightenVarLb(scip, bdchgvars[v], bdchgvals[v], FALSE, &infeasible, &tightened) ); 289 } 290 else 291 { 292 SCIP_CALL( SCIPtightenVarUb(scip, bdchgvars[v], bdchgvals[v], FALSE, &infeasible, &tightened) ); 293 } 294 295 if( infeasible ) 296 { 297 SCIPdebugMsg(scip, " -> infeasible bound change <%s> %s %g\n", SCIPvarGetName(bdchgvars[v]), 298 bdchgtypes[v] == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", bdchgvals[v]); 299 *result = SCIP_CUTOFF; 300 } 301 else if( tightened ) 302 { 303 (*nchgbds)++; 304 *result = SCIP_SUCCESS; 305 } 306 } 307 308 /* perform the aggregations 309 * 310 * Note, that we cannot assume y to be active (see var.c: varRemoveImplicsVbs()), but it should not cause any 311 * troubles as this case seems to be handled correctly in SCIPaggregateVars(), unless the variable is 312 * multiaggregated, but this has been excluded above. 313 */ 314 for( v = 0; v < naggregations && *result != SCIP_CUTOFF; ++v ) 315 { 316 SCIP_Bool infeasible; 317 SCIP_Bool redundant; 318 SCIP_Bool aggregated; 319 320 assert(aggrvars != NULL); 321 assert(aggraggvars != NULL); 322 assert(aggrcoefs != NULL); 323 assert(aggrconsts != NULL); 324 325 /* aggregation y = const + coef * x => y - coef * x = const */ 326 SCIP_CALL( SCIPaggregateVars(scip, aggrvars[v], aggraggvars[v], 1.0, -aggrcoefs[v], aggrconsts[v], 327 &infeasible, &redundant, &aggregated) ); 328 if( infeasible ) 329 { 330 SCIPdebugMsg(scip, " -> infeasible aggregation <%s> = %g %+g<%s>\n", 331 SCIPvarGetName(aggrvars[v]), aggrconsts[v], aggrcoefs[v], SCIPvarGetName(aggraggvars[v])); 332 *result = SCIP_CUTOFF; 333 } 334 else if( aggregated ) 335 { 336 (*naggrvars)++; 337 *result = SCIP_SUCCESS; 338 } 339 } 340 341 /* free the storage buffers */ 342 SCIPfreeBufferArrayNull(scip, &aggrconsts); 343 SCIPfreeBufferArrayNull(scip, &aggrcoefs); 344 SCIPfreeBufferArrayNull(scip, &aggraggvars); 345 SCIPfreeBufferArrayNull(scip, &aggrvars); 346 SCIPfreeBufferArrayNull(scip, &bdchgvals); 347 SCIPfreeBufferArrayNull(scip, &bdchgtypes); 348 SCIPfreeBufferArrayNull(scip, &bdchgvars); 349 350 return SCIP_OKAY; 351 } 352 353 354 /* 355 * presolver specific interface methods 356 */ 357 358 /** creates the implics presolver and includes it in SCIP */ 359 SCIP_RETCODE SCIPincludePresolImplics( 360 SCIP* scip /**< SCIP data structure */ 361 ) 362 { 363 SCIP_PRESOL* presolptr; 364 365 /* include presolver */ 366 SCIP_CALL( SCIPincludePresolBasic(scip, &presolptr, PRESOL_NAME, PRESOL_DESC, PRESOL_PRIORITY, PRESOL_MAXROUNDS, PRESOL_TIMING, presolExecImplics, NULL) ); 367 368 assert(presolptr != NULL); 369 370 SCIP_CALL( SCIPsetPresolCopy(scip, presolptr, presolCopyImplics) ); 371 372 return SCIP_OKAY; 373 } 374