Scippy

SoPlex

Sequential object-oriented simPlex

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-2015 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  DataArray<IdxElement> prices; ///< temporary array of precomputed pricing values
52  DataArray<IdxElement> pricesCo; ///< temporary array of precomputed pricing values
53  DIdxSet bestPrices; ///< set of best pricing candidates
54  DIdxSet bestPricesCo; ///< set of best pricing candidates
55  bool refined; ///< has a refinement step already been tried?
56  ///@}
57 
58  //-------------------------------------
59  /**@name Private helpers */
60  //@{
61  /// set entering/leaving algorithm
62  void init(SPxSolver::Type);
63  /// build up vector of pricing values for later use
64  int buildBestPriceVectorLeave(Real feastol);
65  /// internal implementation of SPxPricer::selectLeave()
66  int selectLeaveX(Real feastol, int start = 0, int incr = 1);
67  /// implementation of sparse pricing in the leaving Simplex
68  int selectLeaveSparse(Real feastol);
69  /// implementation of hyper sparse pricing in the leaving Simplex
70  int selectLeaveHyper(Real feastol);
71  /// build up vector of pricing values for later use
74  /// choose the best entering index among columns and rows but prefer sparsity
75  SPxId selectEnterX(Real tol);
76  /// implementation of sparse pricing in the entering Simplex (slack variables)
77  SPxId selectEnterSparseDim(Real& best, Real feastol);
78  /// implementation of sparse pricing in the entering Simplex
79  SPxId selectEnterSparseCoDim(Real& best, Real feastol);
80  /// SPxPricer::selectEnter() in dense case (slack variabels)
81  SPxId selectEnterDenseDim(Real& best, Real feastol, int start = 0, int incr = 1);
82  /// SPxPricer::selectEnter() in dense case
83  SPxId selectEnterDenseCoDim(Real& best, Real feastol, int start = 0, int incr = 1);
84  /// implementation of hyper sparse pricing in the entering Simplex
85  SPxId selectEnterHyperDim(Real& best, Real feastol);
86  /// implementation of hyper sparse pricing in the entering Simplex
87  SPxId selectEnterHyperCoDim(Real& best, Real feastol);
88  //@}
89 
90 public:
91 
92  //-------------------------------------
93  /**@name Construction / destruction */
94  //@{
95  /// default constructor
97  : SPxPricer("Devex")
98  , last(0)
99  , refined(false)
100  {}
101  /// copy constructor
102  SPxDevexPR( const SPxDevexPR& old)
103  : SPxPricer(old)
104  , last(old.last)
105  , refined(false)
106  {}
107  /// assignment operator
109  {
110  if(this != &rhs)
111  {
113  last = rhs.last;
114  }
115 
116  return *this;
117  }
118  /// destructor
119  virtual ~SPxDevexPR()
120  {}
121  /// clone function for polymorphism
122  inline virtual SPxPricer* clone() const
123  {
124  return new SPxDevexPR(*this);
125  }
126  //@}
127 
128  //-------------------------------------
129  /**@name Access / modification */
130  //@{
131  /// sets the solver
132  virtual void load(SPxSolver* base);
133  /// set entering/leaving algorithm
134  virtual void setType(SPxSolver::Type);
135  /// set row/column representation
136  virtual void setRep(SPxSolver::Representation);
137  ///
138  virtual int selectLeave();
139  ///
140  virtual SPxId selectEnter();
141  ///
142  virtual void left4(int n, SPxId id);
143  ///
144  virtual void entered4(SPxId id, int n);
145  /// \p n vectors have been added to loaded LP.
146  virtual void addedVecs (int n);
147  /// \p n covectors have been added to loaded LP.
148  virtual void addedCoVecs(int n);
149  //@}
150 
151  //-------------------------------------
152  /**@name Consistency check */
153  //@{
154  /// consistency check
155  virtual bool isConsistent() const;
156  //@}
157 };
158 
159 } // namespace soplex
160 #endif // _SPXDEVEXPR_H_