Scippy

SCIP

Solving Constraint Integer Programs

bandit.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-2019 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 bandit.c
17  * @brief internal API of bandit algorithms and bandit virtual function tables
18  * @author Gregor Hendel
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #include <assert.h>
24 #include <string.h>
25 #include "scip/bandit.h"
26 #include "scip/pub_bandit.h"
27 #include "scip/struct_bandit.h"
28 #include "struct_set.h"
29 #include "scip/set.h"
30 
31 /** creates and resets bandit algorithm */
33  SCIP_BANDIT** bandit, /**< pointer to bandit algorithm data structure */
34  SCIP_BANDITVTABLE* banditvtable, /**< virtual table for this bandit algorithm */
35  BMS_BLKMEM* blkmem, /**< block memory for parameter settings */
36  BMS_BUFMEM* bufmem, /**< buffer memory */
37  SCIP_Real* priorities, /**< nonnegative priorities for each action, or NULL if not needed */
38  int nactions, /**< the positive number of actions for this bandit */
39  unsigned int initseed, /**< initial seed for random number generation */
40  SCIP_BANDITDATA* banditdata /**< algorithm specific bandit data */
41  )
42 {
43  SCIP_BANDIT* banditptr;
44  assert(bandit != NULL);
45  assert(banditvtable != NULL);
46 
47  /* the number of actions must be positive */
48  if( nactions <= 0 )
49  {
50  SCIPerrorMessage("Cannot create bandit selector with %d <= 0 actions\n", nactions);
51 
52  return SCIP_INVALIDDATA;
53  }
54 
55  SCIP_ALLOC( BMSallocBlockMemory(blkmem, bandit) );
56  assert(*bandit != NULL);
57  banditptr = *bandit;
58  banditptr->vtable = banditvtable;
59  banditptr->data = banditdata;
60  banditptr->nactions = nactions;
61 
62  SCIP_CALL( SCIPrandomCreate(&banditptr->rng, blkmem, initseed) );
63 
64  SCIP_CALL( SCIPbanditReset(bufmem, banditptr, priorities, initseed) );
65 
66  return SCIP_OKAY;
67 }
68 
69 /** calls destructor and frees memory of bandit algorithm */
71  BMS_BLKMEM* blkmem, /**< block memory */
72  SCIP_BANDIT** bandit /**< pointer to bandit algorithm data structure */
73  )
74 {
75  SCIP_BANDIT* banditptr;
76  SCIP_BANDITVTABLE* vtable;
77  assert(bandit != NULL);
78  assert(*bandit != NULL);
79 
80  banditptr = *bandit;
81  vtable = banditptr->vtable;
82  assert(vtable != NULL);
83 
84  /* call bandit specific data destructor */
85  if( vtable->banditfree != NULL )
86  {
87  SCIP_CALL( vtable->banditfree(blkmem, banditptr) );
88  }
89 
90  /* free random number generator */
91  SCIPrandomFree(&banditptr->rng, blkmem);
92 
93  BMSfreeBlockMemory(blkmem, bandit);
94 
95  return SCIP_OKAY;
96 }
97 
98 /** reset the bandit algorithm */
100  BMS_BUFMEM* bufmem, /**< buffer memory */
101  SCIP_BANDIT* bandit, /**< pointer to bandit algorithm data structure */
102  SCIP_Real* priorities, /**< nonnegative priorities for each action, or NULL if not needed */
103  unsigned int seed /**< initial seed for random number generation */
104  )
105 {
106  SCIP_BANDITVTABLE* vtable;
107 
108  assert(bandit != NULL);
109  assert(bufmem != NULL);
110 
111  vtable = bandit->vtable;
112  assert(vtable != NULL);
113  assert(vtable->banditreset != NULL);
114 
115  /* test if the priorities are nonnegative */
116  if( priorities != NULL )
117  {
118  int i;
119 
120  assert(SCIPbanditGetNActions(bandit) > 0);
121 
122  for( i = 0; i < SCIPbanditGetNActions(bandit); ++i )
123  {
124  if( priorities[i] < 0 )
125  {
126  SCIPerrorMessage("Negative priority for action %d\n", i);
127 
128  return SCIP_INVALIDDATA;
129  }
130  }
131  }
132 
133  /* reset the random seed of the bandit algorithm */
134  SCIPrandomSetSeed(bandit->rng, seed);
135 
136  /* call the reset callback of the bandit algorithm */
137  SCIP_CALL( vtable->banditreset(bufmem, bandit, priorities) );
138 
139  return SCIP_OKAY;
140 }
141 
142 /** select the next action */
144  SCIP_BANDIT* bandit, /**< bandit algorithm data structure */
145  int* action /**< pointer to store the selected action */
146  )
147 {
148  assert(bandit != NULL);
149  assert(action != NULL);
150 
151  *action = -1;
152 
153  assert(bandit->vtable->banditselect != NULL);
154 
155  SCIP_CALL( bandit->vtable->banditselect(bandit, action) );
156 
157  assert(*action >= 0);
158  assert(*action < SCIPbanditGetNActions(bandit));
159 
160  return SCIP_OKAY;
161 }
162 
163 /** update the score of the selected action */
165  SCIP_BANDIT* bandit, /**< bandit algorithm data structure */
166  int action, /**< index of action for which the score should be updated */
167  SCIP_Real score /**< observed gain of the i'th action */
168  )
169 {
170  assert(bandit != NULL);
171  assert(0 <= action && action < SCIPbanditGetNActions(bandit));
172  assert(bandit->vtable->banditupdate != NULL);
173 
174  SCIP_CALL( bandit->vtable->banditupdate(bandit, action, score) );
175 
176  return SCIP_OKAY;
177 }
178 
179 /** get data of this bandit algorithm */
181  SCIP_BANDIT* bandit /**< bandit algorithm data structure */
182  )
183 {
184  assert(bandit != NULL);
185 
186  return bandit->data;
187 }
188 
189 /** set the data of this bandit algorithm */
191  SCIP_BANDIT* bandit, /**< bandit algorithm data structure */
192  SCIP_BANDITDATA* banditdata /**< bandit algorihm specific data, or NULL */
193  )
194 {
195  assert(bandit != NULL);
196 
197  bandit->data = banditdata;
198 }
199 
200 /** internal method to create a bandit VTable */
201 static
203  SCIP_BANDITVTABLE** banditvtable, /**< pointer to virtual table for bandit algorithm */
204  const char* name, /**< a name for the algorithm represented by this vtable */
205  SCIP_DECL_BANDITFREE ((*banditfree)), /**< callback to free bandit specific data structures */
206  SCIP_DECL_BANDITSELECT((*banditselect)), /**< selection callback for bandit selector */
207  SCIP_DECL_BANDITUPDATE((*banditupdate)), /**< update callback for bandit algorithms */
208  SCIP_DECL_BANDITRESET ((*banditreset)) /**< update callback for bandit algorithms */
209  )
210 {
211  SCIP_BANDITVTABLE* banditvtableptr;
212 
213  assert(banditvtable != NULL);
214  assert(name != NULL);
215  assert(banditfree != NULL);
216  assert(banditselect != NULL);
217  assert(banditupdate != NULL);
218  assert(banditreset != NULL);
219 
220  /* allocate memory for this virtual function table */
221  SCIP_ALLOC( BMSallocMemory(banditvtable) );
222  BMSclearMemory(*banditvtable);
223 
224  SCIP_ALLOC( BMSduplicateMemoryArray(&(*banditvtable)->name, name, strlen(name)+1) );
225  banditvtableptr = *banditvtable;
226  banditvtableptr->banditfree = banditfree;
227  banditvtableptr->banditselect = banditselect;
228  banditvtableptr->banditupdate = banditupdate;
229  banditvtableptr->banditreset = banditreset;
230 
231  return SCIP_OKAY;
232 }
233 
234 /** create a bandit VTable for bandit algorithm callback functions */
236  SCIP_BANDITVTABLE** banditvtable, /**< pointer to virtual table for bandit algorithm */
237  const char* name, /**< a name for the algorithm represented by this vtable */
238  SCIP_DECL_BANDITFREE ((*banditfree)), /**< callback to free bandit specific data structures */
239  SCIP_DECL_BANDITSELECT((*banditselect)), /**< selection callback for bandit selector */
240  SCIP_DECL_BANDITUPDATE((*banditupdate)), /**< update callback for bandit algorithms */
241  SCIP_DECL_BANDITRESET ((*banditreset)) /**< update callback for bandit algorithms */
242  )
243 {
244  assert(banditvtable != NULL);
245  assert(name != NULL);
246  assert(banditfree != NULL);
247  assert(banditselect != NULL);
248  assert(banditupdate != NULL);
249  assert(banditreset != NULL);
250 
251  SCIP_CALL_FINALLY( doBanditvtableCreate(banditvtable, name, banditfree, banditselect, banditupdate, banditreset),
252  SCIPbanditvtableFree(banditvtable) );
253 
254  return SCIP_OKAY;
255 }
256 
257 
258 /** free a bandit virtual table for bandit algorithm callback functions */
260  SCIP_BANDITVTABLE** banditvtable /**< pointer to virtual table for bandit algorithm */
261  )
262 {
263  assert(banditvtable != NULL);
264  if( *banditvtable == NULL )
265  return;
266 
267  BMSfreeMemoryArrayNull(&(*banditvtable)->name);
268  BMSfreeMemory(banditvtable);
269 }
270 
271 /** return the name of this bandit virtual function table */
273  SCIP_BANDITVTABLE* banditvtable /**< virtual table for bandit algorithm */
274  )
275 {
276  assert(banditvtable != NULL);
277 
278  return banditvtable->name;
279 }
280 
281 
282 /** return the random number generator of a bandit algorithm */
284  SCIP_BANDIT* bandit /**< bandit algorithm data structure */
285  )
286 {
287  assert(bandit != NULL);
288 
289  return bandit->rng;
290 }
291 
292 /** return number of actions of this bandit algorithm */
294  SCIP_BANDIT* bandit /**< bandit algorithm data structure */
295  )
296 {
297  assert(bandit != NULL);
298 
299  return bandit->nactions;
300 }
SCIP_RETCODE SCIPbanditvtableCreate(SCIP_BANDITVTABLE **banditvtable, const char *name, SCIP_DECL_BANDITFREE((*banditfree)), SCIP_DECL_BANDITSELECT((*banditselect)), SCIP_DECL_BANDITUPDATE((*banditupdate)), SCIP_DECL_BANDITRESET((*banditreset)))
Definition: bandit.c:235
#define NULL
Definition: def.h:246
#define BMSfreeMemoryArrayNull(ptr)
Definition: memory.h:137
SCIP_RETCODE SCIPbanditSelect(SCIP_BANDIT *bandit, int *action)
Definition: bandit.c:143
#define SCIP_CALL_FINALLY(x, y)
Definition: def.h:400
const char * SCIPbanditvtableGetName(SCIP_BANDITVTABLE *banditvtable)
Definition: bandit.c:272
internal methods for bandit algorithms
void SCIPbanditvtableFree(SCIP_BANDITVTABLE **banditvtable)
Definition: bandit.c:259
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_RETCODE SCIPbanditReset(BMS_BUFMEM *bufmem, SCIP_BANDIT *bandit, SCIP_Real *priorities, unsigned int seed)
Definition: bandit.c:99
static SCIP_RETCODE doBanditvtableCreate(SCIP_BANDITVTABLE **banditvtable, const char *name, SCIP_DECL_BANDITFREE((*banditfree)), SCIP_DECL_BANDITSELECT((*banditselect)), SCIP_DECL_BANDITUPDATE((*banditupdate)), SCIP_DECL_BANDITRESET((*banditreset)))
Definition: bandit.c:202
#define BMSfreeMemory(ptr)
Definition: memory.h:134
SCIP_BANDITDATA * SCIPbanditGetData(SCIP_BANDIT *bandit)
Definition: bandit.c:180
SCIP_RANDNUMGEN * rng
Definition: struct_bandit.h:51
#define SCIPerrorMessage
Definition: pub_message.h:45
data structures for bandit selection algorithms
#define SCIP_DECL_BANDITRESET(x)
Definition: type_bandit.h:73
void SCIPrandomFree(SCIP_RANDNUMGEN **randnumgen, BMS_BLKMEM *blkmem)
Definition: misc.c:9592
void SCIPrandomSetSeed(SCIP_RANDNUMGEN *randnumgen, unsigned int initseed)
Definition: misc.c:9522
internal methods for global SCIP settings
#define SCIP_CALL(x)
Definition: def.h:358
void SCIPbanditSetData(SCIP_BANDIT *bandit, SCIP_BANDITDATA *banditdata)
Definition: bandit.c:190
#define BMSduplicateMemoryArray(ptr, source, num)
Definition: memory.h:132
#define BMSfreeBlockMemory(mem, ptr)
Definition: memory.h:453
SCIP_BANDITDATA * data
Definition: struct_bandit.h:53
SCIP_BANDITVTABLE * vtable
Definition: struct_bandit.h:50
public methods for bandit algorithms
SCIP_RETCODE SCIPbanditFree(BMS_BLKMEM *blkmem, SCIP_BANDIT **bandit)
Definition: bandit.c:70
#define BMSclearMemory(ptr)
Definition: memory.h:118
SCIP_RETCODE SCIPbanditUpdate(SCIP_BANDIT *bandit, int action, SCIP_Real score)
Definition: bandit.c:164
struct SCIP_BanditData SCIP_BANDITDATA
Definition: type_bandit.h:47
#define SCIP_DECL_BANDITFREE(x)
Definition: type_bandit.h:54
const char * name
Definition: struct_bandit.h:40
#define SCIP_Real
Definition: def.h:157
int SCIPbanditGetNActions(SCIP_BANDIT *bandit)
Definition: bandit.c:293
SCIP_RETCODE SCIPrandomCreate(SCIP_RANDNUMGEN **randnumgen, BMS_BLKMEM *blkmem, unsigned int initialseed)
Definition: misc.c:9576
#define BMSallocMemory(ptr)
Definition: memory.h:108
#define SCIP_DECL_BANDITUPDATE(x)
Definition: type_bandit.h:66
SCIP_RANDNUMGEN * SCIPbanditGetRandnumgen(SCIP_BANDIT *bandit)
Definition: bandit.c:283
#define SCIP_DECL_BANDITSELECT(x)
Definition: type_bandit.h:60
#define BMSallocBlockMemory(mem, ptr)
Definition: memory.h:440
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:426
#define SCIP_ALLOC(x)
Definition: def.h:369
datastructures for global SCIP settings
SCIP_RETCODE SCIPbanditCreate(SCIP_BANDIT **bandit, SCIP_BANDITVTABLE *banditvtable, BMS_BLKMEM *blkmem, BMS_BUFMEM *bufmem, SCIP_Real *priorities, int nactions, unsigned int initseed, SCIP_BANDITDATA *banditdata)
Definition: bandit.c:32