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 prop_dualfix.c 26 * @ingroup DEFPLUGINS_PROP 27 * @brief fixing roundable variables to best bound 28 * @author Tobias Achterberg 29 * @author Stefan Heinz 30 */ 31 32 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 33 34 #include "scip/prop_dualfix.h" 35 #include "scip/pub_message.h" 36 #include "scip/pub_prop.h" 37 #include "scip/pub_var.h" 38 #include "scip/scip_general.h" 39 #include "scip/scip_message.h" 40 #include "scip/scip_numerics.h" 41 #include "scip/scip_prob.h" 42 #include "scip/scip_probing.h" 43 #include "scip/scip_prop.h" 44 #include "scip/scip_tree.h" 45 #include "scip/scip_var.h" 46 #include <string.h> 47 48 #define PROP_NAME "dualfix" 49 #define PROP_DESC "roundable variables dual fixing" 50 #define PROP_TIMING SCIP_PROPTIMING_BEFORELP 51 #define PROP_PRIORITY +8000000 /**< propagation priority */ 52 #define PROP_FREQ 0 /**< propagation frequency */ 53 #define PROP_DELAY FALSE /**< should propagation method be delayed, if other propagators found 54 * reductions? */ 55 #define PROP_PRESOL_PRIORITY +8000000 /**< priority of the propagator (>= 0: before, < 0: after constraint handlers) */ 56 #define PROP_PRESOL_MAXROUNDS -1 /**< maximal number of propving rounds the propver participates in (-1: no limit) */ 57 #define PROP_PRESOLTIMING SCIP_PRESOLTIMING_FAST /* timing of the presolving method (fast, medium, or exhaustive) */ 58 59 60 /**@name Local methods 61 * 62 * @{ 63 */ 64 65 /** perform dual presolving */ 66 static 67 SCIP_RETCODE performDualfix( 68 SCIP* scip, /**< SCIP data structure */ 69 int* nfixedvars, /**< pointer to store number of fixed variables */ 70 SCIP_Bool* unbounded, /**< pointer to store if an unboundness was detected */ 71 SCIP_Bool* cutoff /**< pointer to store if a cutoff was detected */ 72 ) 73 { 74 SCIP_VAR** vars; 75 int nvars; 76 int v; 77 78 /* get active problem variables */ 79 vars = SCIPgetVars(scip); 80 nvars = SCIPgetNVars(scip); 81 82 /* look for fixable variables 83 * loop backwards, since a variable fixing can change the current and the subsequent slots in the vars array 84 */ 85 for( v = nvars - 1; v >= 0; --v ) 86 { 87 SCIP_VAR* var; 88 SCIP_Real bound; 89 SCIP_Real obj; 90 SCIP_Bool infeasible; 91 SCIP_Bool fixed; 92 93 var = vars[v]; 94 assert(var != NULL); 95 96 /* don't perform dual presolving operations on deleted variables */ 97 if( SCIPvarIsDeleted(var) ) 98 continue; 99 100 /* ignore already fixed variables */ 101 if( SCIPisEQ(scip, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) ) 102 continue; 103 104 obj = SCIPvarGetObj(var); 105 106 /* if the objective coefficient of the variable is 0 and it may be rounded both 107 * up and down, then fix it to the closest feasible value to 0 */ 108 if( SCIPisZero(scip, obj) && SCIPvarMayRoundDown(var) && SCIPvarMayRoundUp(var) ) 109 { 110 SCIP_Real roundbound; 111 112 bound = SCIPvarGetLbGlobal(var); 113 if( SCIPisLT(scip, bound, 0.0) ) 114 { 115 if( SCIPisLE(scip, 0.0, SCIPvarGetUbGlobal(var)) ) 116 bound = 0.0; 117 else 118 { 119 /* try to take an integer value, only for polishing */ 120 roundbound = SCIPfloor(scip, SCIPvarGetUbGlobal(var)); 121 122 if( roundbound < bound ) 123 bound = SCIPvarGetUbGlobal(var); 124 else 125 bound = roundbound; 126 } 127 } 128 else 129 { 130 /* try to take an integer value, only for polishing */ 131 roundbound = SCIPceil(scip, bound); 132 133 if( roundbound < SCIPvarGetUbGlobal(var) ) 134 bound = roundbound; 135 } 136 SCIPdebugMsg(scip, "fixing variable <%s> with objective 0 to %g\n", SCIPvarGetName(var), bound); 137 } 138 else 139 { 140 /* if it is always possible to round variable in direction of objective value, fix it to its proper bound */ 141 if( SCIPvarMayRoundDown(var) && !SCIPisNegative(scip, obj) ) 142 { 143 bound = SCIPvarGetLbGlobal(var); 144 if ( SCIPisInfinity(scip, -bound) ) 145 { 146 /* variable can be fixed to -infinity */ 147 if ( SCIPgetStage(scip) > SCIP_STAGE_PRESOLVING ) 148 { 149 /* Fixing variables to infinity is not allowed after presolving, since LP-solvers cannot handle this 150 * consistently. We thus have to ignore this (should better be handled in presolving). */ 151 continue; 152 } 153 if ( SCIPisZero(scip, obj) && SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) == 1 ) 154 { 155 /* Variable is only contained in one constraint: we hope that the corresponding constraint handler is 156 * clever enough to set/aggregate the variable to something more useful than -infinity and do nothing 157 * here. */ 158 continue; 159 } 160 } 161 SCIPdebugMsg(scip, "fixing variable <%s> with objective %g and %d uplocks to lower bound %g\n", 162 SCIPvarGetName(var), SCIPvarGetObj(var), SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL), bound); 163 } 164 else if( SCIPvarMayRoundUp(var) && !SCIPisPositive(scip, obj) ) 165 { 166 bound = SCIPvarGetUbGlobal(var); 167 if ( SCIPisInfinity(scip, bound) ) 168 { 169 /* variable can be fixed to infinity */ 170 if ( SCIPgetStage(scip) > SCIP_STAGE_PRESOLVING ) 171 { 172 /* Fixing variables to infinity is not allowed after presolving, since LP-solvers cannot handle this 173 * consistently. We thus have to ignore this (should better be handled in presolving). */ 174 continue; 175 } 176 if ( SCIPisZero(scip, obj) && SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) == 1 ) 177 { 178 /* Variable is only contained in one constraint: we hope that the corresponding constraint handler is 179 * clever enough to set/aggregate the variable to something more useful than +infinity and do nothing 180 * here */ 181 continue; 182 } 183 } 184 SCIPdebugMsg(scip, "fixing variable <%s> with objective %g and %d downlocks to upper bound %g\n", 185 SCIPvarGetName(var), SCIPvarGetObj(var), SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL), bound); 186 } 187 else 188 continue; 189 } 190 191 if( SCIPisInfinity(scip, REALABS(bound)) && !SCIPisZero(scip, obj) ) 192 { 193 SCIPdebugMsg(scip, " -> unbounded fixing\n"); 194 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, 195 "problem infeasible or unbounded: variable <%s> with objective %.15g can be made infinitely %s\n", 196 SCIPvarGetName(var), SCIPvarGetObj(var), bound < 0.0 ? "small" : "large"); 197 *unbounded = TRUE; 198 return SCIP_OKAY; 199 } 200 201 /* apply the fixing */ 202 SCIPdebugMsg(scip, "apply fixing of variable %s to %g\n", SCIPvarGetName(var), bound); 203 SCIP_CALL( SCIPfixVar(scip, var, bound, &infeasible, &fixed) ); 204 205 if( infeasible ) 206 { 207 SCIPdebugMsg(scip, " -> infeasible fixing\n"); 208 *cutoff = TRUE; 209 return SCIP_OKAY; 210 } 211 212 /* SCIPfixVar only changes bounds if not already feaseq. 213 * Only if in presolve and not probing, variables will always be fixed. 214 */ 215 assert(fixed || (SCIPisFeasEQ(scip, bound, SCIPvarGetLbLocal(var)) 216 && SCIPisFeasEQ(scip, bound, SCIPvarGetUbLocal(var)))); 217 (*nfixedvars)++; 218 } 219 220 return SCIP_OKAY; 221 } 222 223 /**@} */ 224 225 /**@name Callback methods 226 * 227 * @{ 228 */ 229 230 /** copy method for constraint handler plugins (called when SCIP copies plugins) */ 231 static 232 SCIP_DECL_PROPCOPY(propCopyDualfix) 233 { /*lint --e{715}*/ 234 assert(scip != NULL); 235 assert(prop != NULL); 236 assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0); 237 238 /* call inclusion method of propagator */ 239 SCIP_CALL( SCIPincludePropDualfix(scip) ); 240 241 return SCIP_OKAY; 242 } 243 244 /** presolving method of propagator */ 245 static 246 SCIP_DECL_PROPPRESOL(propPresolDualfix) 247 { /*lint --e{715}*/ 248 SCIP_Bool cutoff; 249 SCIP_Bool unbounded; 250 int oldnfixedvars; 251 252 assert(prop != NULL); 253 assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0); 254 assert(result != NULL); 255 256 *result = SCIP_DIDNOTRUN; 257 258 if( !SCIPallowStrongDualReds(scip) ) 259 return SCIP_OKAY; 260 261 cutoff = FALSE; 262 unbounded = FALSE; 263 oldnfixedvars = *nfixedvars; 264 265 SCIP_CALL( performDualfix(scip, nfixedvars, &unbounded, &cutoff) ); 266 267 /* evaluate propagation result */ 268 if( cutoff ) 269 *result = SCIP_CUTOFF; 270 else if( unbounded ) 271 *result = SCIP_UNBOUNDED; 272 else if( *nfixedvars > oldnfixedvars ) 273 *result = SCIP_SUCCESS; 274 else 275 *result = SCIP_DIDNOTFIND; 276 277 return SCIP_OKAY; 278 } 279 280 /** execution method of propagator */ 281 static 282 SCIP_DECL_PROPEXEC(propExecDualfix) 283 { /*lint --e{715}*/ 284 int nfixedvars; 285 SCIP_Bool cutoff; 286 SCIP_Bool unbounded; 287 288 assert(prop != NULL); 289 assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0); 290 assert(result != NULL); 291 292 *result = SCIP_DIDNOTRUN; 293 294 /** @warning Don't run in probing or in repropagation since this can lead to wrong conclusion 295 * 296 * do not run if propagation w.r.t. current objective is not allowed 297 */ 298 if( SCIPinProbing(scip) || SCIPinRepropagation(scip) || !SCIPallowStrongDualReds(scip) ) 299 return SCIP_OKAY; 300 301 cutoff = FALSE; 302 unbounded = FALSE; 303 nfixedvars = 0; 304 305 SCIP_CALL( performDualfix(scip, &nfixedvars, &unbounded, &cutoff) ); 306 307 /* evaluate propagation result */ 308 if( cutoff ) 309 *result = SCIP_CUTOFF; 310 else if( unbounded ) 311 *result = SCIP_UNBOUNDED; 312 else if( nfixedvars > 0 ) 313 *result = SCIP_REDUCEDDOM; 314 else 315 *result = SCIP_DIDNOTFIND; 316 317 return SCIP_OKAY; 318 } 319 320 321 /**@} */ 322 323 324 /** creates the dual fixing propagator and includes it in SCIP */ 325 SCIP_RETCODE SCIPincludePropDualfix( 326 SCIP* scip /**< SCIP data structure */ 327 ) 328 { 329 SCIP_PROP* prop; 330 331 /* include propagator */ 332 SCIP_CALL( SCIPincludePropBasic(scip, &prop, PROP_NAME, PROP_DESC, PROP_PRIORITY, PROP_FREQ, PROP_DELAY, PROP_TIMING, propExecDualfix, NULL) ); 333 assert(prop != NULL); 334 335 SCIP_CALL( SCIPsetPropCopy(scip, prop, propCopyDualfix) ); 336 SCIP_CALL( SCIPsetPropPresol(scip, prop, propPresolDualfix, PROP_PRESOL_PRIORITY, PROP_PRESOL_MAXROUNDS, PROP_PRESOLTIMING) ); 337 338 return SCIP_OKAY; 339 } 340