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