1// Copyright (C) 2003, International Business Machines
2// Corporation and others. All Rights Reserved.
3// This code is licensed under the terms of the Eclipse Public License (EPL).
4
5#ifndef OsiPresolve_H
6#define OsiPresolve_H
7#include "OsiSolverInterface.hpp"
8
9class CoinPresolveAction;
10#include "CoinPresolveMatrix.hpp"
11
12
13/*! \class OsiPresolve
14 \brief OSI interface to COIN problem simplification capabilities
15
16 COIN provides a number of classes which implement problem simplification
17 algorithms (CoinPresolveAction, CoinPrePostsolveMatrix, and derived
18 classes). The model of operation is as follows:
19 <ul>
20 <li>
21 Create a copy of the original problem.
22 </li>
23 <li>
24 Subject the copy to a series of transformations (the <i>presolve</i>
25 methods) to produce a presolved model. Each transformation is also
26 expected to provide a method to reverse the transformation (the
27 <i>postsolve</i> method). The postsolve methods are collected in a
28 linked list; the postsolve method for the final presolve transformation
29 is at the head of the list.
30 </li>
31 <li>
32 Hand the presolved problem to the solver for optimization.
33 </li>
34 <li>
35 Apply the collected postsolve methods to the presolved problem
36 and solution, restating the solution in terms of the original problem.
37 </li>
38 </ul>
39
40 The COIN presolve algorithms are unaware of OSI. The OsiPresolve class takes
41 care of the interface. Given an OsiSolverInterface \c origModel, it will take
42 care of creating a clone properly loaded with the presolved problem and ready
43 for optimization. After optimization, it will apply postsolve
44 transformations and load the result back into \c origModel.
45
46 Assuming a problem has been loaded into an
47 \c OsiSolverInterface \c origModel, a bare-bones application looks like this:
48 \code
49 OsiPresolve pinfo ;
50 OsiSolverInterface *presolvedModel ;
51 // Return an OsiSolverInterface loaded with the presolved problem.
52 presolvedModel = pinfo.presolvedModel(*origModel,1.0e-8,false,numberPasses) ;
53 presolvedModel->initialSolve() ;
54 // Restate the solution and load it back into origModel.
55 pinfo.postsolve(true) ;
56 delete presolvedModel ;
57 \endcode
58*/
59
60
61
62class OsiPresolve {
63public:
64 /// Default constructor (empty object)
65 OsiPresolve();
66
67 /// Virtual destructor
68 virtual ~OsiPresolve();
69
70 /*! \brief Create a new OsiSolverInterface loaded with the presolved problem.
71
72 This method implements the first two steps described in the class
73 documentation. It clones \c origModel and applies presolve
74 transformations, storing the resulting list of postsolve
75 transformations. It returns a pointer to a new OsiSolverInterface loaded
76 with the presolved problem, or NULL if the problem is infeasible or
77 unbounded. If \c keepIntegers is true then bounds may be tightened in
78 the original. Bounds will be moved by up to \c feasibilityTolerance to
79 try and stay feasible. When \c doStatus is true, the current solution will
80 be transformed to match the presolved model.
81
82 This should be paired with postsolve(). It is up to the client to
83 destroy the returned OsiSolverInterface, <i>after</i> calling postsolve().
84
85 This method is virtual. Override this method if you need to customize
86 the steps of creating a model to apply presolve transformations.
87
88 In some sense, a wrapper for presolve(CoinPresolveMatrix*).
89 */
90 virtual OsiSolverInterface *presolvedModel(OsiSolverInterface & origModel,
91 double feasibilityTolerance=0.0,
92 bool keepIntegers=true,
93 int numberPasses=5,
94 const char * prohibited=nullptr,
95 bool doStatus=true,
96 const char * rowProhibited=nullptr);
97
98 /*! \brief Restate the solution to the presolved problem in terms of the
99 original problem and load it into the original model.
100
101 postsolve() restates the solution in terms of the original problem and
102 updates the original OsiSolverInterface supplied to presolvedModel(). If
103 the problem has not been solved to optimality, there are no guarantees.
104 If you are using an algorithm like simplex that has a concept of a basic
105 solution, then set updateStatus
106
107 The advantage of going back to the original problem is that it
108 will be exactly as it was, <i>i.e.</i>, 0.0 will not become 1.0e-19.
109
110 Note that if you modified the original problem after presolving, then you
111 must ``undo'' these modifications before calling postsolve().
112
113 In some sense, a wrapper for postsolve(CoinPostsolveMatrix&).
114 */
115 virtual void postsolve(bool updateStatus=true);
116
117 /*! \brief Return a pointer to the presolved model. */
118 OsiSolverInterface * model() const;
119
120 /// Return a pointer to the original model
121 OsiSolverInterface * originalModel() const;
122
123 /// Set the pointer to the original model
124 void setOriginalModel(OsiSolverInterface *model);
125
126 /// Return a pointer to the original columns
127 const int * originalColumns() const;
128
129 /// Return a pointer to the original rows
130 const int * originalRows() const;
131
132 /// Return number of rows in original model
133 inline int getNumRows() const
134 { return nrows_;}
135
136 /// Return number of columns in original model
137 inline int getNumCols() const
138 { return ncols_;}
139
140 /** "Magic" number. If this is non-zero then any elements with this value
141 may change and so presolve is very limited in what can be done
142 to the row and column. This is for non-linear problems.
143 */
144 inline void setNonLinearValue(double value)
145 { nonLinearValue_ = value;}
146 inline double nonLinearValue() const
147 { return nonLinearValue_;}
148 /** Whether we want to skip dual part of presolve etc.
149 1 bit allows duplicate column processing on integer columns
150 and dual stuff on integers
151 2 bit set switches off actions which can change +1 to something else
152 4 bit set transfers costs to integer variables
153 8 bit set stops x+y+z=1 transform
154 16 bit set allows doing presolve things which don't easily unroll
155 32 bit set allows dubious gub element reduction
156 */
157 inline void setPresolveActions(int action)
158 { presolveActions_ = (presolveActions_&0xffff0000)|(action&0xffff);}
159
160private:
161 /*! Original model (solver interface loaded with the original problem).
162
163 Must not be destroyed until after postsolve().
164 */
165 OsiSolverInterface * originalModel_;
166
167 /*! Presolved model (solver interface loaded with the presolved problem)
168
169 Must be destroyed by the client (using delete) after postsolve().
170 */
171 OsiSolverInterface * presolvedModel_;
172
173 /*! "Magic" number. If this is non-zero then any elements with this value
174 may change and so presolve is very limited in what can be done
175 to the row and column. This is for non-linear problems.
176 One could also allow for cases where sign of coefficient is known.
177 */
178 double nonLinearValue_;
179
180 /// Original column numbers
181 int * originalColumn_;
182
183 /// Original row numbers
184 int * originalRow_;
185
186 /// The list of transformations applied.
187 const CoinPresolveAction *paction_;
188
189 /*! \brief Number of columns in original model.
190
191 The problem will expand back to its former size as postsolve
192 transformations are applied. It is efficient to allocate data structures
193 for the final size of the problem rather than expand them as needed.
194 */
195 int ncols_;
196
197 /*! \brief Number of rows in original model. */
198 int nrows_;
199
200 /*! \brief Number of nonzero matrix coefficients in the original model. */
201 CoinBigIndex nelems_;
202
203 /** Whether we want to skip dual part of presolve etc.
204 1 bit allows duplicate column processing on integer columns
205 and dual stuff on integers
206 4 transfers costs to integer variables
207 */
208 int presolveActions_;
209 /// Number of major passes
210 int numberPasses_;
211
212protected:
213 /*! \brief Apply presolve transformations to the problem.
214
215 Handles the core activity of applying presolve transformations.
216
217 If you want to apply the individual presolve routines differently, or
218 perhaps add your own to the mix, define a derived class and override
219 this method
220 */
221 virtual const CoinPresolveAction *presolve(CoinPresolveMatrix *prob);
222
223 /*! \brief Reverse presolve transformations to recover the solution
224 to the original problem.
225
226 Handles the core activity of applying postsolve transformations.
227
228 Postsolving is pretty generic; just apply the transformations in reverse
229 order. You will probably only be interested in overriding this method if
230 you want to add code to test for consistency while debugging new presolve
231 techniques.
232 */
233 virtual void postsolve(CoinPostsolveMatrix &prob);
234
235 /*! \brief Destroys queued postsolve actions.
236
237 <i>E.g.</i>, when presolve() determines the problem is infeasible, so that
238 it will not be necessary to actually solve the presolved problem and
239 convert the result back to the original problem.
240 */
241 void gutsOfDestroy();
242};
243#endif
244