Scippy

SCIP

Solving Constraint Integer Programs

boundstore.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 boundstore.c
17  * @ingroup PARALLEL
18  * @brief the implementation of the bound store datastructure
19  * @author Robert Lion Gottwald
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #include "scip/boundstore.h"
25 #include "scip/struct_syncstore.h"
26 #include "blockmemshell/memory.h"
27 #include "scip/scip.h"
28 
29 /** create bound store data structure */
31  SCIP* scip, /**< scip main datastructure */
32  SCIP_BOUNDSTORE** boundstore, /**< pointer to store the bound store datastructure */
33  int nvars /**< number of variables for which bounds may be stored */
34  )
35 {
36  assert(scip != NULL);
37  assert(boundstore != NULL);
38 
39  SCIP_CALL( SCIPallocMemory(scip, boundstore) );
40 
41  (*boundstore)->bndchg = NULL;
42  (*boundstore)->bndchgsize = 0;
43  (*boundstore)->nbndchg = 0;
44  (*boundstore)->nvars = nvars;
45  SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &(*boundstore)->bndpos, nvars) );
46 
47  return SCIP_OKAY;
48 }
49 
50 /** free bound store data structure */
52  SCIP* scip, /**< scip main datastructure */
53  SCIP_BOUNDSTORE** boundstore /**< pointer to the bound store datastructure */
54  )
55 {
56  assert(scip != NULL);
57  assert(boundstore != NULL);
58  assert((*boundstore) != NULL);
59 
60  SCIPfreeBlockMemoryArray(scip, &(*boundstore)->bndpos, (*boundstore)->nvars);
61  SCIPfreeBlockMemoryArrayNull(scip, &(*boundstore)->bndchg, (*boundstore)->bndchgsize);
62  SCIPfreeMemory(scip, boundstore);
63 }
64 
65 /** add bound change to bound store data structure */
67  SCIP* scip, /**< scip main datastructure */
68  SCIP_BOUNDSTORE* boundstore, /**< the bound store datastructure */
69  int varidx, /**< variable index of bound change, must be smaller than the
70  * number of variables given during creation of bound store */
71  SCIP_Real newbound, /**< bound value of variable */
72  SCIP_BOUNDTYPE boundtype /**< type of new bound */
73  )
74 {
75  /* check if already stored a bound of same type for this variable */
76  int pos;
77 
78  assert(scip != NULL);
79  assert(boundstore != NULL);
80 
81  pos = boundstore->bndpos[varidx].pos[boundtype];
82 
83  if( pos == 0 )
84  {
85  /* variable has no bound stored yet so store this bound */
86  int i;
87  i = boundstore->nbndchg++;
88  SCIP_CALL( SCIPensureBlockMemoryArray(scip, &boundstore->bndchg, &boundstore->bndchgsize, boundstore->nbndchg) );
89  boundstore->bndchg[i].varidx = varidx;
90  boundstore->bndchg[i].newbound = newbound;
91  boundstore->bndchg[i].boundtype = boundtype;
92  boundstore->bndpos[varidx].pos[boundtype] = boundstore->nbndchg;
93  }
94  else
95  {
96  /* since pos == 0 is reserved if no bound is stored
97  * the index is pos-1
98  */
99  --pos;
100  assert(boundstore->bndchg[pos].boundtype == boundtype);
101  assert(boundstore->bndchg[pos].varidx == varidx);
102 
103  /* if the bound is better overwrite the old one */
104  if( (boundtype == SCIP_BOUNDTYPE_LOWER && newbound > boundstore->bndchg[pos].newbound) ||
105  (boundtype == SCIP_BOUNDTYPE_UPPER && newbound < boundstore->bndchg[pos].newbound) )
106  {
107  boundstore->bndchg[pos].newbound = newbound;
108  }
109  }
110 
111  return SCIP_OKAY;
112 }
113 
114 /** add all bound changes of source to target */
116  SCIP* scip, /**< scip main datastructure for target boundstore */
117  SCIP_BOUNDSTORE* target, /**< the bound store datastructure where the bounds get merged in */
118  SCIP_BOUNDSTORE* source /**< the bound store datastructure from which the bounds get merged in */
119  )
120 {
121  int i;
122 
123  assert(scip != NULL);
124  assert(source != NULL);
125  assert(target != NULL);
126 
127  /* just iterate over the boundchanges in the source and add them to the target */
128  for( i = 0; i < source->nbndchg; ++i )
129  {
130  SCIP_CALL( SCIPboundstoreAdd(scip, target, source->bndchg[i].varidx, source->bndchg[i].newbound, source->bndchg[i].boundtype) );
131  }
132 
133  return SCIP_OKAY;
134 }
135 
136 /** remove all boundchanges from bound store */
138  SCIP_BOUNDSTORE* boundstore /**< the bound store datastructure */
139  )
140 {
141  assert(boundstore != NULL);
142 
143  /* clearing the positions is enough */
144  if( boundstore->nbndchg > 0 )
145  {
146  BMSclearMemoryArray(boundstore->bndpos, boundstore->nvars);
147  boundstore->nbndchg = 0;
148  }
149 }
150 
151 /** gets variable index of the i'th stored boundchange */
153  SCIP_BOUNDSTORE* boundstore, /**< the bound store datastructure */
154  int i /**< the index of the bound change */
155  )
156 {
157  assert(boundstore != NULL);
158  assert(i < boundstore->nbndchg);
159 
160  return boundstore->bndchg[i].varidx;
161 }
162 
163 /** gets the type of the i'th stored boundchange */
165  SCIP_BOUNDSTORE* boundstore, /**< the bound store datastructure */
166  int i /**< the index of the bound change */
167  )
168 {
169  assert(boundstore != NULL);
170  assert(i < boundstore->nbndchg);
171 
172  return boundstore->bndchg[i].boundtype;
173 }
174 
175 /** gets the bound value of the i'th stored boundchange */
177  SCIP_BOUNDSTORE* boundstore, /**< the bound store datastructure */
178  int i /**< the index of the bound change */
179  )
180 {
181  assert(boundstore != NULL);
182  assert(i < boundstore->nbndchg);
183 
184  return boundstore->bndchg[i].newbound;
185 }
186 
187 /** gets the number of stored bound changes */
189  SCIP_BOUNDSTORE* boundstore /**< the bound store datastructure */
190  )
191 {
192  assert(boundstore != NULL);
193 
194  return boundstore->nbndchg;
195 }
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:116
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:50
#define NULL
Definition: def.h:246
SCIP_Real newbound
int SCIPboundstoreGetNChgs(SCIP_BOUNDSTORE *boundstore)
Definition: boundstore.c:188
#define SCIPallocClearBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:103
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
the struct definitions for the synchronization store
int SCIPboundstoreGetChgVaridx(SCIP_BOUNDSTORE *boundstore, int i)
Definition: boundstore.c:152
void SCIPboundstoreFree(SCIP *scip, SCIP_BOUNDSTORE **boundstore)
Definition: boundstore.c:51
SCIP_RETCODE SCIPboundstoreAdd(SCIP *scip, SCIP_BOUNDSTORE *boundstore, int varidx, SCIP_Real newbound, SCIP_BOUNDTYPE boundtype)
Definition: boundstore.c:66
SCIP_BOUNDTYPE boundtype
the interface of the boundstore structure
#define SCIP_CALL(x)
Definition: def.h:358
#define SCIPensureBlockMemoryArray(scip, ptr, arraysizeptr, minsize)
Definition: scip_mem.h:113
#define SCIPfreeMemory(scip, ptr)
Definition: scip_mem.h:86
SCIP_Real SCIPboundstoreGetChgVal(SCIP_BOUNDSTORE *boundstore, int i)
Definition: boundstore.c:176
#define SCIP_Real
Definition: def.h:157
SCIP_RETCODE SCIPboundstoreCreate(SCIP *scip, SCIP_BOUNDSTORE **boundstore, int nvars)
Definition: boundstore.c:30
#define SCIPallocMemory(scip, ptr)
Definition: scip_mem.h:70
SCIP_RETCODE SCIPboundstoreMerge(SCIP *scip, SCIP_BOUNDSTORE *target, SCIP_BOUNDSTORE *source)
Definition: boundstore.c:115
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:117
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:119
SCIP_BOUNDTYPE SCIPboundstoreGetChgType(SCIP_BOUNDSTORE *boundstore, int i)
Definition: boundstore.c:164
SCIP callable library.
void SCIPboundstoreClear(SCIP_BOUNDSTORE *boundstore)
Definition: boundstore.c:137
memory allocation routines