1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file heur_trysol.c
17 * @ingroup DEFPLUGINS_HEUR
18 * @brief primal heuristic that tries a given solution
19 * @author Marc Pfetsch
20 *
21 * This heuristic takes a solution from somewhere else via the function SCIPheurPassSolTrySol(). It
22 * then tries to commit this solution. It is mainly used by cons_indicator, which tries to correct a
23 * given solution, but cannot directly submit this solution, because it is a constraint handler and
24 * not a heuristic.
25 */
26
27 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
28
29 #include "scip/heur_trysol.h"
30 #include "scip/pub_heur.h"
31 #include "scip/pub_message.h"
32 #include "scip/pub_sol.h"
33 #include "scip/scip_heur.h"
34 #include "scip/scip_mem.h"
35 #include "scip/scip_message.h"
36 #include "scip/scip_numerics.h"
37 #include "scip/scip_prob.h"
38 #include "scip/scip_sol.h"
39 #include <string.h>
40
41 #define HEUR_NAME "trysol"
42 #define HEUR_DESC "try solution heuristic"
43 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_TRIVIAL
44 #define HEUR_PRIORITY -3000000 /* should process after all other heuristics */
45 #define HEUR_FREQ 1
46 #define HEUR_FREQOFS 0
47 #define HEUR_MAXDEPTH -1
48 #define HEUR_TIMING SCIP_HEURTIMING_DURINGLPLOOP | SCIP_HEURTIMING_BEFOREPRESOL | SCIP_HEURTIMING_BEFORENODE
49 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
50
51
52 /*
53 * Data structures
54 */
55
56
57 /** primal heuristic data */
58 struct SCIP_HeurData
59 {
60 SCIP_SOL* trysol; /**< storing solution passed to heuristic which has to tried (NULL if none) */
61 SCIP_SOL* addsol; /**< storing solution passed to heuristic which can be added without checking (NULL if none) */
62 SCIP_Bool rec; /**< whether we are within our own call */
63 };
64
65
66 /*
67 * Callback methods of primal heuristic
68 */
69
70 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
71 static
SCIP_DECL_HEURCOPY(heurCopyTrySol)72 SCIP_DECL_HEURCOPY(heurCopyTrySol)
73 { /*lint --e{715}*/
74 assert(scip != NULL);
75 assert(heur != NULL);
76 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
77
78 /* call inclusion method of primal heuristic */
79 SCIP_CALL( SCIPincludeHeurTrySol(scip) );
80
81 return SCIP_OKAY;
82 }
83
84 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
85 static
SCIP_DECL_HEURFREE(heurFreeTrySol)86 SCIP_DECL_HEURFREE(heurFreeTrySol)
87 { /*lint --e{715}*/
88 SCIP_HEURDATA* heurdata;
89
90 assert( heur != NULL );
91 assert( strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0 );
92 assert( scip != NULL );
93
94 SCIPdebugMsg(scip, "free method of trysol primal heuristic.\n");
95
96 /* get heuristic data */
97 heurdata = SCIPheurGetData(heur);
98 assert(heurdata != NULL);
99
100 SCIPfreeBlockMemory(scip, &heurdata);
101
102 return SCIP_OKAY;
103 }
104
105
106 /** deinitialization method of primal heuristic (called before transformed problem is freed) */
107 static
SCIP_DECL_HEUREXITSOL(heurExitTrySol)108 SCIP_DECL_HEUREXITSOL(heurExitTrySol)
109 { /*lint --e{715}*/
110 SCIP_HEURDATA* heurdata;
111
112 assert( heur != NULL );
113 assert( strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0 );
114 assert( scip != NULL );
115
116 SCIPdebugMsg(scip, "exit method of trysol primal heuristic.\n");
117
118 /* get heuristic data */
119 heurdata = SCIPheurGetData(heur);
120 assert(heurdata != NULL);
121
122 /* free solution if one is still present */
123 if( heurdata->trysol != NULL )
124 SCIP_CALL( SCIPfreeSol(scip, &heurdata->trysol) );
125 assert( heurdata->trysol == NULL );
126
127 /* free solution if one is still present */
128 if( heurdata->addsol != NULL )
129 SCIP_CALL( SCIPfreeSol(scip, &heurdata->addsol) );
130 assert( heurdata->trysol == NULL );
131
132 return SCIP_OKAY;
133 }
134
135
136 /** execution method of primal heuristic */
137 static
SCIP_DECL_HEUREXEC(heurExecTrySol)138 SCIP_DECL_HEUREXEC(heurExecTrySol)
139 { /*lint --e{715}*/
140 SCIP_HEURDATA* heurdata;
141 SCIP_Bool stored;
142 #ifdef SCIP_DEBUG
143 SCIP_Real obj;
144 #endif
145
146 assert( heur != NULL );
147 assert( strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0 );
148 assert( scip != NULL );
149 assert( result != NULL );
150
151 *result = SCIP_DIDNOTRUN;
152
153 /* get heuristic data */
154 heurdata = SCIPheurGetData(heur);
155 assert(heurdata != NULL);
156
157 /* only run if solution present */
158 if( heurdata->addsol == NULL && heurdata->trysol == NULL )
159 return SCIP_OKAY;
160
161 SCIPdebugMsg(scip, "exec method of trysol primal heuristic.\n");
162 *result = SCIP_DIDNOTFIND;
163 heurdata->rec = TRUE;
164
165 if( heurdata->trysol != NULL )
166 {
167 /* try solution and free it - check everything, because we are not sure */
168 #ifdef SCIP_DEBUG
169 obj = SCIPgetSolOrigObj(scip, heurdata->trysol);
170 #endif
171
172 SCIP_CALL( SCIPtrySolFree(scip, &heurdata->trysol, FALSE, FALSE, TRUE, TRUE, TRUE, &stored) );
173
174 if( stored )
175 {
176 #ifdef SCIP_DEBUG
177 SCIPdebugMsg(scip, "Found feasible solution of value %g.\n", obj);
178 #endif
179 *result = SCIP_FOUNDSOL;
180 }
181 }
182
183 if( heurdata->addsol != NULL )
184 {
185 #ifdef SCIP_DEBUG
186 obj = SCIPgetSolOrigObj(scip, heurdata->addsol);
187 #endif
188
189 SCIP_CALL( SCIPaddSolFree(scip, &heurdata->addsol, &stored) );
190
191 if( stored )
192 {
193 #ifdef SCIP_DEBUG
194 SCIPdebugMsg(scip, "Found feasible solution of value %g.\n", obj);
195 #endif
196 *result = SCIP_FOUNDSOL;
197 }
198 }
199
200 assert( heurdata->trysol == NULL );
201 assert( heurdata->addsol == NULL );
202
203 heurdata->rec = FALSE;
204
205 return SCIP_OKAY;
206 }
207
208 /*
209 * primal heuristic specific interface methods
210 */
211
212 /** creates the trysol primal heuristic and includes it in SCIP */
SCIPincludeHeurTrySol(SCIP * scip)213 SCIP_RETCODE SCIPincludeHeurTrySol(
214 SCIP* scip /**< SCIP data structure */
215 )
216 {
217 SCIP_HEURDATA* heurdata;
218 SCIP_HEUR* heur;
219
220 /* create heuristic data */
221 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
222 heurdata->trysol = NULL;
223 heurdata->addsol = NULL;
224 heurdata->rec = FALSE;
225
226 /* include primal heuristic */
227 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
228 HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
229 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecTrySol, heurdata) );
230
231 assert(heur != NULL);
232
233 /* set non-NULL pointers to callback methods */
234 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyTrySol) );
235 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeTrySol) );
236 SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitTrySol) );
237
238 return SCIP_OKAY;
239 }
240
241
242 /** pass solution to trysol heuristic */
SCIPheurPassSolTrySol(SCIP * scip,SCIP_HEUR * heur,SCIP_SOL * sol)243 SCIP_RETCODE SCIPheurPassSolTrySol(
244 SCIP* scip, /**< SCIP data structure */
245 SCIP_HEUR* heur, /**< trysol heuristic */
246 SCIP_SOL* sol /**< solution to be passed */
247 )
248 {
249 SCIP_HEURDATA* heurdata;
250
251 assert( scip != NULL );
252 assert( heur != NULL );
253 assert( sol != NULL );
254 assert( strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0 );
255
256 /* get heuristic data */
257 heurdata = SCIPheurGetData(heur);
258 assert(heurdata != NULL);
259
260 /* only store solution if we are not within our own SCIPtrySol() call */
261 if( ! heurdata->rec )
262 {
263 if( heurdata->trysol == NULL || (SCIPgetObjsense(scip) == SCIP_OBJSENSE_MAXIMIZE &&
264 SCIPisGT(scip, SCIPgetSolOrigObj(scip, sol), SCIPgetSolOrigObj(scip, heurdata->trysol))) ||
265 SCIPisLT(scip, SCIPgetSolOrigObj(scip, sol), SCIPgetSolOrigObj(scip, heurdata->trysol)) )
266 {
267 if( heurdata->trysol != NULL )
268 {
269 /* free previous solution */
270 SCIP_CALL( SCIPfreeSol(scip, &heurdata->trysol) );
271 }
272
273 SCIPdebugMsg(scip, "Received solution of value %g.\n", SCIPgetSolOrigObj(scip, sol));
274 SCIP_CALL( SCIPcreateSolCopy(scip, &heurdata->trysol, sol) );
275 SCIP_CALL( SCIPunlinkSol(scip, heurdata->trysol) );
276 SCIPsolSetHeur(heurdata->trysol, heur);
277 }
278 }
279
280 return SCIP_OKAY;
281 }
282
283 /** pass solution to trysol heuristic which just gets added (without checking feasibility */
SCIPheurPassSolAddSol(SCIP * scip,SCIP_HEUR * heur,SCIP_SOL * sol)284 SCIP_RETCODE SCIPheurPassSolAddSol(
285 SCIP* scip, /**< SCIP data structure */
286 SCIP_HEUR* heur, /**< trysol heuristic */
287 SCIP_SOL* sol /**< solution to be passed */
288 )
289 {
290 SCIP_HEURDATA* heurdata;
291
292 assert( scip != NULL );
293 assert( heur != NULL );
294 assert( sol != NULL );
295 assert( strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0 );
296
297 /* get heuristic data */
298 heurdata = SCIPheurGetData(heur);
299 assert(heurdata != NULL);
300
301 /* only store solution if we are not within our own SCIPtrySol() call */
302 if( ! heurdata->rec )
303 {
304 if( heurdata->addsol == NULL || (SCIPgetObjsense(scip) == SCIP_OBJSENSE_MAXIMIZE &&
305 SCIPisGT(scip, SCIPgetSolOrigObj(scip, sol), SCIPgetSolOrigObj(scip, heurdata->addsol))) ||
306 SCIPisLT(scip, SCIPgetSolOrigObj(scip, sol), SCIPgetSolOrigObj(scip, heurdata->addsol)) )
307 {
308 if( heurdata->addsol != NULL )
309 {
310 /* free previous solution */
311 SCIP_CALL( SCIPfreeSol(scip, &heurdata->addsol) );
312 }
313
314 SCIPdebugMsg(scip, "Received solution of value %g.\n", SCIPgetSolOrigObj(scip, sol));
315 SCIP_CALL( SCIPcreateSolCopy(scip, &heurdata->addsol, sol) );
316 SCIP_CALL( SCIPunlinkSol(scip, heurdata->addsol) );
317 SCIPsolSetHeur(heurdata->addsol, heur);
318 }
319 }
320
321 return SCIP_OKAY;
322 }
323