SoPlex Doxygen Documentation
spxboundflippingrt.h
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the class library */
4 /* SoPlex --- the Sequential object-oriented simPlex. */
5 /* */
6 /* Copyright (C) 1996-2012 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SoPlex is distributed under the terms of the ZIB Academic Licence. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SoPlex; see the file COPYING. If not email to soplex@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file spxboundflippingrt.h
17  * @brief Bound flipping ratio test (long step dual) for SoPlex.
18  * @author Matthias Miltenberger
19  */
20 #ifndef _SPXBOUNDFLIPPINGRT_H_
21 #define _SPXBOUNDFLIPPINGRT_H_
22 
23 
24 #include <assert.h>
25 #include "spxdefines.h"
26 #include "spxratiotester.h"
27 #include "spxfastrt.h"
28 
29 namespace soplex
30 {
31 struct Compare;
32 
33 /**@brief Bound flipping ratio test ("long step dual") for SoPlex.
34  @ingroup Algo
35 
36  Class SPxBoundFlippingRT provides an implementation of the bound flipping
37  ratio test as a derived class of SPxRatioTester. Dual step length is
38  increased beyond some breakpoints and corresponding primal nonbasic
39  variables are set to their other bound to handle the resulting dual infeasibility.
40 
41  The implementation mostly follows the papers
42  - I. Maros, "A generalized dual phase-2 simplex algorithm",
43  European Journal of Operational Research Vol 149, Issue 1, pp. 1-16, 2003
44  - A. Koberstein, "Progress in the dual simplex algorithm for solving large scale LP problems:
45  techniques for a fast and stable implementation",
46  Computational Optimization and Applications Vol 41, Nr 2, pp. 185-204, 2008
47 
48  See SPxRatioTester for a class documentation.
49 */
50 class SPxBoundFlippingRT : public SPxFastRT
51 {
52 private:
53  /**@name substructures */
54  //@{
55  /** enumerator to remember which vector we have been searching to find a breakpoint
56  */
57  enum BreakpointSource
58  {
59  FVEC = -1,
60  PVEC = 0,
61  COPVEC = 1
62  };
63 
64  /** breakpoint structure
65  */
66  struct Breakpoint
67  {
68  Real val; /**< breakpoint value (step length) */
69  int idx; /**< index of corresponding row/column */
70  BreakpointSource src; /**< origin of breakpoint, i.e. vector which was searched */
71  };
72 
73  /** Compare class for breakpoints
74  */
75  struct BreakpointCompare
76  {
77  public:
78  /** constructor
79  */
80  BreakpointCompare()
81  : entry(0)
82  {
83  }
84 
85  const Breakpoint* entry;
86 
87  Real operator() (
88  Breakpoint i,
89  Breakpoint j
90  ) const
91  {
92  return i.val - j.val;
93  }
94  };
95  //@}
96 
97  /**@name Data
98  */
99  //@{
100  bool enableLongsteps; /**< enable or disable long steps (bound flips) */
101  Real flipPotential; /**< tracks bound flip history and decides which ratio test to use */
102  int relax_count; /**< count rounds of ratio test */
103  DataArray<Breakpoint> breakpoints; /**< array of breakpoints */
104  SSVector updPrimRhs; /**< right hand side vector of additional system to be solved after the ratio test */
105  DVector updPrimVec; /**< allocation of memory for additional solution vector */
106  //@}
107 
108  /** store all available pivots/breakpoints in an array (positive pivot search direction) */
109  void collectBreakpointsMax(
110  int& nBp, /**< number of found breakpoints so far */
111  int& minIdx, /**< index to current minimal breakpoint */
112  const int* idx, /**< pointer to indices of current vector */
113  int nnz, /**< number of nonzeros in current vector */
114  const Real* upd, /**< pointer to update values of current vector */
115  const Real* vec, /**< pointer to values of current vector */
116  const Real* upp, /**< pointer to upper bound/rhs of current vector */
117  const Real* low, /**< pointer to lower bound/lhs of current vector */
118  BreakpointSource src /**< type of vector (pVec or coPvec)*/
119  );
120 
121  /** store all available pivots/breakpoints in an array (negative pivot search direction) */
122  void collectBreakpointsMin(
123  int& nBp, /**< number of found breakpoints so far */
124  int& minIdx, /**< index to current minimal breakpoint */
125  const int* idx, /**< pointer to indices of current vector */
126  int nnz, /**< number of nonzeros in current vector */
127  const Real* upd, /**< pointer to update values of current vector */
128  const Real* vec, /**< pointer to values of current vector */
129  const Real* upp, /**< pointer to upper bound/rhs of current vector */
130  const Real* low, /**< pointer to lower bound/lhs of current vector */
131  BreakpointSource src /**< type of vector (pVec or coPvec)*/
132  );
133 
134  /** get values for entering index and perform shifts if necessary */
135  bool getData(
136  Real& val,
137  SPxId& enterId,
138  int idx,
139  Real stab,
140  Real degeneps,
141  const Real* upd,
142  const Real* vec,
143  const Real* low,
144  const Real* upp,
145  BreakpointSource src,
146  Real max
147  );
148 
149  /** perform necessary bound flips to restore dual feasibility */
150  void flipAndUpdate(
151  int& usedBp /**< number of bounds that should be flipped */
152  );
153 
154  /** comparison method for breakpoints */
155  static bool isSmaller(
156  Breakpoint x,
157  Breakpoint y
158  )
159  {
160  return (fabs(x.val) < fabs(y.val));
161  };
162 
163 public:
164 
165  void setLongsteps(
166  bool ls
167  )
168  {
169  enableLongsteps = ls;
170  }
171 
172  //-------------------------------------
173  /**@name Construction / destruction */
174  //@{
175  /// default constructor
176  SPxBoundFlippingRT()
177  : SPxFastRT("Bound Flipping")
178  , enableLongsteps(true)
179  , flipPotential(1)
180  , relax_count(0)
181  , breakpoints(10)
182  , updPrimRhs(0)
183  , updPrimVec(0)
184  {}
185  /// copy constructor
186  SPxBoundFlippingRT(const SPxBoundFlippingRT& old)
187  : SPxFastRT(old)
188  , enableLongsteps(true)
189  , flipPotential(1)
190  , relax_count(0)
191  , breakpoints(10)
192  , updPrimRhs(0)
193  , updPrimVec(0)
194  {}
195  /// assignment operator
196  SPxBoundFlippingRT& operator=( const SPxBoundFlippingRT& rhs)
197  {
198  if(this != &rhs)
199  {
200  SPxFastRT::operator=(rhs);
201  }
202 
203  return *this;
204  }
205  /// destructor
206  virtual ~SPxBoundFlippingRT()
207  {}
208  /// clone function for polymorphism
209  inline virtual SPxRatioTester* clone() const
210  {
211  return new SPxBoundFlippingRT(*this);
212  }
213  //@}
214 
215  //-------------------------------------
216  /**@name Select enter/leave */
217  //@{
218  ///
219  virtual int selectLeave(
220  Real& val,
221  SPxId enterId
222  );
223  ///
224  virtual SPxId selectEnter(
225  Real& val,
226  int leaveIdx
227  );
228 
229  //@}
230 };
231 
232 } // namespace soplex
233 #endif // _SPXBOUNDFLIPPINGRT_H_
234 
235 //-----------------------------------------------------------------------------
236 //Emacs Local Variables:
237 //Emacs mode:c++
238 //Emacs c-basic-offset:3
239 //Emacs tab-width:8
240 //Emacs indent-tabs-mode:nil
241 //Emacs End:
242 //-----------------------------------------------------------------------------
© 2003-2013 by Zuse Institute Berlin (ZIB), Imprint Generated on Wed Jan 9 2013 for SoPlex by doxygen