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  spxsimplifier.h
26   	 * @brief LP simplification base class.
27   	 */
28   	#ifndef _SPXSIMPLIFIER_H_
29   	#define _SPXSIMPLIFIER_H_
30   	
31   	#include <assert.h>
32   	
33   	#include "soplex/spxdefines.h"
34   	#include "soplex/timerfactory.h"
35   	#include "soplex/spxlp.h"
36   	#include "soplex/spxsolver.h"
37   	
38   	namespace soplex
39   	{
40   	/**@brief   LP simplification abstract base class.
41   	   @ingroup Algo
42   	
43   	   Instances of classes derived from SPxSimplifier may be loaded to SoPlex in
44   	   order to simplify LPs before solving them. SoPlex will call #simplify()
45   	   on itself. Generally any SPxLP can be given to
46   	   a SPxSimplifier for #simplify()%ing it. The simplification cannot be undone,
47   	   but given an primal/dual solution for the simplified SPxLP, the simplifier
48   	   can reconstruct the primal/dual solution of the unsimplified LP.
49   	*/
50   	template <class R>
51   	class SPxSimplifier
52   	{
53   	protected:
54   	   //-------------------------------------
55   	   /**@name Protected Data */
56   	   ///@{
57   	   /// name of the simplifier
58   	   const char* m_name;
59   	   /// user time used for simplification
60   	   Timer*      m_timeUsed;
61   	   Timer::TYPE m_timerType;
62   	   /// number of removed rows
63   	   int         m_remRows;
64   	   /// number of removed columns
65   	   int         m_remCols;
66   	   /// number of removed nonzero coefficients
67   	   int         m_remNzos;
68   	   /// number of changed bounds
69   	   int         m_chgBnds;
70   	   /// number of change right-hand sides
71   	   int         m_chgLRhs;
72   	   /// number of kept bounds
73   	   int         m_keptBnds;
74   	   /// number of kept left- and right-hand sides
75   	   int         m_keptLRhs;
76   	   /// objective offset
77   	   R        m_objoffset;
78   	   /// minimal reduction (sum of removed rows/cols) to continue simplification
79   	   R        m_minReduction;
80   	   /// message handler
81   	   SPxOut*     spxout;
82   	   ///< tolerances used by the solver
83   	   std::shared_ptr<Tolerances> _tolerances;
84   	   ///@}
85   	
86   	public:
87   	
88   	   //-------------------------------------
89   	   /**@name Types */
90   	   ///@{
91   	   /// Result of the simplification.
92   	   enum Result
93   	   {
94   	      OKAY            =  0,  ///< simplification could be done
95   	      INFEASIBLE      =  1,  ///< primal infeasibility was detected
96   	      DUAL_INFEASIBLE =  2,  ///< dual infeasibility was detected
97   	      UNBOUNDED       =  3,  ///< primal unboundedness was detected
98   	      VANISHED        =  4   ///< the problem was so much simplified that it vanished
99   	   };
100  	   ///@}
101  	
102  	   //-------------------------------------
103  	   /**@name Types */
104  	   ///@{
105  	   /// constructor
106  	   explicit SPxSimplifier(const char* p_name, Timer::TYPE ttype = Timer::USER_TIME)
107  	      : m_name(p_name)
108  	      , m_timeUsed(0)
109  	      , m_timerType(ttype)
110  	      , m_remRows(0)
111  	      , m_remCols(0)
112  	      , m_remNzos(0)
113  	      , m_chgBnds(0)
114  	      , m_chgLRhs(0)
115  	      , m_keptBnds(0)
116  	      , m_keptLRhs(0)
117  	      , m_objoffset(0.0)
118  	      , m_minReduction(1e-4)
119  	      , spxout(0)
120  	   {
121  	      assert(isConsistent());
122  	
123  	      m_timeUsed = TimerFactory::createTimer(ttype);
124  	   }
125  	   /// copy constructor
126  	   SPxSimplifier(const SPxSimplifier& old)
127  	      : m_name(old.m_name)
128  	      , m_timerType(old.m_timerType)
129  	      , m_remRows(old.m_remRows)
130  	      , m_remCols(old.m_remCols)
131  	      , m_remNzos(old.m_remNzos)
132  	      , m_chgBnds(old.m_chgBnds)
133  	      , m_chgLRhs(old.m_chgLRhs)
134  	      , m_keptBnds(old.m_keptBnds)
135  	      , m_keptLRhs(old.m_keptLRhs)
136  	      , m_objoffset(old.m_objoffset)
137  	      , m_minReduction(old.m_minReduction)
138  	      , spxout(old.spxout)
139  	   {
140  	      m_timeUsed = TimerFactory::createTimer(m_timerType);
141  	      assert(isConsistent());
142  	   }
143  	   /// assignment operator
144  	   SPxSimplifier& operator=(const SPxSimplifier& rhs)
145  	   {
146  	      if(this != &rhs)
147  	      {
148  	         m_name = rhs.m_name;
149  	         *m_timeUsed = *(rhs.m_timeUsed);
150  	         m_timerType = rhs.m_timerType;
151  	         m_remRows = rhs.m_remRows;
152  	         m_remCols = rhs.m_remCols;
153  	         m_remNzos = rhs.m_remNzos;
154  	         m_chgBnds = rhs.m_chgBnds;
155  	         m_chgLRhs = rhs.m_chgLRhs;
156  	         m_keptBnds = rhs.m_keptBnds;
157  	         m_keptLRhs = rhs.m_keptLRhs;
158  	         m_objoffset = rhs.m_objoffset;
159  	         m_minReduction = rhs.m_minReduction;
160  	         spxout = rhs.spxout;
161  	
162  	         assert(isConsistent());
163  	      }
164  	
165  	      return *this;
166  	   }
167  	   /// destructor.
168  	   virtual ~SPxSimplifier()
169  	   {
170  	      m_name = nullptr;
171  	      m_timeUsed->~Timer();
172  	      spx_free(m_timeUsed);
173  	   }
174  	   /// clone function for polymorphism
175  	   virtual SPxSimplifier* clone() const = 0;
176  	   ///@}
177  	
178  	   //-------------------------------------
179  	   /**@name Access / modfication */
180  	   ///@{
181  	   /// get name of simplifier.
182  	   virtual const char* getName() const
183  	   {
184  	      return m_name;
185  	   }
186  	   virtual R timeUsed() const
187  	   {
188  	      return m_timeUsed->time();
189  	   }
190  	   ///@}
191  	
192  	   //-------------------------------------
193  	   /**@name Simplifying / unsimplifying */
194  	   ///@{
195  	   /// simplify SPxLP \p lp
196  	   virtual Result simplify(SPxLPBase<R>& lp, Real remainingTime,
197  	                           bool keepbounds = false, uint32_t seed = 0) = 0;
198  	   /// reconstructs an optimal solution for the unsimplified LP.
199  	   virtual void unsimplify(const VectorBase<R>&, const VectorBase<R>&, const VectorBase<R>&,
200  	                           const VectorBase<R>&,
201  	                           const typename SPxSolverBase<R>::VarStatus[], const typename SPxSolverBase<R>::VarStatus[],
202  	                           bool isOptimal = true) = 0;
203  	   /// returns result status of the simplification
204  	   virtual Result result() const = 0;
205  	   /// specifies whether an optimal solution has already been unsimplified.
206  	   virtual bool isUnsimplified() const
207  	   {
208  	      return false;
209  	   }
210  	   /// returns a reference to the unsimplified primal solution.
211  	   virtual const VectorBase<R>& unsimplifiedPrimal() = 0;
212  	
213  	   /// returns a reference to the unsimplified dual solution.
214  	   virtual const VectorBase<R>& unsimplifiedDual() = 0;
215  	
216  	   /// returns a reference to the unsimplified slack values.
217  	   virtual const VectorBase<R>& unsimplifiedSlacks() = 0;
218  	
219  	   /// returns a reference to the unsimplified reduced costs.
220  	   virtual const VectorBase<R>& unsimplifiedRedCost() = 0;
221  	
222  	   /// gets basis status for a single row.
223  	   virtual typename SPxSolverBase<R>::VarStatus getBasisRowStatus(int) const = 0;
224  	
225  	   /// gets basis status for a single column.
226  	   virtual typename SPxSolverBase<R>::VarStatus getBasisColStatus(int) const = 0;
227  	
228  	   /// get optimal basis.
229  	   virtual void getBasis(typename SPxSolverBase<R>::VarStatus[],
230  	                         typename SPxSolverBase<R>::VarStatus[], const int rowsSize = -1, const int colsSize = -1) const = 0;
231  	
232  	   /// get objective offset.
233  	   virtual R getObjoffset() const
234  	   {
235  	      return m_objoffset;
236  	   }
237  	
238  	   /// add objective offset.
239  	   virtual void addObjoffset(const R val)
240  	   {
241  	      m_objoffset += val;
242  	   }
243  	
244  	   /// set minimal reduction threshold to continue simplification
245  	   virtual void setMinReduction(const R minRed)
246  	   {
247  	      m_minReduction = minRed;
248  	   }
249  	
250  	   ///@}
251  	
252  	   //-------------------------------------
253  	   /**@name Consistency check */
254  	   ///@{
255  	   /// consistency check
256  	   virtual bool isConsistent() const
257  	   {
258  	      return true;
259  	   }
260  	   ///@}
261  	
262  	   void setOutstream(SPxOut& newOutstream)
263  	   {
264  	      spxout = &newOutstream;
265  	   }
266  	
267  	   /// set the _tolerances member variable
268  	   virtual void setTolerances(std::shared_ptr<Tolerances> newTolerances)
269  	   {
270  	      this->_tolerances = newTolerances;
271  	   }
272  	   /// get the _tolerances member variable
273  	   const std::shared_ptr<Tolerances> tolerances() const
274  	   {
275  	      return _tolerances;
276  	   }
277  	
278  	};
279  	
280  	/// Pretty-printing of simplifier status
281  	template <class R>
282  	std::ostream& operator<<(std::ostream& os, const typename SPxSimplifier<R>::Result& status);
283  	
284  	} // namespace soplex
285  	#endif // _SPXSIMPLIFIER_H_
286