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