SoPlex Doxygen Documentation
spxdevexpr.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 spxdevexpr.h
17  * @brief Devex pricer.
18  */
19 #ifndef _SPXDEVEXPR_H_
20 #define _SPXDEVEXPR_H_
21 
22 #include <assert.h>
23 
24 #include "spxdefines.h"
25 #include "spxpricer.h"
26 
27 namespace soplex
28 {
29 
30 /**@brief Devex pricer.
31  @ingroup Algo
32 
33  The Devex Pricer for SoPlex implements an approximate steepest edge pricing,
34  that does without solving an extra linear system and computing the scalar
35  products.
36 
37  See SPxPricer for a class documentation.
38 
39  @todo There seem to be problems with this pricer especially on the
40  greenbe[ab] problems with the entering algorithm
41  (row representation?).
42 */
43 class SPxDevexPR : public SPxPricer
44 {
45 private:
46 
47  //-------------------------------------
48  /**@name Data */
49  //@{
50  Real last; ///< penalty, selected at last iteration.
51  DVector penalty; ///< vector of pricing penalties.
52  DVector coPenalty; ///< vector of pricing penalties.
53  bool refined; ///< has a refinement step already been tried?
54  int startpricing; ///< index at which partial pricing should start
55  ///@}
56 
57  //-------------------------------------
58  /**@name Private helpers */
59  //@{
60  /// set entering/leaving algorithm
61  void init(SPxSolver::Type);
62  /// internal implementation of SPxPricer::selectLeave()
63  int selectLeaveX(Real& best, Real feastol, int start = 0, int incr = 1);
64  /// implementation of partial pricing
65  int selectLeavePart(Real& best, Real feastol);
66  /// implementation of sparse pricing in the leaving Simplex
67  int selectLeaveSparse(Real& best, Real feastol);
68  /// internal implementation of SPxPricer::left4()
69  void left4X(int n, const SPxId& id, int start, int incr);
70  /// choose the best entering index among columns and rows but prefer sparsity
71  SPxId selectEnterX(Real tol);
72  /// implementation of sparse pricing in the entering Simplex (slack variables)
73  SPxId selectEnterSparseDim(Real& best, Real feastol);
74  /// implementation of sparse pricing in the entering Simplex
75  SPxId selectEnterSparseCoDim(Real& best, Real feastol);
76  /// SPxPricer::selectEnter() in dense case (slack variabels)
77  SPxId selectEnterDenseDim(Real& best, Real feastol, int start = 0, int incr = 1);
78  /// SPxPricer::selectEnter() in dense case
79  SPxId selectEnterDenseCoDim(Real& best, Real feastol, int start = 0, int incr = 1);
80  /// internal implementation of SPxPricer::entered4()
81  void entered4X(SPxId id, int n, int start1, int incr1, int start2, int incr2);
82  //@}
83 
84 public:
85 
86  //-------------------------------------
87  /**@name Construction / destruction */
88  //@{
89  /// default constructor
90  SPxDevexPR()
91  : SPxPricer("Devex")
92  , startpricing(0)
93  {}
94  /// copy constructor
95  SPxDevexPR( const SPxDevexPR& old)
96  : SPxPricer(old)
97  , last(old.last)
98  , penalty(old.penalty)
99  , coPenalty(old.coPenalty)
100  ,startpricing(old.startpricing)
101  {}
102  /// assignment operator
103  SPxDevexPR& operator=( const SPxDevexPR& rhs)
104  {
105  if(this != &rhs)
106  {
107  SPxPricer::operator=(rhs);
108  last = rhs.last;
109  penalty = rhs.penalty;
110  coPenalty = rhs.coPenalty;
111  startpricing = rhs.startpricing;
112  }
113 
114  return *this;
115  }
116  /// destructor
117  virtual ~SPxDevexPR()
118  {}
119  /// clone function for polymorphism
120  inline virtual SPxPricer* clone() const
121  {
122  return new SPxDevexPR(*this);
123  }
124  //@}
125 
126  //-------------------------------------
127  /**@name Access / modification */
128  //@{
129  /// sets the solver
130  virtual void load(SPxSolver* base);
131  /// set entering/leaving algorithm
132  virtual void setType(SPxSolver::Type);
133  /// set row/column representation
134  virtual void setRep(SPxSolver::Representation);
135  ///
136  virtual int selectLeave();
137  ///
138  virtual SPxId selectEnter();
139  ///
140  virtual void left4(int n, SPxId id);
141  ///
142  virtual void entered4(SPxId id, int n);
143  /// \p n vectors have been added to loaded LP.
144  virtual void addedVecs (int n);
145  /// \p n covectors have been added to loaded LP.
146  virtual void addedCoVecs(int n);
147  //@}
148 
149  //-------------------------------------
150  /**@name Consistency check */
151  //@{
152  /// consistency check
153  virtual bool isConsistent() const;
154  //@}
155 };
156 
157 } // namespace soplex
158 #endif // _SPXDEVEXPR_H_
159 
160 //-----------------------------------------------------------------------------
161 //Emacs Local Variables:
162 //Emacs mode:c++
163 //Emacs c-basic-offset:3
164 //Emacs tab-width:8
165 //Emacs indent-tabs-mode:nil
166 //Emacs End:
167 //-----------------------------------------------------------------------------
© 2003-2013 by Zuse Institute Berlin (ZIB), Imprint Generated on Wed Jan 9 2013 for SoPlex by doxygen