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