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-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
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 */
80 
81  return SCIP_OKAY;
82 }
83 
84 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
85 static
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
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
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 */
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,
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 */
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 */
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 }
#define HEUR_FREQ
Definition: heur_trysol.c:45
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:977
SCIP_RETCODE SCIPheurPassSolTrySol(SCIP *scip, SCIP_HEUR *heur, SCIP_SOL *sol)
Definition: heur_trysol.c:243
primal heuristic that tries a given solution
#define HEUR_PRIORITY
Definition: heur_trysol.c:44
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1429
public methods for memory management
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1340
#define HEUR_DESC
Definition: heur_trysol.c:42
SCIP_RETCODE SCIPincludeHeurTrySol(SCIP *scip)
Definition: heur_trysol.c:213
#define FALSE
Definition: def.h:73
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:67
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:95
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:78
SCIP_RETCODE SCIPunlinkSol(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1182
#define SCIPdebugMsg
Definition: scip_message.h:69
public methods for numerical tolerances
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:108
SCIP_RETCODE SCIPcreateSolCopy(SCIP *scip, SCIP_SOL **sol, SCIP_SOL *sourcesol)
Definition: scip_sol.c:610
#define HEUR_FREQOFS
Definition: heur_trysol.c:46
SCIP_RETCODE SCIPheurPassSolAddSol(SCIP *scip, SCIP_HEUR *heur, SCIP_SOL *sol)
Definition: heur_trysol.c:284
SCIP_EXPORT void SCIPsolSetHeur(SCIP_SOL *sol, SCIP_HEUR *heur)
Definition: sol.c:2649
static SCIP_DECL_HEURFREE(heurFreeTrySol)
Definition: heur_trysol.c:86
#define NULL
Definition: lpi_spx1.cpp:155
SCIP_OBJSENSE SCIPgetObjsense(SCIP *scip)
Definition: scip_prob.c:1223
public methods for primal CIP solutions
#define SCIP_CALL(x)
Definition: def.h:370
public methods for primal heuristic plugins and divesets
#define SCIP_Bool
Definition: def.h:70
SCIP_RETCODE SCIPaddSolFree(SCIP *scip, SCIP_SOL **sol, SCIP_Bool *stored)
Definition: scip_sol.c:3016
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip_heur.c:201
static SCIP_DECL_HEUREXEC(heurExecTrySol)
Definition: heur_trysol.c:138
#define HEUR_DISPCHAR
Definition: heur_trysol.c:43
#define HEUR_TIMING
Definition: heur_trysol.c:48
static SCIP_DECL_HEURCOPY(heurCopyTrySol)
Definition: heur_trysol.c:72
public methods for solutions
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:153
public methods for message output
static SCIP_DECL_HEUREXITSOL(heurExitTrySol)
Definition: heur_trysol.c:108
#define SCIP_Real
Definition: def.h:163
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for message handling
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define HEUR_USESSUBSCIP
Definition: heur_trysol.c:49
#define HEUR_MAXDEPTH
Definition: heur_trysol.c:47
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:169
public methods for primal heuristics
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:3232
public methods for global and local (sub)problems
#define HEUR_NAME
Definition: heur_trysol.c:41
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1436