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