1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 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 scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file boundstore.c
17 * @ingroup PARALLEL
18 * @brief the implementation of the bound store datastructure
19 * @author Leona 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 */
SCIPboundstoreCreate(SCIP * scip,SCIP_BOUNDSTORE ** boundstore,int nvars)30 SCIP_RETCODE SCIPboundstoreCreate(
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 */
SCIPboundstoreFree(SCIP * scip,SCIP_BOUNDSTORE ** boundstore)51 void SCIPboundstoreFree(
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 */
SCIPboundstoreAdd(SCIP * scip,SCIP_BOUNDSTORE * boundstore,int varidx,SCIP_Real newbound,SCIP_BOUNDTYPE boundtype)66 SCIP_RETCODE SCIPboundstoreAdd(
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 */
SCIPboundstoreMerge(SCIP * scip,SCIP_BOUNDSTORE * target,SCIP_BOUNDSTORE * source)115 SCIP_RETCODE SCIPboundstoreMerge(
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 */
SCIPboundstoreClear(SCIP_BOUNDSTORE * boundstore)137 void SCIPboundstoreClear(
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 */
SCIPboundstoreGetChgVaridx(SCIP_BOUNDSTORE * boundstore,int i)152 int SCIPboundstoreGetChgVaridx(
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 */
SCIPboundstoreGetChgType(SCIP_BOUNDSTORE * boundstore,int i)164 SCIP_BOUNDTYPE SCIPboundstoreGetChgType(
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 */
SCIPboundstoreGetChgVal(SCIP_BOUNDSTORE * boundstore,int i)176 SCIP_Real SCIPboundstoreGetChgVal(
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 */
SCIPboundstoreGetNChgs(SCIP_BOUNDSTORE * boundstore)188 int SCIPboundstoreGetNChgs(
189 SCIP_BOUNDSTORE* boundstore /**< the bound store datastructure */
190 )
191 {
192 assert(boundstore != NULL);
193
194 return boundstore->nbndchg;
195 }
196