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_sync.c 26 * @ingroup DEFPLUGINS_HEUR 27 * @brief primal heuristic that adds solutions from synchronization 28 * @author Leona Gottwald 29 * 30 * This heuristic takes solutions during synchronization and then adds them. 31 */ 32 33 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 34 35 #include <assert.h> 36 #include <string.h> 37 38 #include "scip/heur_sync.h" 39 #include "scip/scip.h" 40 41 42 #define HEUR_NAME "sync" 43 #define HEUR_DESC "heuristic for synchronizing solution" 44 #define HEUR_DISPCHAR 'S' 45 #define HEUR_PRIORITY -3000000 /* should process after all other heuristics */ 46 #define HEUR_FREQ -1 47 #define HEUR_FREQOFS 0 48 #define HEUR_MAXDEPTH -1 49 #define HEUR_TIMING SCIP_HEURTIMING_DURINGLPLOOP | SCIP_HEURTIMING_BEFOREPRESOL | SCIP_HEURTIMING_BEFORENODE 50 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */ 51 52 53 /* 54 * Data structures 55 */ 56 57 58 /** primal heuristic data */ 59 struct SCIP_HeurData 60 { 61 SCIP_SOL** sols; /**< storing solutions passed to heuristic sorted by objective value */ 62 int nsols; /**< number of soluions stored */ 63 int maxnsols; /**< maximum number of solutions that can be stored */ 64 }; 65 66 67 /* 68 * Callback methods of primal heuristic 69 */ 70 71 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */ 72 static 73 SCIP_DECL_HEURFREE(heurFreeSync) 74 { /*lint --e{715}*/ 75 SCIP_HEURDATA* heurdata; 76 77 assert( heur != NULL ); 78 assert( strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0 ); 79 assert( scip != NULL ); 80 81 SCIPdebugMessage("free method of sync primal heuristic.\n"); 82 83 /* get heuristic data */ 84 heurdata = SCIPheurGetData(heur); 85 assert(heurdata != NULL); 86 assert(heurdata->nsols == 0); 87 SCIPfreeBlockMemoryArray(scip, &heurdata->sols, heurdata->maxnsols); 88 SCIPfreeBlockMemory(scip, &heurdata); 89 90 return SCIP_OKAY; 91 } 92 93 94 /** deinitialization method of primal heuristic (called before transformed problem is freed) */ 95 static 96 SCIP_DECL_HEUREXITSOL(heurExitSync) 97 { /*lint --e{715}*/ 98 SCIP_HEURDATA* heurdata; 99 int i; 100 101 assert( heur != NULL ); 102 assert( strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0 ); 103 assert( scip != NULL ); 104 105 SCIPdebugMessage("exit method of sync primal heuristic.\n"); 106 107 /* get heuristic data */ 108 heurdata = SCIPheurGetData(heur); 109 assert(heurdata != NULL); 110 111 /* free solution if one is still present */ 112 for( i = 0; i < heurdata->nsols; ++i ) 113 { 114 SCIP_CALL( SCIPfreeSol(scip, &heurdata->sols[i]) ); 115 } 116 heurdata->nsols = 0; 117 return SCIP_OKAY; 118 } 119 120 121 /** execution method of primal heuristic */ 122 static 123 SCIP_DECL_HEUREXEC(heurExecSync) 124 { /*lint --e{715}*/ 125 SCIP_HEURDATA* heurdata; 126 SCIP_Bool stored; 127 int i; 128 129 assert(heur != NULL); 130 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 131 assert(scip != NULL); 132 assert(result != NULL); 133 assert(SCIPheurGetFreq(heur) == 1); 134 135 SCIPheurSetFreq(heur, -1); 136 137 /* get heuristic data */ 138 heurdata = SCIPheurGetData(heur); 139 assert(heurdata != NULL); 140 assert(heurdata->nsols > 0); 141 142 SCIPdebugMessage("exec method of sync primal heuristic.\n"); 143 *result = SCIP_DIDNOTFIND; 144 for( i = 0; i < heurdata->nsols; ++i ) 145 { 146 SCIP_CALL( SCIPtrySolFree(scip, &heurdata->sols[i], FALSE, FALSE, FALSE, FALSE, FALSE, &stored) ); 147 if( stored ) 148 *result = SCIP_FOUNDSOL; 149 } 150 151 heurdata->nsols = 0; 152 153 return SCIP_OKAY; 154 } 155 156 /* 157 * primal heuristic specific interface methods 158 */ 159 160 /** creates the sync primal heuristic and includes it in SCIP */ 161 SCIP_RETCODE SCIPincludeHeurSync( 162 SCIP* scip /**< SCIP data structure */ 163 ) 164 { 165 SCIP_HEURDATA* heurdata; 166 SCIP_HEUR* heur; 167 168 /* create heuristic data */ 169 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) ); 170 SCIP_CALL( SCIPgetIntParam(scip, "concurrent/sync/maxnsols", &heurdata->maxnsols) ); 171 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &heurdata->sols, heurdata->maxnsols) ); 172 heurdata->nsols = 0; 173 174 /* include primal heuristic */ 175 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur, 176 HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS, 177 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecSync, heurdata) ); 178 179 assert(heur != NULL); 180 181 /* set non-NULL pointers to callback methods */ 182 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeSync) ); 183 SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitSync) ); 184 185 return SCIP_OKAY; 186 } 187 188 189 /** pass solution to sync heuristic */ 190 SCIP_RETCODE SCIPheurSyncPassSol( 191 SCIP* scip, /**< SCIP data structure */ 192 SCIP_HEUR* heur, /**< sync heuristic */ 193 SCIP_SOL* sol /**< solution to be passed */ 194 ) 195 { 196 SCIP_HEURDATA* heurdata; 197 SCIP_Real solobj; 198 int i; 199 assert(scip != NULL); 200 assert(heur != NULL); 201 assert(sol != NULL); 202 assert(strcmp(HEUR_NAME, SCIPheurGetName(heur)) == 0); 203 204 /* get heuristic data */ 205 heurdata = SCIPheurGetData(heur); 206 assert(heurdata != NULL); 207 208 SCIPsolSetHeur(sol, heur); 209 solobj = SCIPgetSolTransObj(scip, sol); 210 211 /* check if we have an empty space in the solution array or 212 * if we need to discard the worst solution 213 */ 214 if( heurdata->nsols < heurdata->maxnsols ) 215 { 216 /* if the maximum number of solutions is not yet reached just 217 * insert the solution sorted by its objective value */ 218 i = heurdata->nsols++; 219 220 while( i > 0 && solobj > SCIPgetSolTransObj(scip, heurdata->sols[i - 1]) ) 221 { 222 heurdata->sols[i] = heurdata->sols[i - 1]; 223 --i; 224 } 225 heurdata->sols[i] = sol; 226 } 227 else 228 { 229 /* already have reached the maximum number of solutions so 230 * we need to check if the solution is better than a previous 231 * one and free the worst solution to make room for it if that 232 * is the case 233 */ 234 i = 0; 235 while( i < heurdata->nsols && solobj < SCIPgetSolTransObj(scip, heurdata->sols[i]) ) 236 { 237 if( i > 0 ) 238 { 239 heurdata->sols[i - 1] = heurdata->sols[i]; 240 } 241 else 242 { 243 SCIP_CALL( SCIPfreeSol(scip, &heurdata->sols[i]) ); 244 } 245 246 ++i; 247 } 248 /* check if solution must be inserted or discarded */ 249 if( i > 0) 250 { 251 /* found position to insert the solution sorted by objective value */ 252 heurdata->sols[i-1] = sol; 253 } 254 else 255 { 256 /* solution is not better just discard it */ 257 SCIP_CALL( SCIPfreeSol(scip, &sol) ); 258 } 259 } 260 assert(heurdata->nsols > 0); 261 assert(heurdata->nsols <= heurdata->maxnsols); 262 263 SCIPheurSetFreq(heur, 1); 264 265 return SCIP_OKAY; 266 } 267