1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the class library */ 4 /* SoPlex --- the Sequential object-oriented simPlex. */ 5 /* */ 6 /* Copyright (c) 1996-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 SoPlex; see the file LICENSE. If not email to soplex@zib.de. */ 22 /* */ 23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 24 25 #include <assert.h> 26 #include <iostream> 27 28 #include "soplex/spxdefines.h" 29 30 namespace soplex 31 { 32 33 template <class R> 34 int SPxDantzigPR<R>::selectLeave() 35 { 36 assert(this->thesolver != 0); 37 38 if(this->thesolver->sparsePricingLeave) 39 return selectLeaveSparse(); 40 41 // const R* up = this->thesolver->ubBound(); 42 // const R* low = this->thesolver->lbBound(); 43 44 R best = -this->thetolerance; 45 int n = -1; 46 47 for(int i = this->thesolver->dim() - 1; i >= 0; --i) 48 { 49 R x = this->thesolver->fTest()[i]; 50 51 if(x < -this->thetolerance) 52 { 53 if(x < best) 54 { 55 n = i; 56 best = x; 57 } 58 } 59 } 60 61 return n; 62 } 63 64 template <class R> 65 int SPxDantzigPR<R>::selectLeaveSparse() 66 { 67 assert(this->thesolver != 0); 68 69 R best = -this->thetolerance; 70 R x; 71 int n = -1; 72 int index; 73 74 for(int i = this->thesolver->infeasibilities.size() - 1; i >= 0; --i) 75 { 76 index = this->thesolver->infeasibilities.index(i); 77 x = this->thesolver->fTest()[index]; 78 79 if(x < -this->thetolerance) 80 { 81 if(x < best) 82 { 83 n = index; 84 best = x; 85 } 86 } 87 else 88 { 89 this->thesolver->infeasibilities.remove(i); 90 assert(this->thesolver->isInfeasible[index] > 0); 91 this->thesolver->isInfeasible[index] = 0; 92 } 93 } 94 95 return n; 96 } 97 98 template <class R> 99 SPxId SPxDantzigPR<R>::selectEnter() 100 { 101 assert(this->thesolver != 0); 102 103 // const SPxBasisBase<R>::Desc& ds = this->thesolver->basis().desc(); 104 105 SPxId enterId; 106 enterId = selectEnterX(); 107 108 return enterId; 109 } 110 111 template <class R> 112 SPxId SPxDantzigPR<R>::selectEnterX() 113 { 114 SPxId enterId; 115 SPxId enterIdCo; 116 R best; 117 R bestCo; 118 119 best = -this->thetolerance; 120 bestCo = -this->thetolerance; 121 enterId = (this->thesolver->sparsePricingEnter) ? selectEnterSparseDim(best, 122 enterId) : selectEnterDenseDim(best, enterId); 123 enterIdCo = (this->thesolver->sparsePricingEnterCo) ? selectEnterSparseCoDim(bestCo, 124 enterId) : selectEnterDenseCoDim(bestCo, enterId); 125 126 // prefer slack indices to reduce nonzeros in basis matrix 127 if(enterId.isValid() && (best > SOPLEX_SPARSITY_TRADEOFF * bestCo || !enterIdCo.isValid())) 128 return enterId; 129 else 130 return enterIdCo; 131 } 132 133 134 template <class R> 135 SPxId SPxDantzigPR<R>::selectEnterSparseDim(R& best, SPxId& enterId) 136 { 137 assert(this->thesolver != 0); 138 139 int idx; 140 R x; 141 142 for(int i = this->thesolver->infeasibilities.size() - 1; i >= 0; --i) 143 { 144 idx = this->thesolver->infeasibilities.index(i); 145 x = this->thesolver->coTest()[idx]; 146 147 if(x < -this->thetolerance) 148 { 149 if(x < best) 150 { 151 enterId = this->thesolver->coId(idx); 152 best = x; 153 } 154 } 155 else 156 { 157 this->thesolver->infeasibilities.remove(i); 158 159 assert(this->thesolver->isInfeasible[idx]); 160 this->thesolver->isInfeasible[idx] = 0; 161 } 162 } 163 164 return enterId; 165 } 166 167 template <class R> 168 SPxId SPxDantzigPR<R>::selectEnterSparseCoDim(R& best, SPxId& enterId) 169 { 170 assert(this->thesolver != 0); 171 172 int idx; 173 R x; 174 175 for(int i = this->thesolver->infeasibilitiesCo.size() - 1; i >= 0; --i) 176 { 177 idx = this->thesolver->infeasibilitiesCo.index(i); 178 x = this->thesolver->test()[idx]; 179 180 if(x < -this->thetolerance) 181 { 182 if(x < best) 183 { 184 enterId = this->thesolver->id(idx); 185 best = x; 186 } 187 } 188 else 189 { 190 this->thesolver->infeasibilitiesCo.remove(i); 191 assert(this->thesolver->isInfeasibleCo[idx] > 0); 192 this->thesolver->isInfeasibleCo[idx] = 0; 193 } 194 } 195 196 return enterId; 197 } 198 199 template <class R> 200 SPxId SPxDantzigPR<R>::selectEnterDenseDim(R& best, SPxId& enterId) 201 { 202 assert(this->thesolver != 0); 203 204 R x; 205 206 for(int i = this->thesolver->dim() - 1; i >= 0; --i) 207 { 208 x = this->thesolver->coTest()[i]; 209 210 if(x < -this->thetolerance) 211 { 212 if(x < best) 213 { 214 enterId = this->thesolver->coId(i); 215 best = x; 216 } 217 } 218 } 219 220 return enterId; 221 } 222 223 template <class R> 224 SPxId SPxDantzigPR<R>::selectEnterDenseCoDim(R& best, SPxId& enterId) 225 { 226 assert(this->thesolver != 0); 227 228 R x; 229 230 for(int i = this->thesolver->coDim() - 1; i >= 0; --i) 231 { 232 x = this->thesolver->test()[i]; 233 234 if(x < -this->thetolerance) 235 { 236 if(x < best) 237 { 238 enterId = this->thesolver->id(i); 239 best = x; 240 } 241 } 242 } 243 244 return enterId; 245 } 246 247 } // namespace soplex 248