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-2019 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 "soplex/spxdefines.h"
25 #include "soplex/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
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_
virtual SPxId selectEnter()
Definition: spxdevexpr.cpp:484
DIdxSet bestPricesCo
set of best pricing candidates
Definition: spxdevexpr.h:54
SPxId buildBestPriceVectorEnterCoDim(Real &best, Real feastol)
Definition: spxdevexpr.cpp:431
virtual ~SPxDevexPR()
destructor
Definition: spxdevexpr.h:119
Devex pricer.The Devex Pricer for SoPlex implements an approximate steepest edge pricing, that does without solving an extra linear system and computing the scalar products.
Definition: spxdevexpr.h:43
Type
Algorithmic type.
Definition: spxsolver.h:124
DataArray< IdxElement > pricesCo
temporary array of precomputed pricing values
Definition: spxdevexpr.h:52
virtual bool isConsistent() const
consistency check
Definition: spxdevexpr.cpp:31
SPxDevexPR()
default constructor
Definition: spxdevexpr.h:96
Abstract pricer base class.
Representation
LP basis representation.
Definition: spxsolver.h:105
SPxPricer & operator=(const SPxPricer &rhs)
assignment operator
Definition: spxpricer.h:277
virtual void left4(int n, SPxId id)
Definition: spxdevexpr.cpp:340
SPxId selectEnterDenseCoDim(Real &best, Real feastol, int start=0, int incr=1)
SPxPricer::selectEnter() in dense case.
Definition: spxdevexpr.cpp:832
SPxId buildBestPriceVectorEnterDim(Real &best, Real feastol)
build up vector of pricing values for later use
Definition: spxdevexpr.cpp:378
Real last
penalty, selected at last iteration.
Definition: spxdevexpr.h:50
SPxDevexPR & operator=(const SPxDevexPR &rhs)
assignment operator
Definition: spxdevexpr.h:108
SPxId selectEnterSparseCoDim(Real &best, Real feastol)
implementation of sparse pricing in the entering Simplex
Definition: spxdevexpr.cpp:758
int buildBestPriceVectorLeave(Real feastol)
build up vector of pricing values for later use
Definition: spxdevexpr.cpp:119
Generic Ids for LP rows or columns.Both SPxColIds and SPxRowIds may be treated uniformly as SPxIds: ...
Definition: spxid.h:85
SPxDevexPR(const SPxDevexPR &old)
copy constructor
Definition: spxdevexpr.h:102
DataArray< IdxElement > prices
temporary array of precomputed pricing values
Definition: spxdevexpr.h:51
double Real
Definition: spxdefines.h:218
int selectLeaveSparse(Real feastol)
implementation of sparse pricing in the leaving Simplex
Definition: spxdevexpr.cpp:225
virtual void setType(SPxSolver::Type)
set entering/leaving algorithm
Definition: spxdevexpr.cpp:77
virtual void setRep(SPxSolver::Representation)
set row/column representation
Definition: spxdevexpr.cpp:99
virtual SPxPricer * clone() const
clone function for polymorphism
Definition: spxdevexpr.h:122
void setupWeights(SPxSolver::Type)
set entering/leaving algorithm
Definition: spxdevexpr.cpp:45
SPxId selectEnterHyperCoDim(Real &best, Real feastol)
implementation of hyper sparse pricing in the entering Simplex
Definition: spxdevexpr.cpp:633
Abstract pricer base class.Class SPxPricer is a pure virtual class defining the interface for pricer ...
Definition: spxpricer.h:46
Dynamic index set.Class DIdxSet provides dynamic IdxSet in the sense, that no restrictions are posed ...
Definition: didxset.h:42
DIdxSet bestPrices
set of best pricing candidates
Definition: spxdevexpr.h:53
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:85
Everything should be within this namespace.
int selectLeaveHyper(Real feastol)
implementation of hyper sparse pricing in the leaving Simplex
Definition: spxdevexpr.cpp:263
virtual int selectLeave()
Definition: spxdevexpr.cpp:166
bool refined
has a refinement step already been tried?
Definition: spxdevexpr.h:55
SPxId selectEnterHyperDim(Real &best, Real feastol)
implementation of hyper sparse pricing in the entering Simplex
Definition: spxdevexpr.cpp:548
int selectLeaveX(Real feastol, int start=0, int incr=1)
internal implementation of SPxPricer::selectLeave()
Definition: spxdevexpr.cpp:197
virtual void entered4(SPxId id, int n)
Definition: spxdevexpr.cpp:870
virtual void addedCoVecs(int n)
n covectors have been added to loaded LP.
Definition: spxdevexpr.cpp:926
virtual void load(SPxSolver *base)
sets the solver
Definition: spxdevexpr.cpp:24
SPxId selectEnterSparseDim(Real &best, Real feastol)
implementation of sparse pricing in the entering Simplex (slack variables)
Definition: spxdevexpr.cpp:718
SPxId selectEnterDenseDim(Real &best, Real feastol, int start=0, int incr=1)
SPxPricer::selectEnter() in dense case (slack variabels)
Definition: spxdevexpr.cpp:798
virtual void addedVecs(int n)
n vectors have been added to loaded LP.
Definition: spxdevexpr.cpp:915
SPxId selectEnterX(Real tol)
choose the best entering index among columns and rows but prefer sparsity
Definition: spxdevexpr.cpp:503