1    	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2    	/*                                                                           */
3    	/*                  This file is part of the class library                   */
4    	/*       SoPlex --- the Sequential object-oriented simPlex.                  */
5    	/*                                                                           */
6    	/*  Copyright (c) 1996-2023 Zuse Institute Berlin (ZIB)                      */
7    	/*                                                                           */
8    	/*  Licensed under the Apache License, Version 2.0 (the "License");          */
9    	/*  you may not use this file except in compliance with the License.         */
10   	/*  You may obtain a copy of the License at                                  */
11   	/*                                                                           */
12   	/*      http://www.apache.org/licenses/LICENSE-2.0                           */
13   	/*                                                                           */
14   	/*  Unless required by applicable law or agreed to in writing, software      */
15   	/*  distributed under the License is distributed on an "AS IS" BASIS,        */
16   	/*  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17   	/*  See the License for the specific language governing permissions and      */
18   	/*  limitations under the License.                                           */
19   	/*                                                                           */
20   	/*  You should have received a copy of the Apache-2.0 license                */
21   	/*  along with SoPlex; see the file LICENSE. If not email to soplex@zib.de.  */
22   	/*                                                                           */
23   	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24   	
25   	/**@file  spxdevexpr.h
26   	 * @brief Devex pricer.
27   	 */
28   	#ifndef _SPXDEVEXPR_H_
29   	#define _SPXDEVEXPR_H_
30   	
31   	#include <assert.h>
32   	
33   	#include "soplex/spxdefines.h"
34   	#include "soplex/spxpricer.h"
35   	
36   	namespace soplex
37   	{
38   	
39   	/**@brief   Devex pricer.
40   	   @ingroup Algo
41   	
42   	   The Devex Pricer for SoPlex implements an approximate steepest edge pricing,
43   	   that does without solving an extra linear system and computing the scalar
44   	   products.
45   	
46   	   See SPxPricer for a class documentation.
47   	
48   	   @todo There seem to be problems with this pricer especially on the
49   	         greenbe[ab] problems with the entering algorithm
50   	         (row representation?).
51   	*/
52   	template <class R>
53   	class SPxDevexPR : public SPxPricer<R>
54   	{
55   	private:
56   	
57   	   //-------------------------------------
58   	   /**@name Data */
59   	   ///@{
60   	   R  last;           ///< penalty, selected at last iteration.
61   	   Array<typename SPxPricer<R>::IdxElement>
62   	   prices;   ///< temporary array of precomputed pricing values
63   	   Array<typename SPxPricer<R>::IdxElement>
64   	   pricesCo; ///< temporary array of precomputed pricing values
65   	   DIdxSet bestPrices;   ///< set of best pricing candidates
66   	   DIdxSet bestPricesCo; ///< set of best pricing candidates
67   	   bool refined;         ///< has a refinement step already been tried?
68   	   ///@}
69   	
70   	   //-------------------------------------
71   	   /**@name Private helpers */
72   	   ///@{
73   	   /// set entering/leaving algorithm
74   	   void setupWeights(typename SPxSolverBase<R>::Type);
75   	   /// build up vector of pricing values for later use
76   	   int buildBestPriceVectorLeave(R feastol);
77   	   /// internal implementation of SPxPricer::selectLeave()
78   	   int selectLeaveX(R feastol, int start = 0, int incr = 1);
79   	   /// implementation of sparse pricing in the leaving Simplex
80   	   int selectLeaveSparse(R feastol);
81   	   /// implementation of hyper sparse pricing in the leaving Simplex
82   	   int selectLeaveHyper(R feastol);
83   	   /// build up vector of pricing values for later use
84   	   SPxId buildBestPriceVectorEnterDim(R& best, R feastol);
85   	   SPxId buildBestPriceVectorEnterCoDim(R& best, R feastol);
86   	   /// choose the best entering index among columns and rows but prefer sparsity
87   	   SPxId selectEnterX(R tol);
88   	   /// implementation of sparse pricing in the entering Simplex (slack variables)
89   	   SPxId selectEnterSparseDim(R& best, R feastol);
90   	   /// implementation of sparse pricing in the entering Simplex
91   	   SPxId selectEnterSparseCoDim(R& best, R feastol);
92   	   /// SPxPricer::selectEnter() in dense case (slack variabels)
93   	   SPxId selectEnterDenseDim(R& best, R feastol, int start = 0, int incr = 1);
94   	   /// SPxPricer::selectEnter() in dense case
95   	   SPxId selectEnterDenseCoDim(R& best, R feastol, int start = 0, int incr = 1);
96   	   /// implementation of hyper sparse pricing in the entering Simplex
97   	   SPxId selectEnterHyperDim(R& best, R feastol);
98   	   /// implementation of hyper sparse pricing in the entering Simplex
99   	   SPxId selectEnterHyperCoDim(R& best, R feastol);
100  	   ///@}
101  	
102  	public:
103  	
104  	   //-------------------------------------
105  	   /**@name Construction / destruction */
106  	   ///@{
107  	   /// default constructor
108  	   SPxDevexPR()
109  	      : SPxPricer<R>("Devex")
110  	      , last(0)
111  	      , refined(false)
112  	   {}
113  	   /// copy constructor
114  	   SPxDevexPR(const SPxDevexPR& old)
115  	      : SPxPricer<R>(old)
116  	      , last(old.last)
117  	      , refined(false)
118  	   {}
119  	   /// assignment operator
120  	   SPxDevexPR& operator=(const SPxDevexPR& rhs)
121  	   {
122  	      if(this != &rhs)
123  	      {
124  	         SPxPricer<R>::operator=(rhs);
125  	         last = rhs.last;
126  	      }
127  	
128  	      return *this;
129  	   }
130  	   /// destructor
131  	   virtual ~SPxDevexPR()
132  	   {}
133  	   /// clone function for polymorphism
134  	   inline virtual SPxPricer<R>* clone()  const
135  	   {
136  	      return new SPxDevexPR(*this);
137  	   }
138  	   ///@}
139  	
140  	   //-------------------------------------
141  	   /**@name Access / modification */
142  	   ///@{
143  	   /// sets the solver
144  	   virtual void load(SPxSolverBase<R>* base);
145  	   /// set entering/leaving algorithm
146  	   virtual void setType(typename SPxSolverBase<R>::Type);
147  	   /// set row/column representation
148  	   virtual void setRep(typename SPxSolverBase<R>::Representation);
149  	   ///
150  	   virtual int selectLeave();
151  	   ///
152  	   virtual SPxId selectEnter();
153  	   ///
154  	   virtual void left4(int n, SPxId id);
155  	   ///
156  	   virtual void entered4(SPxId id, int n);
157  	   /// \p n vectors have been added to loaded LP.
158  	   virtual void addedVecs(int n);
159  	   /// \p n covectors have been added to loaded LP.
160  	   virtual void addedCoVecs(int n);
161  	   ///@}
162  	
163  	   //-------------------------------------
164  	   /**@name Consistency check */
165  	   ///@{
166  	   /// consistency check
167  	   virtual bool isConsistent() const;
168  	   ///@}
169  	};
170  	
171  	} // namespace soplex
172  	
173  	#include "spxdevexpr.hpp"
174  	
175  	#endif // _SPXDEVEXPR_H_
176