1/* $Id: ClpPresolve.hpp 1753 2011-06-19 16:27:26Z stefan $ */
2// Copyright (C) 2002, International Business Machines
3// Corporation and others. All Rights Reserved.
4// This code is licensed under the terms of the Eclipse Public License (EPL).
5
6#ifndef ClpPresolve_H
7#define ClpPresolve_H
8#include "ClpSimplex.hpp"
9
10class CoinPresolveAction;
11#include "CoinPresolveMatrix.hpp"
12/** This is the Clp interface to CoinPresolve
13
14*/
15class ClpPresolve {
16public:
17 /**@name Main Constructor, destructor */
18 //@{
19 /// Default constructor
20 ClpPresolve();
21
22 /// Virtual destructor
23 virtual ~ClpPresolve();
24 //@}
25 /**@name presolve - presolves a model, transforming the model
26 * and saving information in the ClpPresolve object needed for postsolving.
27 * This underlying (protected) method is virtual; the idea is that in the future,
28 * one could override this method to customize how the various
29 * presolve techniques are applied.
30
31 This version of presolve returns a pointer to a new presolved
32 model. NULL if infeasible or unbounded.
33 This should be paired with postsolve
34 below. The advantage of going back to original model is that it
35 will be exactly as it was i.e. 0.0 will not become 1.0e-19.
36 If keepIntegers is true then bounds may be tightened in
37 original. Bounds will be moved by up to feasibilityTolerance
38 to try and stay feasible.
39 Names will be dropped in presolved model if asked
40 */
41 ClpSimplex * presolvedModel(ClpSimplex & si,
42 double feasibilityTolerance = 0.0,
43 bool keepIntegers = true,
44 int numberPasses = 5,
45 bool dropNames = false,
46 bool doRowObjective = false);
47#ifndef CLP_NO_STD
48 /** This version saves data in a file. The passed in model
49 is updated to be presolved model.
50 Returns non-zero if infeasible*/
51 int presolvedModelToFile(ClpSimplex &si, std::string fileName,
52 double feasibilityTolerance = 0.0,
53 bool keepIntegers = true,
54 int numberPasses = 5,
55 bool dropNames = false,
56 bool doRowObjective = false);
57#endif
58 /** Return pointer to presolved model,
59 Up to user to destroy */
60 ClpSimplex * model() const;
61 /// Return pointer to original model
62 ClpSimplex * originalModel() const;
63 /// Set pointer to original model
64 void setOriginalModel(ClpSimplex * model);
65
66 /// return pointer to original columns
67 const int * originalColumns() const;
68 /// return pointer to original rows
69 const int * originalRows() const;
70 /** "Magic" number. If this is non-zero then any elements with this value
71 may change and so presolve is very limited in what can be done
72 to the row and column. This is for non-linear problems.
73 */
74 inline void setNonLinearValue(double value) {
75 nonLinearValue_ = value;
76 }
77 inline double nonLinearValue() const {
78 return nonLinearValue_;
79 }
80 /// Whether we want to do dual part of presolve
81 inline bool doDual() const {
82 return (presolveActions_ & 1) == 0;
83 }
84 inline void setDoDual(bool doDual) {
85 if (doDual) presolveActions_ &= ~1;
86 else presolveActions_ |= 1;
87 }
88 /// Whether we want to do singleton part of presolve
89 inline bool doSingleton() const {
90 return (presolveActions_ & 2) == 0;
91 }
92 inline void setDoSingleton(bool doSingleton) {
93 if (doSingleton) presolveActions_ &= ~2;
94 else presolveActions_ |= 2;
95 }
96 /// Whether we want to do doubleton part of presolve
97 inline bool doDoubleton() const {
98 return (presolveActions_ & 4) == 0;
99 }
100 inline void setDoDoubleton(bool doDoubleton) {
101 if (doDoubleton) presolveActions_ &= ~4;
102 else presolveActions_ |= 4;
103 }
104 /// Whether we want to do tripleton part of presolve
105 inline bool doTripleton() const {
106 return (presolveActions_ & 8) == 0;
107 }
108 inline void setDoTripleton(bool doTripleton) {
109 if (doTripleton) presolveActions_ &= ~8;
110 else presolveActions_ |= 8;
111 }
112 /// Whether we want to do tighten part of presolve
113 inline bool doTighten() const {
114 return (presolveActions_ & 16) == 0;
115 }
116 inline void setDoTighten(bool doTighten) {
117 if (doTighten) presolveActions_ &= ~16;
118 else presolveActions_ |= 16;
119 }
120 /// Whether we want to do forcing part of presolve
121 inline bool doForcing() const {
122 return (presolveActions_ & 32) == 0;
123 }
124 inline void setDoForcing(bool doForcing) {
125 if (doForcing) presolveActions_ &= ~32;
126 else presolveActions_ |= 32;
127 }
128 /// Whether we want to do impliedfree part of presolve
129 inline bool doImpliedFree() const {
130 return (presolveActions_ & 64) == 0;
131 }
132 inline void setDoImpliedFree(bool doImpliedfree) {
133 if (doImpliedfree) presolveActions_ &= ~64;
134 else presolveActions_ |= 64;
135 }
136 /// Whether we want to do dupcol part of presolve
137 inline bool doDupcol() const {
138 return (presolveActions_ & 128) == 0;
139 }
140 inline void setDoDupcol(bool doDupcol) {
141 if (doDupcol) presolveActions_ &= ~128;
142 else presolveActions_ |= 128;
143 }
144 /// Whether we want to do duprow part of presolve
145 inline bool doDuprow() const {
146 return (presolveActions_ & 256) == 0;
147 }
148 inline void setDoDuprow(bool doDuprow) {
149 if (doDuprow) presolveActions_ &= ~256;
150 else presolveActions_ |= 256;
151 }
152 /// Whether we want to do singleton column part of presolve
153 inline bool doSingletonColumn() const {
154 return (presolveActions_ & 512) == 0;
155 }
156 inline void setDoSingletonColumn(bool doSingleton) {
157 if (doSingleton) presolveActions_ &= ~512;
158 else presolveActions_ |= 512;
159 }
160 /// Whether we want to do gubrow part of presolve
161 inline bool doGubrow() const {
162 return (presolveActions_ & 1024) == 0;
163 }
164 inline void setDoGubrow(bool doGubrow) {
165 if (doGubrow) presolveActions_ &= ~1024;
166 else presolveActions_ |= 1024;
167 }
168 /// Set whole group
169 inline int presolveActions() const {
170 return presolveActions_ & 0xffff;
171 }
172 inline void setPresolveActions(int action) {
173 presolveActions_ = (presolveActions_ & 0xffff0000) | (action & 0xffff);
174 }
175 /// Substitution level
176 inline void setSubstitution(int value) {
177 substitution_ = value;
178 }
179 /// Asks for statistics
180 inline void statistics() {
181 presolveActions_ |= 0x80000000;
182 }
183 /// Return presolve status (0,1,2)
184 int presolveStatus() const;
185
186 /**@name postsolve - postsolve the problem. If the problem
187 has not been solved to optimality, there are no guarantees.
188 If you are using an algorithm like simplex that has a concept
189 of "basic" rows/cols, then set updateStatus
190
191 Note that if you modified the original problem after presolving,
192 then you must ``undo'' these modifications before calling postsolve.
193 This version updates original*/
194 virtual void postsolve(bool updateStatus = true);
195
196 /// Gets rid of presolve actions (e.g.when infeasible)
197 void destroyPresolve();
198
199 /**@name private or protected data */
200private:
201 /// Original model - must not be destroyed before postsolve
202 ClpSimplex * originalModel_;
203
204 /// ClpPresolved model - up to user to destroy by deleteClpPresolvedModel
205 ClpSimplex * presolvedModel_;
206 /** "Magic" number. If this is non-zero then any elements with this value
207 may change and so presolve is very limited in what can be done
208 to the row and column. This is for non-linear problems.
209 One could also allow for cases where sign of coefficient is known.
210 */
211 double nonLinearValue_;
212 /// Original column numbers
213 int * originalColumn_;
214 /// Original row numbers
215 int * originalRow_;
216 /// Row objective
217 double * rowObjective_;
218 /// The list of transformations applied.
219 const CoinPresolveAction *paction_;
220
221 /// The postsolved problem will expand back to its former size
222 /// as postsolve transformations are applied.
223 /// It is efficient to allocate data structures for the final size
224 /// of the problem rather than expand them as needed.
225 /// These fields give the size of the original problem.
226 int ncols_;
227 int nrows_;
228 CoinBigIndex nelems_;
229 /// Number of major passes
230 int numberPasses_;
231 /// Substitution level
232 int substitution_;
233#ifndef CLP_NO_STD
234 /// Name of saved model file
235 std::string saveFile_;
236#endif
237 /** Whether we want to skip dual part of presolve etc.
238 512 bit allows duplicate column processing on integer columns
239 and dual stuff on integers
240 */
241 int presolveActions_;
242protected:
243 /// If you want to apply the individual presolve routines differently,
244 /// or perhaps add your own to the mix,
245 /// define a derived class and override this method
246 virtual const CoinPresolveAction *presolve(CoinPresolveMatrix *prob);
247
248 /// Postsolving is pretty generic; just apply the transformations
249 /// in reverse order.
250 /// You will probably only be interested in overriding this method
251 /// if you want to add code to test for consistency
252 /// while debugging new presolve techniques.
253 virtual void postsolve(CoinPostsolveMatrix &prob);
254 /** This is main part of Presolve */
255 virtual ClpSimplex * gutsOfPresolvedModel(ClpSimplex * originalModel,
256 double feasibilityTolerance,
257 bool keepIntegers,
258 int numberPasses,
259 bool dropNames,
260 bool doRowObjective);
261};
262#endif
263