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_convertinttobin.c 26 * @ingroup DEFPLUGINS_PRESOL 27 * @brief presolver that converts integer variables to binaries 28 * @author Michael Winkler 29 * 30 * Converts integer variables at the beginning of Presolving into their binary representation. If necessary adds a 31 * bounding knapsack constraint. 32 * 33 */ 34 35 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 36 37 #include "blockmemshell/memory.h" 38 #include "scip/cons_knapsack.h" 39 #include "scip/debug.h" 40 #include "scip/presol_convertinttobin.h" 41 #include "scip/pub_message.h" 42 #include "scip/pub_misc.h" 43 #include "scip/pub_presol.h" 44 #include "scip/pub_var.h" 45 #include "scip/scip_cons.h" 46 #include "scip/scip_mem.h" 47 #include "scip/scip_message.h" 48 #include "scip/scip_numerics.h" 49 #include "scip/scip_param.h" 50 #include "scip/scip_presol.h" 51 #include "scip/scip_prob.h" 52 #include "scip/scip_var.h" 53 #include <string.h> 54 55 #define PRESOL_NAME "convertinttobin" 56 #define PRESOL_DESC "converts integer variables to binaries" 57 #define PRESOL_PRIORITY +6000000 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers) */ 58 #define PRESOL_MAXROUNDS 0 /**< maximal number of presolving rounds the presolver participates in (-1: no 59 * limit) */ 60 #define PRESOL_TIMING SCIP_PRESOLTIMING_FAST /* timing of the presolver (fast, medium, or exhaustive) */ 61 62 #define DEFAULT_MAXDOMAINSIZE SCIP_LONGINT_MAX /**< absolute value of maximum domain size which will be converted */ 63 #define DEFAULT_ONLYPOWERSOFTWO FALSE /**< should only integer variables with a domain size of 2^p - 1 be 64 * converted(, there we don't need an knapsack-constraint) */ 65 #define DEFAULT_SAMELOCKSINBOTHDIRECTIONS FALSE /**< should only integer variables with uplocks equals downlocks be converted */ 66 67 /** presolver data */ 68 struct SCIP_PresolData 69 { 70 SCIP_Longint maxdomainsize; /**< absolute value of maximum domain size */ 71 SCIP_Bool onlypoweroftwo; /**< should only integer variables with a domain size of 2^p - 1 be converted */ 72 SCIP_Bool samelocksinbothdirections; /**< should only integer variables with uplocks equals downlocks be converted */ 73 }; 74 75 /* 76 * Callback methods of presolver 77 */ 78 79 /** copy method for constraint handler plugins (called when SCIP copies plugins) */ 80 static 81 SCIP_DECL_PRESOLCOPY(presolCopyConvertinttobin) 82 { /*lint --e{715}*/ 83 assert(scip != NULL); 84 assert(presol != NULL); 85 assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0); 86 87 /* call inclusion method of presolver */ 88 SCIP_CALL( SCIPincludePresolConvertinttobin(scip) ); 89 90 return SCIP_OKAY; 91 } 92 93 /** destructor of presolver to free user data (called when SCIP is exiting) */ 94 static 95 SCIP_DECL_PRESOLFREE(presolFreeConvertinttobin) 96 { /*lint --e{715}*/ 97 SCIP_PRESOLDATA* presoldata; 98 99 /* free presolver data */ 100 presoldata = SCIPpresolGetData(presol); 101 assert(presoldata != NULL); 102 103 SCIPfreeBlockMemory(scip, &presoldata); 104 SCIPpresolSetData(presol, NULL); 105 106 return SCIP_OKAY; 107 } 108 109 /** presolving execution method */ 110 static 111 SCIP_DECL_PRESOLEXEC(presolExecConvertinttobin) 112 { /*lint --e{715}*/ 113 SCIP_VAR** scipvars; 114 SCIP_VAR** vars; 115 SCIP_PRESOLDATA* presoldata; 116 int nbinvars; 117 int nintvars; 118 int v; 119 120 assert(scip != NULL); 121 assert(presol != NULL); 122 assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0); 123 assert(result != NULL); 124 125 *result = SCIP_DIDNOTRUN; 126 127 /* get the problem variables */ 128 scipvars = SCIPgetVars(scip); 129 nbinvars = SCIPgetNBinVars(scip); 130 nintvars = SCIPgetNIntVars(scip); 131 if( nintvars == 0 ) 132 return SCIP_OKAY; 133 134 /* get presolver data */ 135 presoldata = SCIPpresolGetData(presol); 136 assert(presoldata != NULL); 137 138 *result = SCIP_DIDNOTFIND; 139 140 /* copy the integer variables into an own array, since adding binary variables affects the left-most slots in the 141 * array and thereby interferes with our search loop 142 */ 143 SCIP_CALL( SCIPduplicateBufferArray(scip, &vars, &scipvars[nbinvars], nintvars) ); 144 145 /* scan the integer variables for possible conversion into binaries; 146 * we have to collect the variables first in an own 147 */ 148 for( v = 0; v < nintvars; ++v ) 149 { 150 SCIP_VAR** newbinvars; 151 SCIP_Real* newbinvarcoeffs; 152 SCIP_Longint* weights; 153 SCIP_CONS* newcons; 154 SCIP_Real lb; 155 SCIP_Real ub; 156 SCIP_Longint domainsize; 157 char newbinvarname[SCIP_MAXSTRLEN]; 158 char newconsname[SCIP_MAXSTRLEN]; 159 int nnewbinvars; 160 int v2; 161 SCIP_Longint scalar; 162 SCIP_Bool infeasible; 163 SCIP_Bool aggregated; 164 SCIP_Bool noconsknapsack; 165 166 assert(SCIPvarGetType(vars[v]) == SCIP_VARTYPE_INTEGER); 167 168 /* skip variables which cannot be multi-aggregated */ 169 if( SCIPdoNotMultaggrVar(scip, vars[v]) ) 170 continue; 171 172 /* check for correct locks */ 173 if( presoldata->samelocksinbothdirections 174 && SCIPvarGetNLocksUpType(vars[v], SCIP_LOCKTYPE_MODEL) != SCIPvarGetNLocksDownType(vars[v], SCIP_LOCKTYPE_MODEL) ) 175 continue; 176 177 /* get variable's bounds */ 178 lb = SCIPvarGetLbGlobal(vars[v]); 179 ub = SCIPvarGetUbGlobal(vars[v]); 180 assert( SCIPisIntegral(scip, lb) ); 181 assert( SCIPisIntegral(scip, ub) ); 182 183 if( SCIPisInfinity(scip, ub - lb) ) 184 domainsize = SCIP_LONGINT_MAX; 185 else 186 domainsize = (SCIP_Longint) SCIPceil(scip, ub - lb); 187 188 assert(domainsize >= 0); 189 190 /* check for allowed domainsize */ 191 if( SCIPisInfinity(scip, -lb) || SCIPisInfinity(scip, ub) || domainsize > presoldata->maxdomainsize ) 192 continue; 193 194 /* check for domainsize is not 2^p - 1 if necessary */ 195 if( presoldata->onlypoweroftwo ) 196 { 197 /* stop if domainsize is not 2^p - 1*/ 198 SCIP_Longint tmp; 199 200 assert(domainsize < SCIP_LONGINT_MAX); 201 tmp = domainsize + 1; 202 203 while( tmp % 2 == 0 ) 204 tmp /= 2; 205 if( tmp != 1 ) 206 continue; 207 } 208 209 noconsknapsack = FALSE; 210 211 nnewbinvars = (int)SCIPfloor(scip, (log((SCIP_Real) domainsize)/log(2.0))) + 1; 212 213 SCIPdebugMsg(scip, "integer variable <%s> [%g,%g], domainsize %" SCIP_LONGINT_FORMAT "\n, <uplocks = %d, downlocks = %d will be 'binarized' by %d binary variables\n ", 214 SCIPvarGetName(vars[v]), lb, ub, domainsize, SCIPvarGetNLocksUpType(vars[v], SCIP_LOCKTYPE_MODEL), 215 SCIPvarGetNLocksDownType(vars[v], SCIP_LOCKTYPE_MODEL), nnewbinvars); 216 217 assert(nnewbinvars > 0); 218 219 scalar = (SCIP_Longint)pow(2.0, nnewbinvars); /*lint !e747*/ 220 /* because of rounding errors */ 221 if( scalar == domainsize ) 222 { 223 scalar *= 2; 224 nnewbinvars++; 225 } 226 else if( scalar == domainsize + 1 ) 227 noconsknapsack = TRUE; 228 229 assert(scalar > domainsize); 230 231 SCIP_CALL( SCIPallocBufferArray(scip, &newbinvars, nnewbinvars) ); 232 SCIP_CALL( SCIPallocBufferArray(scip, &newbinvarcoeffs, nnewbinvars) ); 233 SCIP_CALL( SCIPallocBufferArray(scip, &weights, nnewbinvars) ); 234 235 for( v2 = nnewbinvars - 1; v2 >= 0; --v2 ) 236 { 237 SCIPdebugMsg(scip, "creating for <%s>[%g,%g] %d. binary variable\n", SCIPvarGetName(vars[v]), lb, ub, v2); 238 239 /* create binary variable */ 240 (void) SCIPsnprintf(newbinvarname, SCIP_MAXSTRLEN, "%s_bin_%d", SCIPvarGetName(vars[v]), v2); 241 SCIP_CALL( SCIPcreateVar(scip, &newbinvars[v2], newbinvarname, 0.0, 1.0, 0.0, SCIP_VARTYPE_BINARY, 242 SCIPvarIsInitial(vars[v]), SCIPvarIsRemovable(vars[v]), NULL, NULL, NULL, NULL, NULL) ); 243 SCIP_CALL( SCIPaddVar(scip, newbinvars[v2]) ); 244 245 scalar /= 2; 246 assert(scalar > 0); 247 248 newbinvarcoeffs[v2] = (SCIP_Real)scalar; 249 weights[v2] = scalar; 250 } 251 252 #ifdef WITH_DEBUG_SOLUTION 253 /* set the debug solution values */ 254 if( SCIPdebugIsMainscip(scip) ) 255 { 256 SCIP_Real varval; 257 258 SCIP_CALL( SCIPdebugGetSolVal(scip, vars[v], &varval) ); 259 assert(SCIPisIntegral(scip, varval)); 260 261 if( SCIPisPositive(scip, varval) ) 262 { 263 SCIP_Real resvarval = varval; 264 265 for( v2 = nnewbinvars - 1; v2 >= 0; --v2 ) 266 { 267 assert(SCIPisPositive(scip, resvarval)); 268 assert(SCIPisIntegral(scip, resvarval)); 269 270 if( SCIPisLE(scip, newbinvarcoeffs[v2], resvarval) ) 271 { 272 SCIP_CALL( SCIPdebugAddSolVal(scip, newbinvars[v2], 1.0) ); 273 resvarval -= newbinvarcoeffs[v2]; 274 } 275 276 if( SCIPisZero(scip, resvarval) ) 277 break; 278 } 279 } 280 } 281 #endif 282 283 /* aggregate integer and binary variable */ 284 SCIP_CALL( SCIPmultiaggregateVar(scip, vars[v], nnewbinvars, newbinvars, (SCIP_Real*)newbinvarcoeffs, lb, &infeasible, &aggregated) ); 285 assert(!infeasible); 286 assert(aggregated); 287 288 (void) SCIPsnprintf(newconsname, SCIP_MAXSTRLEN, "%s_bin_knapsack", SCIPvarGetName(vars[v])); 289 290 if( !noconsknapsack ) 291 { 292 int nodd; 293 nodd = 0; 294 while( domainsize % 2 == 1 ) 295 { 296 nodd++; 297 domainsize = (domainsize - 1) / 2; 298 } 299 if( nodd > 0 ) 300 { 301 SCIP_Longint divisor; 302 303 divisor = (SCIP_Longint)pow(2.0, nodd); /*lint !e747*/ 304 assert(divisor >= 2); 305 306 for( v2 = nodd; v2 < nnewbinvars; ++v2 ) 307 { 308 weights[v2] /= divisor; 309 } 310 } 311 312 SCIP_CALL( SCIPcreateConsKnapsack(scip, &newcons, newconsname, nnewbinvars - nodd, &newbinvars[nodd], 313 &weights[nodd], domainsize, 314 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 315 SCIP_CALL( SCIPaddCons(scip, newcons) ); 316 SCIPdebugPrintCons(scip, newcons, NULL); 317 SCIP_CALL( SCIPreleaseCons(scip, &newcons) ); 318 } 319 320 for( v2 = nnewbinvars - 1; v2 >= 0; --v2 ) 321 { 322 /* release binary variable */ 323 SCIP_CALL( SCIPreleaseVar(scip, &newbinvars[v2]) ); 324 (*nchgvartypes)++; 325 } 326 327 SCIPfreeBufferArray(scip, &newbinvars); 328 SCIPfreeBufferArray(scip, &newbinvarcoeffs); 329 SCIPfreeBufferArray(scip, &weights); 330 331 if( aggregated ) /*lint !e774*/ 332 *result = SCIP_SUCCESS; 333 } 334 335 /* free temporary memory */ 336 SCIPfreeBufferArray(scip, &vars); 337 338 return SCIP_OKAY; 339 } 340 341 342 /* 343 * presolver specific interface methods 344 */ 345 346 /** creates the convertinttobin presolver and includes it in SCIP */ 347 SCIP_RETCODE SCIPincludePresolConvertinttobin( 348 SCIP* scip /**< SCIP data structure */ 349 ) 350 { 351 SCIP_PRESOLDATA* presoldata; 352 SCIP_PRESOL* presolptr; 353 354 /* create convertinttobin presolver data */ 355 SCIP_CALL( SCIPallocBlockMemory(scip, &presoldata) ); 356 357 presoldata->maxdomainsize = DEFAULT_MAXDOMAINSIZE; 358 presoldata->onlypoweroftwo = DEFAULT_ONLYPOWERSOFTWO; 359 360 /* include presolver */ 361 SCIP_CALL( SCIPincludePresolBasic(scip, &presolptr, PRESOL_NAME, PRESOL_DESC, PRESOL_PRIORITY, PRESOL_MAXROUNDS, PRESOL_TIMING, 362 presolExecConvertinttobin, 363 presoldata) ); 364 assert(presolptr != NULL); 365 366 SCIP_CALL( SCIPsetPresolCopy(scip, presolptr, presolCopyConvertinttobin) ); 367 SCIP_CALL( SCIPsetPresolFree(scip, presolptr, presolFreeConvertinttobin) ); 368 369 /* add convertinttobin presolver parameters */ 370 SCIP_CALL( SCIPaddLongintParam(scip, 371 "presolving/" PRESOL_NAME "/maxdomainsize", 372 "absolute value of maximum domain size for converting an integer variable to binaries variables", 373 &presoldata->maxdomainsize, TRUE, DEFAULT_MAXDOMAINSIZE, 0LL, SCIP_LONGINT_MAX, NULL, NULL) ); 374 375 /* add convertinttobin presolver parameters */ 376 SCIP_CALL( SCIPaddBoolParam(scip, 377 "presolving/" PRESOL_NAME "/onlypoweroftwo", 378 "should only integer variables with a domain size of 2^p - 1 be converted(, there we don't need an knapsack-constraint for restricting the sum of the binaries)", 379 &presoldata->onlypoweroftwo, TRUE, DEFAULT_ONLYPOWERSOFTWO, NULL, NULL) ); 380 381 /* add convertinttobin presolver parameters */ 382 SCIP_CALL( SCIPaddBoolParam(scip, 383 "presolving/" PRESOL_NAME "/samelocksinbothdirections", 384 "should only integer variables with uplocks equals downlocks be converted", 385 &presoldata->samelocksinbothdirections, TRUE, DEFAULT_SAMELOCKSINBOTHDIRECTIONS, NULL, NULL) ); 386 387 return SCIP_OKAY; 388 } 389