1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the program and library */ 4 /* SCIP --- Solving Constraint Integer Programs */ 5 /* */ 6 /* Copyright (c) 2002-2023 Zuse Institute Berlin (ZIB) */ 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 */ 39 SCIP_RETCODE SCIPboundstoreCreate( 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 */ 60 void SCIPboundstoreFree( 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 */ 75 SCIP_RETCODE SCIPboundstoreAdd( 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 */ 124 SCIP_RETCODE SCIPboundstoreMerge( 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 */ 146 void SCIPboundstoreClear( 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 */ 161 int SCIPboundstoreGetChgVaridx( 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 */ 173 SCIP_BOUNDTYPE SCIPboundstoreGetChgType( 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 */ 185 SCIP_Real SCIPboundstoreGetChgVal( 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 */ 197 int SCIPboundstoreGetNChgs( 198 SCIP_BOUNDSTORE* boundstore /**< the bound store datastructure */ 199 ) 200 { 201 assert(boundstore != NULL); 202 203 return boundstore->nbndchg; 204 } 205