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-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 email to 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 /** create a bandit VTable for bandit algorithm callback functions */
202  SCIP_BANDITVTABLE** banditvtable, /**< pointer to virtual table for bandit algorithm */
203  const char* name, /**< a name for the algorithm represented by this vtable */
204  SCIP_DECL_BANDITFREE ((*banditfree)), /**< callback to free bandit specific data structures */
205  SCIP_DECL_BANDITSELECT((*banditselect)), /**< selection callback for bandit selector */
206  SCIP_DECL_BANDITUPDATE((*banditupdate)), /**< update callback for bandit algorithms */
207  SCIP_DECL_BANDITRESET ((*banditreset)) /**< update callback for bandit algorithms */
208  )
209 {
210  SCIP_BANDITVTABLE* banditvtableptr;
211  assert(banditvtable != NULL);
212  assert(name != NULL);
213  assert(banditfree != NULL);
214  assert(banditselect != NULL);
215  assert(banditupdate != NULL);
216  assert(banditreset != NULL);
217 
218  /* allocate memory for this virtual function table */
219  SCIP_ALLOC( BMSallocMemory(banditvtable) );
220  SCIP_ALLOC( BMSduplicateMemoryArray(&(*banditvtable)->name, name, strlen(name)+1) );
221  banditvtableptr = *banditvtable;
222  banditvtableptr->banditfree = banditfree;
223  banditvtableptr->banditselect = banditselect;
224  banditvtableptr->banditupdate = banditupdate;
225  banditvtableptr->banditreset = banditreset;
226 
227  return SCIP_OKAY;
228 }
229 
230 
231 /** free a bandit virtual table for bandit algorithm callback functions */
233  SCIP_BANDITVTABLE** banditvtable /**< pointer to virtual table for bandit algorithm */
234  )
235 {
236  assert(banditvtable != NULL);
237  assert(*banditvtable != NULL);
238 
239  BMSfreeMemoryArray(&(*banditvtable)->name);
240  BMSfreeMemory(banditvtable);
241 }
242 
243 /** return the name of this bandit virtual function table */
245  SCIP_BANDITVTABLE* banditvtable /**< virtual table for bandit algorithm */
246  )
247 {
248  assert(banditvtable != NULL);
249 
250  return banditvtable->name;
251 }
252 
253 
254 /** return the random number generator of a bandit algorithm */
256  SCIP_BANDIT* bandit /**< bandit algorithm data structure */
257  )
258 {
259  assert(bandit != NULL);
260 
261  return bandit->rng;
262 }
263 
264 /** return number of actions of this bandit algorithm */
266  SCIP_BANDIT* bandit /**< bandit algorithm data structure */
267  )
268 {
269  assert(bandit != NULL);
270 
271  return bandit->nactions;
272 }
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:201
SCIP_RETCODE SCIPbanditSelect(SCIP_BANDIT *bandit, int *action)
Definition: bandit.c:143
const char * SCIPbanditvtableGetName(SCIP_BANDITVTABLE *banditvtable)
Definition: bandit.c:244
internal methods for bandit algorithms
void SCIPbanditvtableFree(SCIP_BANDITVTABLE **banditvtable)
Definition: bandit.c:232
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
#define BMSfreeMemory(ptr)
Definition: memory.h:127
SCIP_BANDITDATA * SCIPbanditGetData(SCIP_BANDIT *bandit)
Definition: bandit.c:180
SCIP_RANDNUMGEN * rng
Definition: struct_bandit.h:51
#define BMSfreeMemoryArray(ptr)
Definition: memory.h:129
#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:9350
void SCIPrandomSetSeed(SCIP_RANDNUMGEN *randnumgen, unsigned int initseed)
Definition: misc.c:9280
internal methods for global SCIP settings
#define SCIP_CALL(x)
Definition: def.h:350
void SCIPbanditSetData(SCIP_BANDIT *bandit, SCIP_BANDITDATA *banditdata)
Definition: bandit.c:190
#define BMSduplicateMemoryArray(ptr, source, num)
Definition: memory.h:125
#define BMSfreeBlockMemory(mem, ptr)
Definition: memory.h:446
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
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:149
int SCIPbanditGetNActions(SCIP_BANDIT *bandit)
Definition: bandit.c:265
SCIP_RETCODE SCIPrandomCreate(SCIP_RANDNUMGEN **randnumgen, BMS_BLKMEM *blkmem, unsigned int initialseed)
Definition: misc.c:9334
#define BMSallocMemory(ptr)
Definition: memory.h:101
#define SCIP_DECL_BANDITUPDATE(x)
Definition: type_bandit.h:66
SCIP_RANDNUMGEN * SCIPbanditGetRandnumgen(SCIP_BANDIT *bandit)
Definition: bandit.c:255
#define SCIP_DECL_BANDITSELECT(x)
Definition: type_bandit.h:60
#define BMSallocBlockMemory(mem, ptr)
Definition: memory.h:433
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:419
#define SCIP_ALLOC(x)
Definition: def.h:361
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