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_trivial.c 26 * @ingroup DEFPLUGINS_PRESOL 27 * @brief trivial presolver: round fractional bounds on integer variables, fix variables with equal bounds 28 * @author Tobias Achterberg 29 */ 30 31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 32 33 #include "scip/presol_trivial.h" 34 #include "scip/pub_message.h" 35 #include "scip/pub_presol.h" 36 #include "scip/pub_var.h" 37 #include "scip/scip_message.h" 38 #include "scip/scip_numerics.h" 39 #include "scip/scip_presol.h" 40 #include "scip/scip_prob.h" 41 #include "scip/scip_var.h" 42 #include <string.h> 43 44 #define PRESOL_NAME "trivial" 45 #define PRESOL_DESC "round fractional bounds on integers, fix variables with equal bounds" 46 #define PRESOL_PRIORITY +9000000 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers) */ 47 #define PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */ 48 #define PRESOL_TIMING SCIP_PRESOLTIMING_FAST /* timing of the presolver (fast, medium, or exhaustive) */ 49 50 #ifdef FIXSIMPLEVALUE 51 #define MAXDNOM 10000LL /**< maximal denominator for simple rational fixed values */ 52 #endif 53 54 55 /* 56 * Callback methods of presolver 57 */ 58 59 /** copy method for constraint handler plugins (called when SCIP copies plugins) */ 60 static 61 SCIP_DECL_PRESOLCOPY(presolCopyTrivial) 62 { /*lint --e{715}*/ 63 assert(scip != NULL); 64 assert(presol != NULL); 65 assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0); 66 67 /* call inclusion method of presolver */ 68 SCIP_CALL( SCIPincludePresolTrivial(scip) ); 69 70 return SCIP_OKAY; 71 } 72 73 74 /** presolving execution method */ 75 static 76 SCIP_DECL_PRESOLEXEC(presolExecTrivial) 77 { /*lint --e{715}*/ 78 SCIP_VAR** vars; 79 int nvars; 80 int v; 81 82 assert(result != NULL); 83 84 *result = SCIP_DIDNOTFIND; 85 86 /* get the problem variables */ 87 vars = SCIPgetVars(scip); 88 nvars = SCIPgetNVars(scip); 89 90 /* scan the variables for trivial bound reductions 91 * (loop backwards, since a variable fixing can change the current and the subsequent slots in the vars array) 92 */ 93 for( v = nvars-1; v >= 0; --v ) 94 { 95 SCIP_Real lb; 96 SCIP_Real ub; 97 SCIP_Bool infeasible; 98 SCIP_Bool fixed; 99 100 /* get variable's bounds */ 101 lb = SCIPvarGetLbGlobal(vars[v]); 102 ub = SCIPvarGetUbGlobal(vars[v]); 103 104 /* is variable integral? */ 105 if( SCIPvarGetType(vars[v]) != SCIP_VARTYPE_CONTINUOUS ) 106 { 107 SCIP_Real newlb; 108 SCIP_Real newub; 109 110 /* round fractional bounds on integer variables */ 111 newlb = SCIPfeasCeil(scip, lb); 112 newub = SCIPfeasFloor(scip, ub); 113 114 /* check bounds on variable for infeasibility */ 115 if( newlb > newub + 0.5 ) 116 { 117 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, 118 "problem infeasible: integral variable <%s> has bounds [%.17f,%.17f] rounded to [%.17f,%.17f]\n", 119 SCIPvarGetName(vars[v]), lb, ub, newlb, newub); 120 *result = SCIP_CUTOFF; 121 return SCIP_OKAY; 122 } 123 124 /* fix variables with equal bounds */ 125 if( newlb > newub - 0.5 ) 126 { 127 SCIPdebugMsg(scip, "fixing integral variable <%s>: [%.17f,%.17f] -> [%.17f,%.17f]\n", SCIPvarGetName(vars[v]), lb, ub, newlb, newub); 128 SCIP_CALL( SCIPfixVar(scip, vars[v], newlb, &infeasible, &fixed) ); 129 if( infeasible ) 130 { 131 SCIPdebugMsg(scip, " -> infeasible fixing\n"); 132 *result = SCIP_CUTOFF; 133 return SCIP_OKAY; 134 } 135 assert(fixed); 136 (*nfixedvars)++; 137 } 138 else 139 { 140 /* round fractional bounds */ 141 if( !SCIPisFeasEQ(scip, lb, newlb) ) 142 { 143 SCIPdebugMsg(scip, "rounding lower bound of integral variable <%s>: [%.17f,%.17f] -> [%.17f,%.17f]\n", 144 SCIPvarGetName(vars[v]), lb, ub, newlb, ub); 145 SCIP_CALL( SCIPchgVarLb(scip, vars[v], newlb) ); 146 (*nchgbds)++; 147 } 148 if( !SCIPisFeasEQ(scip, ub, newub) ) 149 { 150 SCIPdebugMsg(scip, "rounding upper bound of integral variable <%s>: [%.17f,%.17f] -> [%.17f,%.17f]\n", 151 SCIPvarGetName(vars[v]), newlb, ub, newlb, newub); 152 SCIP_CALL( SCIPchgVarUb(scip, vars[v], newub) ); 153 (*nchgbds)++; 154 } 155 } 156 } 157 else 158 { 159 /* check bounds on continuous variable for infeasibility */ 160 if( SCIPisFeasGT(scip, lb, ub) ) 161 { 162 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, 163 "problem infeasible: continuous variable <%s> has bounds [%.17f,%.17f]\n", 164 SCIPvarGetName(vars[v]), lb, ub); 165 *result = SCIP_CUTOFF; 166 return SCIP_OKAY; 167 } 168 169 /* fix variables with equal bounds */ 170 if( SCIPisEQ(scip, lb, ub) ) 171 { 172 SCIP_Real fixval; 173 174 #ifdef FIXSIMPLEVALUE 175 fixval = SCIPselectSimpleValue(lb - 0.9 * SCIPepsilon(scip), ub + 0.9 * SCIPepsilon(scip), MAXDNOM); 176 #else 177 /* prefer integral values (especially 0) over midpoint */ 178 fixval = SCIPround(scip, lb); 179 if( fixval < lb || fixval > ub ) 180 fixval = (lb + ub)/2; 181 #endif 182 SCIPdebugMsg(scip, "fixing continuous variable <%s>[%.17f,%.17f] to %.17f\n", SCIPvarGetName(vars[v]), lb, ub, fixval); 183 SCIP_CALL( SCIPfixVar(scip, vars[v], fixval, &infeasible, &fixed) ); 184 if( infeasible ) 185 { 186 SCIPdebugMsg(scip, " -> infeasible fixing\n"); 187 *result = SCIP_CUTOFF; 188 return SCIP_OKAY; 189 } 190 assert(fixed); 191 (*nfixedvars)++; 192 } 193 } 194 } 195 196 return SCIP_OKAY; 197 } 198 199 200 /* 201 * presolver specific interface methods 202 */ 203 204 /** creates the trivial presolver and includes it in SCIP */ 205 SCIP_RETCODE SCIPincludePresolTrivial( 206 SCIP* scip /**< SCIP data structure */ 207 ) 208 { 209 SCIP_PRESOL* presolptr; 210 211 /* include presolver */ 212 SCIP_CALL( SCIPincludePresolBasic(scip, &presolptr, PRESOL_NAME, PRESOL_DESC, PRESOL_PRIORITY, PRESOL_MAXROUNDS, PRESOL_TIMING, presolExecTrivial, NULL) ); 213 214 assert(presolptr != NULL); 215 216 SCIP_CALL( SCIPsetPresolCopy(scip, presolptr, presolCopyTrivial) ); 217 218 return SCIP_OKAY; 219 } 220