Scippy

SoPlex

Sequential object-oriented simPlex

spxsteeppr.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-2017 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 
17 /**@file spxsteeppr.h
18  * @brief Steepest edge pricer.
19  */
20 #ifndef _SPXSTEEPPR_H_
21 #define _SPXSTEEPPR_H_
22 
23 
24 #include <assert.h>
25 
26 #include "spxdefines.h"
27 #include "spxpricer.h"
28 #include "random.h"
29 
30 namespace soplex
31 {
32 
33 /**@brief Steepest edge pricer.
34  @ingroup Algo
35 
36  Class SPxSteepPR implements a steepest edge pricer to be used with
37  SoPlex.
38 
39  See SPxPricer for a class documentation.
40 */
41 class SPxSteepPR : public SPxPricer
42 {
43 public:
44 
45  //-------------------------------------
46  /**@name Types */
47  //@{
48  /// How to setup the direction multipliers.
49  /** Possible settings are #EXACT for starting with exactly computed
50  values, or #DEFAULT for starting with multipliers set to 1. The
51  latter is the default.
52  */
53  enum Setup {
54  EXACT, ///< starting with exactly computed values
55  DEFAULT ///< starting with multipliers set to 1
56  };
57  //@}
58  /// setup steepest edge weights
59  void setupWeights(SPxSolver::Type type);
60 
61 private:
62 
63  //-------------------------------------
64  /**@name Data */
65  //@{
66  /// working vector
68  /// working vector
70  /// temporary array of precomputed pricing values
72  /// temporary array of precomputed pricing values
74  /// array of best pricing candidates
76  /// array of best pricing candidates
78  ///
80  /// setup type.
82  /// has a refinement step already been tried?
83  bool refined;
84  //@}
85 
86  //-------------------------------------
87  /// prepare data structures for hyper sparse pricing
88  int buildBestPriceVectorLeave( Real feastol );
89  /// implementation of full pricing
90  int selectLeaveX(Real tol);
91  /// implementation of sparse pricing in the leaving Simplex
92  int selectLeaveSparse(Real tol);
93  /// implementation of hyper sparse pricing in the leaving Simplex
94  int selectLeaveHyper(Real tol);
95  /// build up vector of pricing values for later use
98  /// choose the best entering index among columns and rows but prefer sparsity
99  SPxId selectEnterX(Real tol);
100  /// implementation of sparse pricing for the entering Simplex (slack variables)
101  SPxId selectEnterSparseDim(Real& best, Real tol);
102  /// implementation of sparse pricing for the entering Simplex
104  /// implementation of selectEnter() in dense case (slack variables)
105  SPxId selectEnterDenseDim(Real& best, Real tol);
106  /// implementation of selectEnter() in dense case
107  SPxId selectEnterDenseCoDim(Real& best, Real tol);
108  /// implementation of hyper sparse pricing in the entering Simplex
109  SPxId selectEnterHyperDim(Real& best, Real feastol);
110  /// implementation of hyper sparse pricing in the entering Simplex
111  SPxId selectEnterHyperCoDim(Real& best, Real feastol);
112 
113 public:
114 
115  //-------------------------------------
116  /**@name Construction / destruction */
117  //@{
118  ///
119  SPxSteepPR(const char* name = "Steep", Setup mode = DEFAULT)
120  : SPxPricer(name)
121  , workVec (0)
122  , workRhs (0)
123  , pi_p(1.0)
124  , setup (mode)
125  , refined(false)
126  {
127  assert(isConsistent());
128  }
129  /// copy constructor
130  SPxSteepPR( const SPxSteepPR& old)
131  : SPxPricer(old)
132  , workVec(old.workVec)
133  , workRhs(old.workRhs)
134  , pi_p(old.pi_p)
135  , setup(old.setup)
136  , refined(old.refined)
137  {
138  assert(isConsistent());
139  }
140  /// assignment operator
142  {
143  if(this != &rhs)
144  {
146  workVec = rhs.workVec;
147  workRhs = rhs.workRhs;
148  pi_p = rhs.pi_p;
149  setup = rhs.setup;
150  refined = rhs.refined;
151 
152  assert(isConsistent());
153  }
154 
155  return *this;
156  }
157  /// destructor
158  virtual ~SPxSteepPR()
159  {}
160  /// clone function for polymorphism
161  inline virtual SPxPricer* clone() const
162  {
163  return new SPxSteepPR(*this);
164  }
165  //@}
166 
167  //-------------------------------------
168  /**@name Access / modification */
169  //@{
170  /// sets the solver
171  virtual void load(SPxSolver* base);
172  /// clear solver and preferences
173  virtual void clear();
174  /// set entering/leaving algorithm
175  virtual void setType(SPxSolver::Type);
176  /// set row/column representation
177  virtual void setRep(SPxSolver::Representation rep);
178  ///
179  virtual int selectLeave();
180  ///
181  virtual void left4(int n, SPxId id);
182  ///
183  virtual SPxId selectEnter();
184  ///
185  virtual void entered4(SPxId id, int n);
186  /// \p n vectors have been added to loaded LP.
187  virtual void addedVecs (int n);
188  /// \p n covectors have been added to loaded LP.
189  virtual void addedCoVecs(int n);
190  /// \p the i'th vector has been removed from the loaded LP.
191  virtual void removedVec(int i);
192  /// \p the i'th covector has been removed from the loaded LP.
193  virtual void removedCoVec(int i);
194  /// \p n vectors have been removed from loaded LP.
195  virtual void removedVecs(const int perm[]);
196  /// \p n covectors have been removed from loaded LP.
197  virtual void removedCoVecs(const int perm[]);
198  //@}
199 
200  //-------------------------------------
201  /**@name Consistency check */
202  //@{
203  ///
204  virtual bool isConsistent() const;
205  //@}
206 };
207 
208 } // namespace soplex
209 #endif // _SPXSTEEPPR_H_
Random numbers.
virtual SPxId selectEnter()
Definition: spxsteeppr.cpp:600
int selectLeaveX(Real tol)
implementation of full pricing
Definition: spxsteeppr.cpp:297
SPxId selectEnterHyperCoDim(Real &best, Real feastol)
implementation of hyper sparse pricing in the entering Simplex
Definition: spxsteeppr.cpp:743
int buildBestPriceVectorLeave(Real feastol)
prepare data structures for hyper sparse pricing
Definition: spxsteeppr.cpp:209
SPxSteepPR(const SPxSteepPR &old)
copy constructor
Definition: spxsteeppr.h:130
SPxSteepPR(const char *name="Steep", Setup mode=DEFAULT)
Definition: spxsteeppr.h:119
virtual void setType(SPxSolver::Type)
set entering/leaving algorithm
Definition: spxsteeppr.cpp:51
Type
Algorithmic type.
Definition: spxsolver.h:124
DIdxSet bestPrices
array of best pricing candidates
Definition: spxsteeppr.h:75
Abstract pricer base class.
virtual void load(SPxSolver *base)
sets the solver
Definition: spxsteeppr.cpp:38
Representation
LP basis representation.
Definition: spxsolver.h:105
Setup
How to setup the direction multipliers.
Definition: spxsteeppr.h:53
SPxPricer & operator=(const SPxPricer &rhs)
assignment operator
Definition: spxpricer.h:277
DataArray< IdxElement > prices
temporary array of precomputed pricing values
Definition: spxsteeppr.h:71
starting with multipliers set to 1
Definition: spxsteeppr.h:55
virtual int selectLeave()
Definition: spxsteeppr.cpp:253
virtual void addedCoVecs(int n)
n covectors have been added to loaded LP.
Definition: spxsteeppr.cpp:946
SSVector workVec
working vector
Definition: spxsteeppr.h:67
SPxSteepPR & operator=(const SPxSteepPR &rhs)
assignment operator
Definition: spxsteeppr.h:141
Generic Ids for LP rows or columns.Both SPxColIds and SPxRowIds may be treated uniformly as SPxIds: ...
Definition: spxid.h:85
double Real
Definition: spxdefines.h:218
SPxId selectEnterX(Real tol)
choose the best entering index among columns and rows but prefer sparsity
Definition: spxsteeppr.cpp:630
bool refined
has a refinement step already been tried?
Definition: spxsteeppr.h:83
virtual void setRep(SPxSolver::Representation rep)
set row/column representation
Definition: spxsteeppr.cpp:150
virtual void entered4(SPxId id, int n)
Definition: spxsteeppr.cpp:430
virtual bool isConsistent() const
virtual void left4(int n, SPxId id)
Definition: spxsteeppr.cpp:163
virtual void addedVecs(int n)
n vectors have been added to loaded LP.
Definition: spxsteeppr.cpp:933
Abstract pricer base class.Class SPxPricer is a pure virtual class defining the interface for pricer ...
Definition: spxpricer.h:46
starting with exactly computed values
Definition: spxsteeppr.h:54
DataArray< IdxElement > pricesCo
temporary array of precomputed pricing values
Definition: spxsteeppr.h:73
Dynamic index set.Class DIdxSet provides dynamic IdxSet in the sense, that no restrictions are posed ...
Definition: didxset.h:42
virtual ~SPxSteepPR()
destructor
Definition: spxsteeppr.h:158
DIdxSet bestPricesCo
array of best pricing candidates
Definition: spxsteeppr.h:77
SPxId selectEnterSparseCoDim(Real &best, Real tol)
implementation of sparse pricing for the entering Simplex
Definition: spxsteeppr.cpp:852
SPxId selectEnterHyperDim(Real &best, Real feastol)
implementation of hyper sparse pricing in the entering Simplex
Definition: spxsteeppr.cpp:666
Debugging, floating point type and parameter definitions.
Sequential object-oriented SimPlex.SPxSolver is an LP solver class using the revised Simplex algorith...
Definition: spxsolver.h:84
int selectLeaveHyper(Real tol)
implementation of hyper sparse pricing in the leaving Simplex
Definition: spxsteeppr.cpp:359
Everything should be within this namespace.
void setupWeights(SPxSolver::Type type)
setup steepest edge weights
Definition: spxsteeppr.cpp:72
int selectLeaveSparse(Real tol)
implementation of sparse pricing in the leaving Simplex
Definition: spxsteeppr.cpp:324
SPxId buildBestPriceVectorEnterDim(Real &best, Real feastol)
build up vector of pricing values for later use
Definition: spxsteeppr.cpp:494
virtual void clear()
clear solver and preferences
Definition: spxsteeppr.cpp:33
virtual void removedVec(int i)
the i&#39;th vector has been removed from the loaded LP.
Definition: spxsteeppr.cpp:956
virtual void removedCoVec(int i)
the i&#39;th covector has been removed from the loaded LP.
Definition: spxsteeppr.cpp:981
Setup setup
setup type.
Definition: spxsteeppr.h:81
virtual SPxPricer * clone() const
clone function for polymorphism
Definition: spxsteeppr.h:161
SPxId selectEnterDenseCoDim(Real &best, Real tol)
implementation of selectEnter() in dense case
Definition: spxsteeppr.cpp:908
SSVector workRhs
working vector
Definition: spxsteeppr.h:69
SPxId buildBestPriceVectorEnterCoDim(Real &best, Real feastol)
Definition: spxsteeppr.cpp:547
virtual void removedCoVecs(const int perm[])
n covectors have been removed from loaded LP.
Definition: spxsteeppr.cpp:989
SPxId selectEnterDenseDim(Real &best, Real tol)
implementation of selectEnter() in dense case (slack variables)
Definition: spxsteeppr.cpp:884
Steepest edge pricer.Class SPxSteepPR implements a steepest edge pricer to be used with SoPlex...
Definition: spxsteeppr.h:41
SPxId selectEnterSparseDim(Real &best, Real tol)
implementation of sparse pricing for the entering Simplex (slack variables)
Definition: spxsteeppr.cpp:820
virtual void removedVecs(const int perm[])
n vectors have been removed from loaded LP.
Definition: spxsteeppr.cpp:964