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  spxscaler.h
26   	 * @brief LP scaling base class.
27   	 */
28   	#ifndef _SPXSCALER_H_
29   	#define _SPXSCALER_H_
30   	
31   	#include <assert.h>
32   	
33   	#include "soplex/spxdefines.h"
34   	#include "soplex/dataarray.h"
35   	#include "soplex/vector.h"
36   	#include "soplex/svector.h"
37   	#include "soplex/svset.h"
38   	#include "soplex/dsvector.h"
39   	#include "soplex/dvector.h"
40   	#include <vector>
41   	
42   	namespace soplex
43   	{
44   	
45   	template < class R >
46   	class SPxLPBase;
47   	/**@brief   LP scaler abstract base class.
48   	   @ingroup Algo
49   	
50   	   Instances of classes derived from SPxScaler may be loaded to SoPlex in
51   	   order to scale LPs before solving them. SoPlex will load() itself to
52   	   the SPxScaler and then call #scale(). Generally any SPxLP can be
53   	   loaded to a SPxScaler for #scale()%ing it. The scaling can
54   	   be undone by calling unscale().
55   	
56   	   Mathematically, the scaling of a constraint matrix A can be written
57   	   as \f$ A' = R A C \f$, with \f$ R \f$ and \f$ C \f$, being diagonal matrices
58   	   corresponding to the row and column scale factors, respectively. Besides the
59   	   constraints matrix, also the upper and lower bounds of both columns and rows
60   	   need to be scaled.
61   	
62   	   Note that by default scaling is performed both before and after presolving and
63   	   the former scaling factors are retained during branch-and-bound (persistent scaling).
64   	   However, while within SoPlex the scaled problem is used, data accessed through
65   	   the soplex.cpp interface is provided w.r.t. the original problem (i.e., in unscaled form).
66   	   For instance, consider a scaled constraints matrix A' that is extended by artificial slack
67   	   variables to the matrix (A',I).
68   	   A basis \f$ B' = [(A',I)P]_{[1:m][1:m] }\f$ (with P being a permutation matrix)
69   	   for the scaled problem corresponds to the basis
70   	   \f$ B = R^{-1} [(A',I)P]_{[1:m][1:m]} [P^{T} \tilde{C}^{-1} P]_{[1:m][1:m] } \f$. In
71   	   this equation, \f$ \tilde{C} \f$ is of the form
72   	
73   	   \f[
74   	    \begin{array}{cc}
75   	         C & 0 \\
76   	         O & R^{-1}
77   	   \end{array}
78   	    \f]
79   	
80   	   Note that in SoPlex only scaling factors \f$ 2^k, k \in \mathbb{Z} \f$ are used.
81   	
82   	
83   	*/
84   	
85   	template <class R>
86   	class SPxScaler
87   	{
88   	protected:
89   	
90   	   //-------------------------------------
91   	   /**@name Data */
92   	   ///@{
93   	   const char*        m_name;      ///< Name of the scaler
94   	   DataArray < int >* m_activeColscaleExp; ///< pointer to currently active column scaling factors
95   	   DataArray < int >* m_activeRowscaleExp; ///< pointer to currently active row scaling factors
96   	   bool               m_colFirst;  ///< do column scaling first
97   	   bool               m_doBoth;    ///< do columns and rows
98   	   SPxOut*            spxout;      ///< message handler
99   	   std::shared_ptr<Tolerances> _tolerances; ///< the tolerances
100  	   ///@}
101  	
102  	   //-------------------------------------
103  	   /**@name Protected helpers */
104  	   ///@{
105  	
106  	   /// clear and setup scaling arrays in the LP
107  	   virtual void setup(SPxLPBase<R>& lp);
108  	   ///@}
109  	
110  	public:
111  	
112  	   /// compute a single scaling vector , e.g. of a newly added row
113  	   virtual int computeScaleExp(const SVectorBase<R>& vec, const DataArray<int>& oldScaleExp) const;
114  	
115  	   // The following is now redundant because of the above function.
116  	   // virtual int computeScaleExp(const SVectorBase<Rational>& vec, const DataArray<int>& oldScaleExp) const;
117  	
118  	   /// applies m_colscale and m_rowscale to the \p lp.
119  	   virtual void applyScaling(SPxLPBase<R>& lp);
120  	
121  	
122  	   template <class T>
123  	   friend std::ostream& operator<<(std::ostream& s, const SPxScaler<T>& sc);
124  	
125  	   //-------------------------------------
126  	   /**@name Construction / destruction */
127  	   ///@{
128  	   /// constructor
129  	   explicit SPxScaler(const char* name, bool colFirst = false, bool doBoth = true,
130  	                      SPxOut* spxout = NULL);
131  	   /// copy constructor
132  	   SPxScaler(const SPxScaler&);
133  	   /// assignment operator
134  	   SPxScaler& operator=(const SPxScaler&);
135  	   /// destructor.
136  	   virtual ~SPxScaler();
137  	   /// clone function for polymorphism
138  	   virtual SPxScaler* clone() const = 0;
139  	   ///@}
140  	
141  	   //-------------------------------------
142  	   /**@name Access / modification */
143  	   ///@{
144  	   /// get name of scaler
145  	   virtual const char* getName() const;
146  	   /// set scaling order
147  	   virtual void setOrder(bool colFirst);
148  	   /// set wether column and row scaling should be performed
149  	   virtual void setBoth(bool both);
150  	   /// set message handler
151  	   virtual void setOutstream(SPxOut& newOutstream)
152  	   {
153  	      spxout = &newOutstream;
154  	   }
155  	   /// set R parameter
156  	   virtual void setRealParam(R param, const char* name = "realparam");
157  	   /// set int parameter
158  	   virtual void setIntParam(int param, const char* name = "intparam");
159  	   /// set tolerances
160  	   virtual void setTolerances(std::shared_ptr<Tolerances>& tolerances)
161  	   {
162  	      _tolerances = tolerances;
163  	   }
164  	   /// get the _tolerances member variable
165  	   const std::shared_ptr<Tolerances> tolerances() const
166  	   {
167  	      return _tolerances;
168  	   }
169  	   ///@}
170  	
171  	   //-------------------------------------
172  	   /**@name Scaling */
173  	   ///@{
174  	   /// scale SPxLP.
175  	   virtual void scale(SPxLPBase<R>& lp, bool persistent = true) = 0;
176  	   /// unscale SPxLP
177  	   virtual void unscale(SPxLPBase<R>& lp);
178  	   /// returns scaling factor for column \p i
179  	   virtual int getColScaleExp(int i) const;
180  	   /// returns scaling factor for row \p i
181  	   virtual int getRowScaleExp(int i) const;
182  	   /// gets unscaled column \p i
183  	   virtual void getColUnscaled(const SPxLPBase<R>& lp, int i, DSVectorBase<R>& vec) const;
184  	   /// returns maximum absolute value of unscaled column \p i
185  	   virtual R getColMaxAbsUnscaled(const SPxLPBase<R>& lp, int i) const;
186  	   /// returns minumum absolute value of unscaled column \p i
187  	   virtual R getColMinAbsUnscaled(const SPxLPBase<R>& lp, int i) const;
188  	   /// returns unscaled upper bound \p i
189  	   virtual R upperUnscaled(const SPxLPBase<R>& lp, int i) const;
190  	   /// returns unscaled upper bound vector of \p lp
191  	   virtual void getUpperUnscaled(const SPxLPBase<R>& lp, VectorBase<R>& vec) const;
192  	   /// returns unscaled lower bound \p i
193  	   virtual R lowerUnscaled(const SPxLPBase<R>& lp, int i) const;
194  	   /// gets unscaled lower bound vector
195  	   virtual void getLowerUnscaled(const SPxLPBase<R>& lp, VectorBase<R>& vec) const;
196  	   /// returns unscaled objective function coefficient of \p i
197  	   virtual R maxObjUnscaled(const SPxLPBase<R>& lp, int i) const;
198  	   /// gets unscaled objective function
199  	   virtual void getMaxObjUnscaled(const SPxLPBase<R>& lp, VectorBase<R>& vec) const;
200  	   /// returns unscaled row \p i
201  	   virtual void getRowUnscaled(const SPxLPBase<R>& lp, int i, DSVectorBase<R>& vec) const;
202  	   /// returns maximum absolute value of unscaled row \p i
203  	   virtual R getRowMaxAbsUnscaled(const SPxLPBase<R>& lp, int i) const;
204  	   /// returns minimum absolute value of unscaled row \p i
205  	   virtual R getRowMinAbsUnscaled(const SPxLPBase<R>& lp, int i) const;
206  	   /// returns unscaled right hand side \p i
207  	   virtual R rhsUnscaled(const SPxLPBase<R>& lp, int i) const;
208  	   /// gets unscaled right hand side vector
209  	   virtual void getRhsUnscaled(const SPxLPBase<R>& lp, VectorBase<R>& vec) const;
210  	   /// returns unscaled left hand side \p i of \p lp
211  	   virtual R lhsUnscaled(const SPxLPBase<R>& lp, int i) const;
212  	   /// returns unscaled left hand side vector of \p lp
213  	   virtual void getLhsUnscaled(const SPxLPBase<R>& lp, VectorBase<R>& vec) const;
214  	   /// returns unscaled coefficient of \p lp
215  	   virtual R getCoefUnscaled(const SPxLPBase<R>& lp, int row, int col) const;
216  	   /// unscale dense primal solution vector given in \p x.
217  	   virtual void unscalePrimal(const SPxLPBase<R>& lp, VectorBase<R>& x) const;
218  	   /// unscale dense slack vector given in \p s.
219  	   virtual void unscaleSlacks(const SPxLPBase<R>& lp, VectorBase<R>& s) const;
220  	   /// unscale dense dual solution vector given in \p pi.
221  	   virtual void unscaleDual(const SPxLPBase<R>& lp, VectorBase<R>& pi) const;
222  	   /// unscale dense reduced cost vector given in \p r.
223  	   virtual void unscaleRedCost(const SPxLPBase<R>& lp, VectorBase<R>& r) const;
224  	   /// unscale primal ray given in \p ray.
225  	   virtual void unscalePrimalray(const SPxLPBase<R>& lp, VectorBase<R>& ray) const;
226  	   /// unscale dual ray given in \p ray.
227  	   virtual void unscaleDualray(const SPxLPBase<R>& lp, VectorBase<R>& ray) const;
228  	   /// apply scaling to objective function vector \p origObj.
229  	   virtual void scaleObj(const SPxLPBase<R>& lp, VectorBase<R>& origObj) const;
230  	   /// returns scaled objective function coefficient \p origObj.
231  	   virtual R scaleObj(const SPxLPBase<R>& lp, int i, R origObj) const;
232  	   /// returns scaled LP element in \p row and \p col.
233  	   virtual R scaleElement(const SPxLPBase<R>& lp, int row, int col, R val) const;
234  	   /// returns scaled lower bound of column \p col.
235  	   virtual R scaleLower(const SPxLPBase<R>& lp, int col, R lower) const;
236  	   /// returns scaled upper bound of column \p col.
237  	   virtual R scaleUpper(const SPxLPBase<R>& lp, int col, R upper) const;
238  	   /// returns scaled left hand side of row \p row.
239  	   virtual R scaleLhs(const SPxLPBase<R>& lp, int row, R lhs) const;
240  	   /// returns scaled right hand side of row \p row.
241  	   virtual R scaleRhs(const SPxLPBase<R>& lp, int row, R rhs) const;
242  	   /// absolute smallest column scaling factor
243  	   virtual R minAbsColscale() const;
244  	   /// absolute biggest column scaling factor
245  	   virtual R maxAbsColscale() const;
246  	   /// absolute smallest row scaling factor
247  	   virtual R minAbsRowscale() const;
248  	   /// absolute biggest row scaling factor
249  	   virtual R maxAbsRowscale() const;
250  	   /// maximum ratio between absolute biggest and smallest element in any column.
251  	   virtual R maxColRatio(const SPxLPBase<R>& lp) const;
252  	   /// maximum ratio between absolute biggest and smallest element in any row.
253  	   virtual R maxRowRatio(const SPxLPBase<R>& lp) const;
254  	   /// round vector entries to power of 2
255  	   void computeExpVec(const std::vector<R>& vec, DataArray<int>& vecExp);
256  	   ///@}
257  	
258  	   //-------------------------------------
259  	   /**@name Debugging */
260  	   ///@{
261  	   /// consistency check
262  	   virtual bool isConsistent() const;
263  	   ///@}
264  	};
265  	} // namespace soplex
266  	
267  	// General templated definitions
268  	#include "spxscaler.hpp"
269  	
270  	#endif // _SPXSCALER_H_
271