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