Scippy

SCIP

Solving Constraint Integer Programs

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