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 heur_trivial.c 26 * @ingroup DEFPLUGINS_HEUR 27 * @brief trivial primal heuristic 28 * @author Timo Berthold 29 */ 30 31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 32 33 #include "scip/heur_trivial.h" 34 #include "scip/pub_heur.h" 35 #include "scip/pub_message.h" 36 #include "scip/pub_var.h" 37 #include "scip/scip_heur.h" 38 #include "scip/scip_message.h" 39 #include "scip/scip_numerics.h" 40 #include "scip/scip_prob.h" 41 #include "scip/scip_sol.h" 42 #include "scip/scip_solvingstats.h" 43 #include <string.h> 44 45 #define HEUR_NAME "trivial" 46 #define HEUR_DESC "start heuristic which tries some trivial solutions" 47 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_TRIVIAL 48 #define HEUR_PRIORITY 10000 49 #define HEUR_FREQ 0 50 #define HEUR_FREQOFS 0 51 #define HEUR_MAXDEPTH -1 52 #define HEUR_TIMING SCIP_HEURTIMING_BEFOREPRESOL | SCIP_HEURTIMING_BEFORENODE 53 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */ 54 55 /* 56 * Local methods 57 */ 58 59 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */ 60 static 61 SCIP_DECL_HEURCOPY(heurCopyTrivial) 62 { /*lint --e{715}*/ 63 assert(scip != NULL); 64 assert(heur != NULL); 65 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 66 67 /* call inclusion method of primal heuristic */ 68 SCIP_CALL( SCIPincludeHeurTrivial(scip) ); 69 70 return SCIP_OKAY; 71 } 72 73 74 /** execution method of primal heuristic */ 75 static 76 SCIP_DECL_HEUREXEC(heurExecTrivial) 77 { /*lint --e{715}*/ 78 SCIP_VAR** vars; 79 SCIP_SOL* zerosol; /* solution where all variables are set next to zero within bounds */ 80 SCIP_SOL* lbsol; /* solution where all variables are set to their lower bounds */ 81 SCIP_SOL* ubsol; /* solution where all variables are set to their upper bounds */ 82 SCIP_SOL* locksol; /* solution where all variables are set to the bound with the fewer locks */ 83 SCIP_Real large; 84 SCIP_Bool difflb; 85 SCIP_Bool diffub; 86 SCIP_Bool difflock; 87 SCIP_Bool success; 88 int nvars; 89 int i; 90 91 *result = SCIP_DIDNOTFIND; 92 93 /* initialize data structure */ 94 SCIP_CALL( SCIPcreateSol(scip, &zerosol, heur) ); 95 SCIP_CALL( SCIPcreateSol(scip, &lbsol, heur) ); 96 SCIP_CALL( SCIPcreateSol(scip, &ubsol, heur) ); 97 SCIP_CALL( SCIPcreateSol(scip, &locksol, heur) ); 98 99 /* determine large value to set variables to */ 100 large = SCIPround(scip, MIN(1.0 / SCIPfeastol(scip), SCIPgetHugeValue(scip)) / 10.0); /*lint !e666 */ 101 102 /* check zero solution once */ 103 difflb = FALSE; 104 diffub = FALSE; 105 difflock = FALSE; 106 107 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) ); 108 assert(vars != NULL || nvars == 0); 109 110 for( i = 0; i < nvars; ++i ) 111 { 112 SCIP_Real lb; 113 SCIP_Real ub; 114 SCIP_Real zeroval; 115 SCIP_Real solval; 116 117 assert(vars != NULL); /* this assert is needed for flexelint */ 118 119 lb = SCIPvarGetLbLocal(vars[i]); 120 ub = SCIPvarGetUbLocal(vars[i]); 121 122 /* if problem is obviously infeasible due to empty domain, stop */ 123 if( SCIPisFeasGT(scip, lb, ub) ) 124 goto TERMINATE; 125 126 /* set bounds to sufficient large value */ 127 if( SCIPisInfinity(scip, -lb) ) 128 lb = MIN(-large, ub); 129 if( SCIPisInfinity(scip, ub) ) 130 ub = MAX(large, lb); 131 132 /* set value next to zero within bounds */ 133 zeroval = MAX(MIN(0.0, ub), lb); 134 135 /* set value to the bound with fewer locks, if tie choose an average value */ 136 if( SCIPvarGetNLocksDownType(vars[i], SCIP_LOCKTYPE_MODEL) < SCIPvarGetNLocksUpType(vars[i], SCIP_LOCKTYPE_MODEL) ) 137 solval = lb; 138 else if( SCIPvarGetNLocksDownType(vars[i], SCIP_LOCKTYPE_MODEL) > SCIPvarGetNLocksUpType(vars[i], SCIP_LOCKTYPE_MODEL) ) 139 solval = ub; 140 else 141 { 142 solval = (lb+ub)/2.0; 143 144 /* if a tie occurs, roughly every third integer variable will be rounded up */ 145 if( SCIPvarGetType(vars[i]) != SCIP_VARTYPE_CONTINUOUS ) 146 solval = i % 3 == 0 ? SCIPceil(scip,solval) : SCIPfloor(scip,solval); 147 148 assert(SCIPisFeasLE(scip,SCIPvarGetLbLocal(vars[i]),solval) && SCIPisFeasLE(scip,solval,SCIPvarGetUbLocal(vars[i]))); 149 } 150 151 if( !SCIPisEQ(scip, lb, zeroval) ) 152 difflb = TRUE; 153 154 if( !SCIPisEQ(scip, ub, zeroval) ) 155 diffub = TRUE; 156 157 if( !SCIPisEQ(scip, solval, zeroval) ) 158 difflock = TRUE; 159 160 /* set variable to values */ 161 SCIP_CALL( SCIPsetSolVal(scip, zerosol, vars[i], zeroval) ); 162 SCIP_CALL( SCIPsetSolVal(scip, lbsol, vars[i], lb) ); 163 SCIP_CALL( SCIPsetSolVal(scip, ubsol, vars[i], ub) ); 164 SCIP_CALL( SCIPsetSolVal(scip, locksol, vars[i], solval) ); 165 } 166 167 /* try zero solution */ 168 SCIPdebugMsg(scip, "try zero solution\n"); 169 SCIP_CALL( SCIPtrySol(scip, zerosol, FALSE, FALSE, FALSE, FALSE, TRUE, &success) ); 170 171 if( success ) 172 { 173 SCIPdebugMsg(scip, "found feasible zero solution:\n"); 174 SCIPdebug( SCIP_CALL( SCIPprintSol(scip, zerosol, NULL, FALSE) ) ); 175 176 *result = SCIP_FOUNDSOL; 177 } 178 179 /* try lower bound solution */ 180 if( difflb ) 181 { 182 SCIPdebugMsg(scip, "try lower bound solution\n"); 183 SCIP_CALL( SCIPtrySol(scip, lbsol, FALSE, FALSE, FALSE, FALSE, TRUE, &success) ); 184 185 if( success ) 186 { 187 SCIPdebugMsg(scip, "found feasible lower bound solution:\n"); 188 SCIPdebug( SCIP_CALL( SCIPprintSol(scip, lbsol, NULL, FALSE) ) ); 189 190 *result = SCIP_FOUNDSOL; 191 } 192 } 193 194 /* try upper bound solution */ 195 if( diffub ) 196 { 197 SCIPdebugMsg(scip, "try upper bound solution\n"); 198 SCIP_CALL( SCIPtrySol(scip, ubsol, FALSE, FALSE, FALSE, FALSE, TRUE, &success) ); 199 200 if( success ) 201 { 202 SCIPdebugMsg(scip, "found feasible upper bound solution:\n"); 203 SCIPdebug( SCIP_CALL( SCIPprintSol(scip, ubsol, NULL, FALSE) ) ); 204 205 *result = SCIP_FOUNDSOL; 206 } 207 } 208 209 /* try lock solution */ 210 if( difflock ) 211 { 212 SCIPdebugMsg(scip, "try lock solution\n"); 213 SCIP_CALL( SCIPtrySol(scip, locksol, FALSE, FALSE, FALSE, FALSE, TRUE, &success) ); 214 215 if( success ) 216 { 217 SCIPdebugMsg(scip, "found feasible lock solution:\n"); 218 SCIPdebug( SCIP_CALL( SCIPprintSol(scip, locksol, NULL, FALSE) ) ); 219 220 *result = SCIP_FOUNDSOL; 221 } 222 } 223 224 TERMINATE: 225 /* free solutions */ 226 SCIP_CALL( SCIPfreeSol(scip, &locksol) ); 227 SCIP_CALL( SCIPfreeSol(scip, &ubsol) ); 228 SCIP_CALL( SCIPfreeSol(scip, &lbsol) ); 229 SCIP_CALL( SCIPfreeSol(scip, &zerosol) ); 230 231 return SCIP_OKAY; 232 } 233 234 235 /* 236 * primal heuristic specific interface methods 237 */ 238 239 /** creates the trivial primal heuristic and includes it in SCIP */ 240 SCIP_RETCODE SCIPincludeHeurTrivial( 241 SCIP* scip /**< SCIP data structure */ 242 ) 243 { 244 SCIP_HEUR* heur; 245 246 /* include primal heuristic */ 247 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur, 248 HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS, 249 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecTrivial, NULL) ); 250 251 assert(heur != NULL); 252 253 /* set non-NULL pointers to callback methods */ 254 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyTrivial) ); 255 256 return SCIP_OKAY; 257 } 258