Scippy

SoPlex

Sequential object-oriented simPlex

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