SoPlex Documentation
Loading...
Searching...
No Matches
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-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
38namespace 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*/
50template <class R>
52{
53protected:
54
55 //-------------------------------------
56 /**@name Protected Data */
57 ///@{
58 /// name of the simplifier
59 const char* m_name;
60 /// user time used for simplification
63 /// number of removed rows
65 /// number of removed columns
67 /// number of removed nonzero coefficients
69 /// number of changed bounds
71 /// number of change right-hand sides
73 /// number of kept bounds
75 /// number of kept left- and right-hand sides
77 /// objective offset
79 /// minimal reduction (sum of removed rows/cols) to continue simplification
81 /// message handler
83 ///@}
84
85public:
86
87 //-------------------------------------
88 /**@name Types */
89 ///@{
90 /// Result of the simplification.
91 enum Result
92 {
93 OKAY = 0, ///< simplification could be done
94 INFEASIBLE = 1, ///< primal infeasibility was detected
95 DUAL_INFEASIBLE = 2, ///< dual infeasibility was detected
96 UNBOUNDED = 3, ///< primal unboundedness was detected
97 VANISHED = 4 ///< the problem was so much simplified that it vanished
98 };
99 ///@}
100
101 //-------------------------------------
102 /**@name Types */
103 ///@{
104 /// constructor
106 : m_name(p_name)
107 , m_timeUsed(0)
109 , m_remRows(0)
110 , m_remCols(0)
111 , m_remNzos(0)
112 , m_chgBnds(0)
113 , m_chgLRhs(0)
114 , m_keptBnds(0)
115 , m_keptLRhs(0)
116 , m_objoffset(0.0)
117 , m_minReduction(1e-4)
118 , spxout(0)
119 {
121
123 }
124 /// copy constructor
142 /// assignment operator
144 {
145 if(this != &rhs)
146 {
147 m_name = rhs.m_name;
148 *m_timeUsed = *(rhs.m_timeUsed);
150 m_remRows = rhs.m_remRows;
151 m_remCols = rhs.m_remCols;
152 m_remNzos = rhs.m_remNzos;
153 m_chgBnds = rhs.m_chgBnds;
154 m_chgLRhs = rhs.m_chgLRhs;
159 spxout = rhs.spxout;
160
162 }
163
164 return *this;
165 }
166 /// destructor.
168 {
169 m_name = nullptr;
172 }
173 /// clone function for polymorphism
174 virtual SPxSimplifier* clone() const = 0;
175 ///@}
176
177 //-------------------------------------
178 /**@name Access / modfication */
179 ///@{
180 /// get name of simplifier.
181 virtual const char* getName() const
182 {
183 return m_name;
184 }
185 virtual R timeUsed() const
186 {
187 return m_timeUsed->time();
188 }
189 ///@}
190
191 //-------------------------------------
192 /**@name Simplifying / unsimplifying */
193 ///@{
194 /// simplify SPxLP \p lp with identical primal and dual feasibility tolerance.
195 virtual Result simplify(SPxLPBase<R>& lp, R eps, R delta, Real remainingTime) = 0;
196 /// simplify SPxLP \p lp with independent primal and dual feasibility tolerance.
197 virtual Result simplify(SPxLPBase<R>& lp, R eps, R feastol, R opttol, Real remainingTime,
198 bool keepbounds = false, uint32_t seed = 0) = 0;
199 /// reconstructs an optimal solution for the unsimplified LP.
200 virtual void unsimplify(const VectorBase<R>&, const VectorBase<R>&, const VectorBase<R>&,
201 const VectorBase<R>&,
202 const typename SPxSolverBase<R>::VarStatus[], const typename SPxSolverBase<R>::VarStatus[],
203 bool isOptimal = true) = 0;
204 /// returns result status of the simplification
205 virtual Result result() const = 0;
206 /// specifies whether an optimal solution has already been unsimplified.
207 virtual bool isUnsimplified() const
208 {
209 return false;
210 }
211 /// returns a reference to the unsimplified primal solution.
212 virtual const VectorBase<R>& unsimplifiedPrimal() = 0;
213
214 /// returns a reference to the unsimplified dual solution.
215 virtual const VectorBase<R>& unsimplifiedDual() = 0;
216
217 /// returns a reference to the unsimplified slack values.
218 virtual const VectorBase<R>& unsimplifiedSlacks() = 0;
219
220 /// returns a reference to the unsimplified reduced costs.
221 virtual const VectorBase<R>& unsimplifiedRedCost() = 0;
222
223 /// gets basis status for a single row.
224 virtual typename SPxSolverBase<R>::VarStatus getBasisRowStatus(int) const = 0;
225
226 /// gets basis status for a single column.
227 virtual typename SPxSolverBase<R>::VarStatus getBasisColStatus(int) const = 0;
228
229 /// get optimal basis.
230 virtual void getBasis(typename SPxSolverBase<R>::VarStatus[],
231 typename SPxSolverBase<R>::VarStatus[], const int rowsSize = -1, const int colsSize = -1) const = 0;
232
233 /// get objective offset.
234 virtual R getObjoffset() const
235 {
236 return m_objoffset;
237 }
238
239 /// add objective offset.
240 virtual void addObjoffset(const R val)
241 {
242 m_objoffset += val;
243 }
244
245 /// set minimal reduction threshold to continue simplification
246 virtual void setMinReduction(const R minRed)
247 {
249 }
250
251 ///@}
252
253 //-------------------------------------
254 /**@name Consistency check */
255 ///@{
256 /// consistency check
257 virtual bool isConsistent() const
258 {
259 return true;
260 }
261 ///@}
262
267
268};
269
270/// Pretty-printing of simplifier status
271template <class R>
272std::ostream& operator<<(std::ostream& os, const typename SPxSimplifier<R>::Result& status);
273
274} // namespace soplex
275#endif // _SPXSIMPLIFIER_H_
Safe arrays of data objects.
Definition dataarray.h:75
Wrapper for several output streams. A verbosity level is used to decide which stream to use and wheth...
Definition spxout.h:73
LP simplification abstract base class.
void setOutstream(SPxOut &newOutstream)
virtual const VectorBase< R > & unsimplifiedPrimal()=0
returns a reference to the unsimplified primal solution.
virtual SPxSolverBase< R >::VarStatus getBasisColStatus(int) const =0
gets basis status for a single column.
int m_remNzos
number of removed nonzero coefficients
virtual void addObjoffset(const R val)
add objective offset.
int m_keptLRhs
number of kept left- and right-hand sides
Result
Result of the simplification.
@ INFEASIBLE
primal infeasibility was detected
@ UNBOUNDED
primal unboundedness was detected
@ OKAY
simplification could be done
@ DUAL_INFEASIBLE
dual infeasibility was detected
@ VANISHED
the problem was so much simplified that it vanished
virtual const VectorBase< R > & unsimplifiedSlacks()=0
returns a reference to the unsimplified slack values.
virtual SPxSolverBase< R >::VarStatus getBasisRowStatus(int) const =0
gets basis status for a single row.
virtual Result simplify(SPxLPBase< R > &lp, R eps, R feastol, R opttol, Real remainingTime, bool keepbounds=false, uint32_t seed=0)=0
simplify SPxLP lp with independent primal and dual feasibility tolerance.
R m_minReduction
minimal reduction (sum of removed rows/cols) to continue simplification
int m_remCols
number of removed columns
int m_remRows
number of removed rows
R m_objoffset
objective offset
SPxSimplifier & operator=(const SPxSimplifier &rhs)
assignment operator
SPxOut * spxout
message handler
virtual const char * getName() const
get name of simplifier.
virtual R timeUsed() const
int m_chgBnds
number of changed bounds
virtual void setMinReduction(const R minRed)
set minimal reduction threshold to continue simplification
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 const VectorBase< R > & unsimplifiedRedCost()=0
returns a reference to the unsimplified reduced costs.
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.
virtual R getObjoffset() const
get objective offset.
virtual ~SPxSimplifier()
destructor.
int m_keptBnds
number of kept bounds
virtual Result result() const =0
returns result status of the simplification
virtual const VectorBase< R > & unsimplifiedDual()=0
returns a reference to the unsimplified dual solution.
Timer * m_timeUsed
user time used for simplification
virtual bool isConsistent() const
consistency check
int m_chgLRhs
number of change right-hand sides
const char * m_name
name of the simplifier
virtual Result simplify(SPxLPBase< R > &lp, R eps, R delta, Real remainingTime)=0
simplify SPxLP lp with identical primal and dual feasibility tolerance.
SPxSimplifier(const char *p_name, Timer::TYPE ttype=Timer::USER_TIME)
constructor
SPxSimplifier(const SPxSimplifier &old)
copy constructor
virtual bool isUnsimplified() const
specifies whether an optimal solution has already been unsimplified.
virtual SPxSimplifier * clone() const =0
clone function for polymorphism
static Timer * createTimer(Timer::TYPE ttype)
create timers and allocate memory for them
Wrapper for the system time query methods.
Definition timer.h:86
TYPE
types of timers
Definition timer.h:109
virtual ~Timer()
Definition timer.h:133
virtual Real time() const =0
Everything should be within this namespace.
double Real
Definition spxdefines.h:266
void spx_free(T &p)
Release memory.
Definition spxalloc.h:121
Debugging, floating point type and parameter definitions.
Saving LPs in a form suitable for SoPlex.
main LP solver class
TimerFactory class.