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_trivialnegation.c 26 * @ingroup DEFPLUGINS_HEUR 27 * @brief trivialnegation primal heuristic 28 * @author Jakob Witzig 29 */ 30 31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 32 33 #include "scip/heur_trivialnegation.h" 34 #include "scip/pub_heur.h" 35 #include "scip/pub_message.h" 36 #include "scip/pub_sol.h" 37 #include "scip/pub_var.h" 38 #include "scip/scip_heur.h" 39 #include "scip/scip_message.h" 40 #include "scip/scip_numerics.h" 41 #include "scip/scip_prob.h" 42 #include "scip/scip_sol.h" 43 #include "scip/scip_solve.h" 44 #include "scip/scip_solvingstats.h" 45 #include <string.h> 46 47 #define HEUR_NAME "trivialnegation" 48 #define HEUR_DESC "negate solution entries if an objective coefficient changes the sign, enters or leaves the objective." 49 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_PROP 50 #define HEUR_PRIORITY 39990 51 #define HEUR_FREQ 0 52 #define HEUR_FREQOFS 0 53 #define HEUR_MAXDEPTH 0 54 #define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE 55 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */ 56 57 /* 58 * Local methods 59 */ 60 61 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */ 62 static 63 SCIP_DECL_HEURCOPY(heurCopyTrivialnegation) 64 { /*lint --e{715}*/ 65 assert(scip != NULL); 66 assert(heur != NULL); 67 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 68 69 /* call inclusion method of primal heuristic */ 70 SCIP_CALL( SCIPincludeHeurTrivialnegation(scip) ); 71 72 return SCIP_OKAY; 73 } 74 75 76 /** execution method of primal heuristic */ 77 static 78 SCIP_DECL_HEUREXEC(heurExecTrivialnegation) 79 { /*lint --e{715}*/ 80 SCIP_SOL* lastbestsol; /* best solution from last run */ 81 SCIP_SOL* allchanged; /* solution with all entries negated */ 82 SCIP_SOL* feasiblechanged; /* solution with all feasible entries negated */ 83 SCIP_SOL* singlenegatedsol; /* solution with exactly one negated entry */ 84 SCIP_VAR** vars; 85 int nbinvars; 86 int i; 87 88 SCIP_Real solval; 89 90 vars = SCIPgetVars(scip); 91 nbinvars = SCIPgetNBinVars(scip); 92 93 *result = SCIP_DIDNOTRUN; 94 95 if( !SCIPisReoptEnabled(scip) ) 96 return SCIP_OKAY; 97 98 if( nbinvars < SCIPgetNVars(scip) ) 99 return SCIP_OKAY; 100 101 *result = SCIP_DIDNOTFIND; 102 103 /* get best solution from the run */ 104 lastbestsol = SCIPgetReoptLastOptSol(scip); 105 106 if( lastbestsol == NULL ) 107 return SCIP_OKAY; 108 109 /* initialize data structure */ 110 SCIP_CALL( SCIPcreateSol(scip, &allchanged, heur) ); 111 SCIP_CALL( SCIPcreateSol(scip, &feasiblechanged, heur) ); 112 SCIP_CALL( SCIPcreateSol(scip, &singlenegatedsol, heur) ); 113 114 /* copy the solutions */ 115 for( i = 0; i < nbinvars; i++ ) 116 { 117 solval = SCIPgetSolVal(scip, lastbestsol, vars[i]); 118 SCIP_CALL( SCIPsetSolVal(scip, allchanged, vars[i], solval) ); 119 SCIP_CALL( SCIPsetSolVal(scip, feasiblechanged, vars[i], solval) ); 120 SCIP_CALL( SCIPsetSolVal(scip, singlenegatedsol, vars[i], solval) ); 121 } 122 123 assert(SCIPsolGetHeur(allchanged) == heur); 124 assert(SCIPsolGetHeur(feasiblechanged) == heur); 125 assert(SCIPsolGetHeur(singlenegatedsol) == heur); 126 127 /* change the entries */ 128 for( i = 0; i < nbinvars; i++ ) 129 { 130 SCIP_VAR* transvar; 131 132 assert(SCIPvarIsActive(vars[i])); 133 134 transvar = vars[i]; 135 136 if( SCIPvarGetType(vars[i]) == SCIP_VARTYPE_BINARY ) 137 { 138 SCIP_Real obj; 139 SCIP_Real newcoef; 140 SCIP_Real oldcoef; 141 SCIP_Bool changed; 142 143 /* perform negation only on variables that are not globally fixed */ 144 if( SCIPvarGetLbGlobal(vars[i]) > 0.5 || SCIPvarGetUbGlobal(vars[i]) < 0.5 ) 145 continue; 146 147 SCIP_CALL( SCIPgetReoptOldObjCoef(scip, transvar, SCIPgetNReoptRuns(scip), &oldcoef)); 148 SCIP_CALL( SCIPgetReoptOldObjCoef(scip, transvar, SCIPgetNReoptRuns(scip)-1, &newcoef)); 149 150 /* check if variable entered or left the objective, or if its objective coefficient changed sign */ 151 changed = FALSE; 152 if( !SCIPisFeasEQ(scip, oldcoef, newcoef) ) 153 { 154 changed = SCIPisZero(scip, oldcoef) != SCIPisZero(scip, newcoef); 155 changed |= SCIPisPositive(scip, oldcoef) == SCIPisNegative(scip, newcoef); /*lint !e514*/ 156 } 157 158 SCIPdebugMsg(scip, "check variable <%s> which has %schanged from %g to %g\n", SCIPvarGetName(transvar), changed ? "" : "not ", oldcoef, newcoef); 159 160 if( changed ) 161 { 162 SCIP_Bool success; 163 164 solval = SCIPgetSolVal(scip, lastbestsol, vars[i]); 165 166 /* change solution value */ 167 SCIP_CALL( SCIPsetSolVal(scip, allchanged, vars[i], 1 - solval) ); 168 SCIP_CALL( SCIPsetSolVal(scip, feasiblechanged, vars[i], 1 - solval) ); 169 SCIP_CALL( SCIPsetSolVal(scip, singlenegatedsol, vars[i], 1 - solval) ); 170 171 /* try solution with all changes */ 172 success = FALSE; 173 obj = SCIPgetSolTransObj(scip, allchanged); 174 if( SCIPisFeasLT(scip, obj, SCIPgetCutoffbound(scip)) ) 175 { 176 SCIPdebugMsg(scip, "try solution with all negations\n"); 177 #ifdef SCIP_DEBUG 178 SCIP_CALL( SCIPtrySol(scip, allchanged, TRUE, FALSE, TRUE, FALSE, TRUE, &success) ); 179 #else 180 SCIP_CALL( SCIPtrySol(scip, allchanged, FALSE, FALSE, TRUE, FALSE, TRUE, &success) ); 181 #endif 182 183 if( success ) 184 { 185 SCIPdebugMsg(scip, "found feasible solution solution:\n"); 186 SCIPdebug( SCIP_CALL( SCIPprintSol(scip, allchanged, NULL, FALSE) ) ); 187 188 *result = SCIP_FOUNDSOL; 189 } 190 } 191 192 /* try solution with feasible changes */ 193 success = FALSE; 194 obj = SCIPgetSolTransObj(scip, feasiblechanged); 195 if( SCIPisFeasLT(scip, obj, SCIPgetCutoffbound(scip)) ) 196 { 197 SCIPdebugMsg(scip, "try solution with feasible negations\n"); 198 #ifdef SCIP_DEBUG 199 SCIP_CALL( SCIPtrySol(scip, feasiblechanged, TRUE, FALSE, TRUE, FALSE, TRUE, &success) ); 200 #else 201 SCIP_CALL( SCIPtrySol(scip, feasiblechanged, FALSE, FALSE, TRUE, FALSE, TRUE, &success) ); 202 #endif 203 if( success ) 204 { 205 SCIPdebugMsg(scip, "found feasible solution solution:\n"); 206 SCIPdebug( SCIP_CALL( SCIPprintSol(scip, feasiblechanged, NULL, FALSE) ) ); 207 208 *result = SCIP_FOUNDSOL; 209 } 210 } 211 212 if( !success ) 213 { 214 /* reset solution with feasible changes */ 215 SCIP_CALL( SCIPsetSolVal(scip, feasiblechanged, vars[i], solval) ); 216 } 217 218 /* try solution with exactly one changed value */ 219 obj = SCIPgetSolTransObj(scip, singlenegatedsol); 220 if( SCIPisFeasLT(scip, obj, SCIPgetCutoffbound(scip)) ) 221 { 222 success = FALSE; 223 SCIPdebugMsg(scip, "try solution with a single negation\n"); 224 #ifdef SCIP_DEBUG 225 SCIP_CALL( SCIPtrySol(scip, singlenegatedsol, TRUE, FALSE, TRUE, FALSE, TRUE, &success) ); 226 #else 227 SCIP_CALL( SCIPtrySol(scip, singlenegatedsol, FALSE, FALSE, TRUE, FALSE, TRUE, &success) ); 228 #endif 229 if( success ) 230 { 231 SCIPdebugMsg(scip, "found feasible solution:\n"); 232 SCIPdebug( SCIP_CALL( SCIPprintSol(scip, singlenegatedsol, NULL, FALSE) ) ); 233 234 *result = SCIP_FOUNDSOL; 235 } 236 } 237 238 /* reset solution with exactly one changed value */ 239 SCIP_CALL( SCIPsetSolVal(scip, singlenegatedsol, vars[i], solval) ); 240 } 241 } 242 } 243 244 /* free solutions */ 245 SCIP_CALL( SCIPfreeSol(scip, &allchanged) ); 246 SCIP_CALL( SCIPfreeSol(scip, &feasiblechanged) ); 247 SCIP_CALL( SCIPfreeSol(scip, &singlenegatedsol) ); 248 249 return SCIP_OKAY; 250 } 251 252 253 /* 254 * primal heuristic specific interface methods 255 */ 256 257 /** creates the trivialnegation primal heuristic and includes it in SCIP */ 258 SCIP_RETCODE SCIPincludeHeurTrivialnegation( 259 SCIP* scip /**< SCIP data structure */ 260 ) 261 { 262 SCIP_HEUR* heur; 263 264 /* include heuristic */ 265 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur, 266 HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS, 267 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecTrivialnegation, NULL) ); 268 269 assert(heur != NULL); 270 271 /* set non fundamental callbacks via setter functions */ 272 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyTrivialnegation) ); 273 274 return SCIP_OKAY; 275 } 276