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_boundshift.c 26 * @ingroup DEFPLUGINS_PRESOL 27 * @brief presolver that converts variables with domain [a,b] to variables with domain [0,b-a] 28 * @author Stefan Heinz 29 * @author Michael Winkler 30 */ 31 32 /**@todo test this presolving step to decide whether to turn it in default mode on or off */ 33 34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 35 36 #include "blockmemshell/memory.h" 37 #include "scip/presol_boundshift.h" 38 #include "scip/pub_message.h" 39 #include "scip/pub_misc.h" 40 #include "scip/pub_presol.h" 41 #include "scip/pub_var.h" 42 #include "scip/scip_mem.h" 43 #include "scip/scip_message.h" 44 #include "scip/scip_numerics.h" 45 #include "scip/scip_param.h" 46 #include "scip/scip_presol.h" 47 #include "scip/scip_prob.h" 48 #include "scip/scip_var.h" 49 #include "scip/debug.h" 50 #include <string.h> 51 52 #define PRESOL_NAME "boundshift" 53 #define PRESOL_DESC "converts variables with domain [a,b] to variables with domain [0,b-a]" 54 #define PRESOL_PRIORITY 7900000 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers) */ 55 #define PRESOL_MAXROUNDS 0 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */ 56 #define PRESOL_TIMING SCIP_PRESOLTIMING_FAST /* timing of the presolver (fast, medium, or exhaustive) */ 57 58 #define MAXABSBOUND 1000.0 /**< maximum absolute variable bounds for aggregation */ 59 60 /* 61 * Default parameter settings 62 */ 63 64 #define DEFAULT_MAXSHIFT SCIP_LONGINT_MAX /**< absolute value of maximum shift */ 65 #define DEFAULT_FLIPPING TRUE /**< is flipping allowed? */ 66 #define DEFAULT_INTEGER TRUE /**< are only integer ranges shifted */ 67 68 /* 69 * Data structures 70 */ 71 72 /** presolver data */ 73 struct SCIP_PresolData 74 { 75 SCIP_Longint maxshift; /**< absolute value of maximum shift */ 76 SCIP_Bool flipping; /**< is flipping allowed? */ 77 SCIP_Bool integer; /**< shift only integer values? */ 78 }; 79 80 81 /* 82 * Local methods 83 */ 84 85 /* 86 * Callback methods of presolver 87 */ 88 89 /** copy method for constraint handler plugins (called when SCIP copies plugins) */ 90 static 91 SCIP_DECL_PRESOLCOPY(presolCopyBoundshift) 92 { /*lint --e{715}*/ 93 assert(scip != NULL); 94 assert(presol != NULL); 95 assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0); 96 97 /* call inclusion method of presolver */ 98 SCIP_CALL( SCIPincludePresolBoundshift(scip) ); 99 100 return SCIP_OKAY; 101 } 102 103 104 /** destructor of presolver to free user data (called when SCIP is exiting) */ 105 /**! [SnippetPresolFreeBoundshift] */ 106 static 107 SCIP_DECL_PRESOLFREE(presolFreeBoundshift) 108 { /*lint --e{715}*/ 109 SCIP_PRESOLDATA* presoldata; 110 111 /* free presolver data */ 112 presoldata = SCIPpresolGetData(presol); 113 assert(presoldata != NULL); 114 115 SCIPfreeBlockMemory(scip, &presoldata); 116 SCIPpresolSetData(presol, NULL); 117 118 return SCIP_OKAY; 119 } 120 /**! [SnippetPresolFreeBoundshift] */ 121 122 123 /** presolving execution method */ 124 static 125 SCIP_DECL_PRESOLEXEC(presolExecBoundshift) 126 { /*lint --e{715}*/ 127 SCIP_PRESOLDATA* presoldata; 128 SCIP_VAR** scipvars; 129 SCIP_VAR** vars; 130 int nbinvars; 131 int nvars; 132 int v; 133 134 assert(scip != NULL); 135 assert(presol != NULL); 136 assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0); 137 assert(result != NULL); 138 139 *result = SCIP_DIDNOTRUN; 140 141 if( SCIPdoNotAggr(scip) ) 142 return SCIP_OKAY; 143 144 /* get presolver data */ 145 presoldata = SCIPpresolGetData(presol); 146 assert(presoldata != NULL); 147 148 /* get the problem variables */ 149 scipvars = SCIPgetVars(scip); 150 nbinvars = SCIPgetNBinVars(scip); 151 nvars = SCIPgetNVars(scip) - nbinvars; 152 153 if( nvars == 0 ) 154 return SCIP_OKAY; 155 156 *result = SCIP_DIDNOTFIND; 157 158 /* copy the integer/continuous variables into an own array, since adding new variables affects the left-most slots in 159 * the array and thereby interferes with our search loop 160 */ 161 SCIP_CALL( SCIPduplicateBufferArray(scip, &vars, &scipvars[nbinvars], nvars) ); 162 163 /* scan the integer, implicit, and continuous variables for possible conversion */ 164 for( v = nvars - 1; v >= 0; --v ) 165 { 166 SCIP_VAR* var = vars[v]; 167 SCIP_Real lb; 168 SCIP_Real ub; 169 170 assert(SCIPvarGetType(var) != SCIP_VARTYPE_BINARY); 171 172 /* do not shift non-active (fixed or (multi-)aggregated) variables */ 173 if( !SCIPvarIsActive(var) ) 174 continue; 175 176 /* get current variable's bounds */ 177 lb = SCIPvarGetLbGlobal(var); 178 ub = SCIPvarGetUbGlobal(var); 179 180 /* it can happen that the variable bounds of integer variables have not been propagated yet or contain 181 * some small noise; this will result in an aggregation that might trigger assertions when updating bounds of 182 * aggregated variables (see #1817) 183 */ 184 if( SCIPvarIsIntegral(var) ) 185 { 186 assert(SCIPisIntegral(scip, lb)); 187 assert(SCIPisIntegral(scip, ub)); 188 189 lb = SCIPadjustedVarLb(scip, var, lb); 190 ub = SCIPadjustedVarUb(scip, var, ub); 191 } 192 193 assert( SCIPisLE(scip, lb, ub) ); 194 if( SCIPisEQ(scip, lb, ub) ) 195 continue; 196 if( presoldata->integer && !SCIPisIntegral(scip, ub - lb) ) 197 continue; 198 199 /* check if bounds are shiftable */ 200 if( !SCIPisEQ(scip, lb, 0.0) && /* lower bound != 0.0 */ 201 SCIPisLT(scip, ub, SCIPinfinity(scip)) && /* upper bound != infinity */ 202 SCIPisGT(scip, lb, -SCIPinfinity(scip)) && /* lower bound != -infinity */ 203 SCIPisLT(scip, ub - lb, (SCIP_Real) presoldata->maxshift) && /* less than max shifting */ 204 SCIPisLE(scip, REALABS(lb), MAXABSBOUND) && /* ensures a small constant in aggregation */ 205 SCIPisLE(scip, REALABS(ub), MAXABSBOUND) ) /* ensures a small constant in aggregation */ 206 { 207 SCIP_VAR* newvar; 208 char newvarname[SCIP_MAXSTRLEN]; 209 SCIP_Bool infeasible; 210 SCIP_Bool redundant; 211 SCIP_Bool aggregated; 212 213 SCIPdebugMsg(scip, "convert range <%s>[%g,%g] to [%g,%g]\n", SCIPvarGetName(var), lb, ub, 0.0, (ub - lb) ); 214 215 /* create new variable */ 216 (void) SCIPsnprintf(newvarname, SCIP_MAXSTRLEN, "%s_shift", SCIPvarGetName(var)); 217 SCIP_CALL( SCIPcreateVar(scip, &newvar, newvarname, 0.0, (ub - lb), 0.0, SCIPvarGetType(var), 218 SCIPvarIsInitial(var), SCIPvarIsRemovable(var), NULL, NULL, NULL, NULL, NULL) ); 219 SCIP_CALL( SCIPaddVar(scip, newvar) ); 220 221 #ifdef WITH_DEBUG_SOLUTION 222 if( SCIPdebugIsMainscip(scip) ) 223 { 224 /* calculate and store debug solution value of shift variable */ 225 SCIP_Real val; 226 227 SCIP_CALL( SCIPdebugGetSolVal(scip, var, &val) ); 228 SCIPdebugMsg(scip, "debug solution value: <%s> = %g", SCIPvarGetName(var), val); 229 230 if( presoldata->flipping ) 231 { 232 if( REALABS(ub) < REALABS(lb) ) 233 val = ub - val; 234 else 235 val = val - lb; 236 } 237 else 238 { 239 val = val - lb; 240 } 241 SCIPdebugMsgPrint(scip, " -> <%s> = %g\n", SCIPvarGetName(newvar), val); 242 243 SCIP_CALL( SCIPdebugAddSolVal(scip, newvar, val) ); 244 } 245 #endif 246 247 /* aggregate old variable with new variable */ 248 if( presoldata->flipping ) 249 { 250 if( REALABS(ub) < REALABS(lb) ) 251 { 252 SCIP_CALL( SCIPaggregateVars(scip, var, newvar, 1.0, 1.0, ub, &infeasible, &redundant, &aggregated) ); 253 } 254 else 255 { 256 SCIP_CALL( SCIPaggregateVars(scip, var, newvar, 1.0, -1.0, lb, &infeasible, &redundant, &aggregated) ); 257 } 258 } 259 else 260 { 261 SCIP_CALL( SCIPaggregateVars(scip, var, newvar, 1.0, -1.0, lb, &infeasible, &redundant, &aggregated) ); 262 } 263 264 if( infeasible ) 265 *result = SCIP_CUTOFF; 266 else 267 { 268 assert(redundant); 269 assert(aggregated); 270 SCIPdebugMsg(scip, "var <%s> with bounds [%f,%f] has obj %f\n", 271 SCIPvarGetName(newvar), SCIPvarGetLbGlobal(newvar), SCIPvarGetUbGlobal(newvar), SCIPvarGetObj(newvar)); 272 273 /* take care of statistics */ 274 (*naggrvars)++; 275 *result = SCIP_SUCCESS; 276 } 277 278 /* release variable */ 279 SCIP_CALL( SCIPreleaseVar(scip, &newvar) ); 280 } 281 } 282 283 /* free temporary memory */ 284 SCIPfreeBufferArray(scip, &vars); 285 286 return SCIP_OKAY; 287 } 288 289 290 /* 291 * presolver specific interface methods 292 */ 293 294 /** creates the boundshift presolver and includes it in SCIP */ 295 SCIP_RETCODE SCIPincludePresolBoundshift( 296 SCIP* scip /**< SCIP data structure */ 297 ) 298 { 299 SCIP_PRESOLDATA* presoldata; 300 SCIP_PRESOL* presolptr; 301 302 /* create boundshift presolver data */ 303 SCIP_CALL( SCIPallocBlockMemory(scip, &presoldata) ); 304 305 /* include presolver */ 306 SCIP_CALL( SCIPincludePresolBasic(scip, &presolptr, PRESOL_NAME, PRESOL_DESC, PRESOL_PRIORITY, PRESOL_MAXROUNDS, PRESOL_TIMING, 307 presolExecBoundshift, 308 presoldata) ); 309 310 assert(presolptr != NULL); 311 312 SCIP_CALL( SCIPsetPresolCopy(scip, presolptr, presolCopyBoundshift) ); 313 SCIP_CALL( SCIPsetPresolFree(scip, presolptr, presolFreeBoundshift) ); 314 315 /* add probing presolver parameters */ 316 SCIP_CALL( SCIPaddLongintParam(scip, 317 "presolving/boundshift/maxshift", 318 "absolute value of maximum shift", 319 &presoldata->maxshift, TRUE, DEFAULT_MAXSHIFT, 0LL, SCIP_LONGINT_MAX, NULL, NULL) ); 320 321 SCIP_CALL( SCIPaddBoolParam(scip, 322 "presolving/boundshift/flipping", 323 "is flipping allowed (multiplying with -1)?", 324 &presoldata->flipping, TRUE, DEFAULT_FLIPPING, NULL, NULL) ); 325 326 SCIP_CALL( SCIPaddBoolParam(scip, 327 "presolving/boundshift/integer", 328 "shift only integer ranges?", 329 &presoldata->integer, TRUE, DEFAULT_INTEGER, NULL, NULL) ); 330 331 return SCIP_OKAY; 332 } 333