Scippy

SCIP

Solving Constraint Integer Programs

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