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