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 /**@file spxboundflippingrt.h 26 * @brief Bound flipping ratio test (long step dual) for SoPlex. 27 * @author Matthias Miltenberger 28 * @author Eva Ramlow 29 */ 30 #ifndef _SPXBOUNDFLIPPINGRT_H_ 31 #define _SPXBOUNDFLIPPINGRT_H_ 32 33 34 #include <assert.h> 35 #include "soplex/spxdefines.h" 36 #include "soplex/spxratiotester.h" 37 #include "soplex/spxfastrt.h" 38 39 namespace soplex 40 { 41 42 /**@brief Bound flipping ratio test ("long step dual") for SoPlex. 43 @ingroup Algo 44 45 Class SPxBoundFlippingRT provides an implementation of the bound flipping 46 ratio test as a derived class of SPxRatioTester. Dual step length is 47 increased beyond some breakpoints and corresponding primal nonbasic 48 variables are set to their other bound to handle the resulting dual infeasibility. 49 50 The implementation mostly follows the papers 51 - I. Maros, "A generalized dual phase-2 simplex algorithm", 52 European Journal of Operational Research Vol 149, Issue 1, pp. 1-16, 2003 53 - A. Koberstein, "Progress in the dual simplex algorithm for solving large scale LP problems: 54 techniques for a fast and stable implementation", 55 Computational Optimization and Applications Vol 41, Nr 2, pp. 185-204, 2008 56 57 See SPxRatioTester for a class documentation. 58 */ 59 template <class R> 60 class SPxBoundFlippingRT : public SPxFastRT<R> 61 { 62 private: 63 /**@name substructures */ 64 ///@{ 65 /** enumerator to remember which vector we have been searching to find a breakpoint 66 */ 67 enum BreakpointSource 68 { 69 FVEC = -1, 70 PVEC = 0, 71 COPVEC = 1 72 }; 73 74 /** breakpoint structure 75 */ 76 struct Breakpoint 77 { 78 R val; /**< breakpoint value (step length) */ 79 int idx; /**< index of corresponding row/column */ 80 BreakpointSource src; /**< origin of breakpoint, i.e. vector which was searched */ 81 }; 82 83 /** Compare class for breakpoints 84 */ 85 struct BreakpointCompare 86 { 87 public: 88 /** constructor 89 */ 90 BreakpointCompare() 91 : entry(0) 92 { 93 } 94 95 const Breakpoint* entry; 96 97 R operator()( 98 Breakpoint i, 99 Breakpoint j 100 ) const 101 { 102 return i.val - j.val; 103 } 104 }; 105 ///@} 106 107 /**@name Data 108 */ 109 ///@{ 110 bool enableBoundFlips; /**< enable or disable long steps in BoundFlippingRT */ 111 bool enableRowBoundFlips;/**< enable bound flips also for row representation */ 112 R 113 flipPotential; /**< tracks bound flip history and decides which ratio test to use */ 114 int relax_count; /**< count rounds of ratio test */ 115 Array<Breakpoint> breakpoints; /**< array of breakpoints */ 116 SSVectorBase<R> 117 updPrimRhs; /**< right hand side vector of additional system to be solved after the ratio test */ 118 SSVectorBase<R> 119 updPrimVec; /**< allocation of memory for additional solution vector */ 120 ///@} 121 122 /** store all available pivots/breakpoints in an array (positive pivot search direction) */ 123 void collectBreakpointsMax( 124 int& nBp, /**< number of found breakpoints so far */ 125 int& minIdx, /**< index to current minimal breakpoint */ 126 const int* idx, /**< pointer to indices of current vector */ 127 int nnz, /**< number of nonzeros in current vector */ 128 const R* upd, /**< pointer to update values of current vector */ 129 const R* vec, /**< pointer to values of current vector */ 130 const R* upp, /**< pointer to upper bound/rhs of current vector */ 131 const R* low, /**< pointer to lower bound/lhs of current vector */ 132 BreakpointSource src /**< type of vector (pVec or coPvec)*/ 133 ); 134 135 /** store all available pivots/breakpoints in an array (negative pivot search direction) */ 136 void collectBreakpointsMin( 137 int& nBp, /**< number of found breakpoints so far */ 138 int& minIdx, /**< index to current minimal breakpoint */ 139 const int* idx, /**< pointer to indices of current vector */ 140 int nnz, /**< number of nonzeros in current vector */ 141 const R* upd, /**< pointer to update values of current vector */ 142 const R* vec, /**< pointer to values of current vector */ 143 const R* upp, /**< pointer to upper bound/rhs of current vector */ 144 const R* low, /**< pointer to lower bound/lhs of current vector */ 145 BreakpointSource src /**< type of vector (pVec or coPvec)*/ 146 ); 147 148 /** get values for entering index and perform shifts if necessary */ 149 bool getData( 150 R& val, 151 SPxId& enterId, 152 int idx, 153 R stab, 154 R degeneps, 155 const R* upd, 156 const R* vec, 157 const R* low, 158 const R* upp, 159 BreakpointSource src, 160 R max 161 ); 162 163 /** get values for leaving index and perform shifts if necessary */ 164 bool getData( 165 R& val, 166 int& leaveIdx, 167 int idx, 168 R stab, 169 R degeneps, 170 const R* upd, 171 const R* vec, 172 const R* low, 173 const R* upp, 174 BreakpointSource src, 175 R max 176 ); 177 178 /** perform necessary bound flips to restore dual feasibility */ 179 void flipAndUpdate( 180 int& usedBp /**< number of bounds that should be flipped */ 181 ); 182 183 /** comparison method for breakpoints */ 184 static bool isSmaller( 185 Breakpoint x, 186 Breakpoint y 187 ) 188 { 189 return (spxAbs(x.val) < spxAbs(y.val)); 190 }; 191 192 public: 193 194 //------------------------------------- 195 /**@name Construction / destruction */ 196 ///@{ 197 /// default constructor 198 SPxBoundFlippingRT() 199 : SPxFastRT<R>("Bound Flipping") 200 , enableBoundFlips(true) 201 , enableRowBoundFlips(false) 202 , flipPotential(1) 203 , relax_count(0) 204 , breakpoints(10) 205 , updPrimRhs(0) 206 , updPrimVec(0) 207 {} 208 /// copy constructor 209 SPxBoundFlippingRT(const SPxBoundFlippingRT& old) 210 : SPxFastRT<R>(old) 211 , enableBoundFlips(old.enableBoundFlips) 212 , enableRowBoundFlips(old.enableRowBoundFlips) 213 , flipPotential(1) 214 , relax_count(0) 215 , breakpoints(10) 216 , updPrimRhs(0) 217 , updPrimVec(0) 218 {} 219 /// assignment operator 220 SPxBoundFlippingRT& operator=(const SPxBoundFlippingRT& rhs) 221 { 222 if(this != &rhs) 223 { 224 SPxFastRT<R>::operator=(rhs); 225 } 226 227 enableBoundFlips = rhs.enableBoundFlips; 228 enableRowBoundFlips = rhs.enableRowBoundFlips; 229 flipPotential = rhs.flipPotential; 230 231 return *this; 232 } 233 /// destructor 234 virtual ~SPxBoundFlippingRT() 235 {} 236 /// clone function for polymorphism 237 inline virtual SPxRatioTester<R>* clone() const 238 { 239 return new SPxBoundFlippingRT(*this); 240 } 241 ///@} 242 243 //------------------------------------- 244 /**@name Select enter/leave */ 245 ///@{ 246 /// 247 virtual int selectLeave( 248 R& val, 249 R enterTest, 250 bool polish = false 251 ); 252 /// 253 virtual SPxId selectEnter( 254 R& val, 255 int leaveIdx, 256 bool polish = false 257 ); 258 259 void useBoundFlips(bool bf) 260 { 261 enableBoundFlips = bf; 262 } 263 264 void useBoundFlipsRow(bool bf) 265 { 266 enableRowBoundFlips = bf; 267 } 268 269 /// set tolerances 270 void setTolerances(std::shared_ptr<Tolerances> tolerances) 271 { 272 this->_tolerances = tolerances; 273 this->updPrimRhs.setTolerances(tolerances); 274 this->updPrimVec.setTolerances(tolerances); 275 } 276 ///@} 277 }; 278 279 } // namespace soplex 280 281 #include "spxboundflippingrt.hpp" 282 283 #endif // _SPXBOUNDFLIPPINGRT_H_ 284