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