1 | // Copyright (C) 2003, International Business Machines |
---|
2 | // Corporation and others. All Rights Reserved. |
---|
3 | |
---|
4 | /* |
---|
5 | Authors |
---|
6 | |
---|
7 | John Forrest |
---|
8 | |
---|
9 | */ |
---|
10 | #ifndef ClpSimplexPrimalQuadratic_H |
---|
11 | #define ClpSimplexPrimalQuadratic_H |
---|
12 | |
---|
13 | class ClpQuadraticInfo; |
---|
14 | class ClpQuadraticObjective; |
---|
15 | |
---|
16 | #include "ClpSimplexPrimal.hpp" |
---|
17 | |
---|
18 | /** This solves Quadratic LPs using the primal simplex method |
---|
19 | |
---|
20 | It inherits from ClpSimplexPrimal. It has no data of its own and |
---|
21 | is never created - only cast from a ClpSimplexPrimal object at algorithm time. |
---|
22 | If needed create new class and pass around |
---|
23 | |
---|
24 | */ |
---|
25 | |
---|
26 | class ClpSimplexPrimalQuadratic : public ClpSimplexPrimal { |
---|
27 | |
---|
28 | public: |
---|
29 | |
---|
30 | /**@name Description of algorithm */ |
---|
31 | //@{ |
---|
32 | /** Primal algorithms for quadratic |
---|
33 | At present we have two algorithms: |
---|
34 | |
---|
35 | a) Dantzig's algorithm |
---|
36 | b) Using a semi-trust region approach as for pooling problem |
---|
37 | This is in because I have it lying around |
---|
38 | |
---|
39 | */ |
---|
40 | /// A sequential LP method |
---|
41 | int primalSLP(int numberPasses, double deltaTolerance); |
---|
42 | /** Dantzig's method (actually a mixture with Jensen and King) |
---|
43 | phase - 0 normal, 1 getting complementary solution, |
---|
44 | 2 getting basic solution. |
---|
45 | Returns 0 if okay, 1 if LP infeasible. |
---|
46 | */ |
---|
47 | int primalQuadratic(int phase=2); |
---|
48 | /** This is done after first pass |
---|
49 | phase - 0 normal, 1 getting complementary solution, |
---|
50 | 2 getting basic solution. */ |
---|
51 | int primalQuadratic2 (ClpQuadraticInfo * info, |
---|
52 | int phase=2); |
---|
53 | /** This creates the large version of QP and |
---|
54 | fills in quadratic information. |
---|
55 | Returns NULL if no quadratic information |
---|
56 | */ |
---|
57 | ClpSimplexPrimalQuadratic * makeQuadratic(ClpQuadraticInfo & info); |
---|
58 | |
---|
59 | /// This moves solution back |
---|
60 | int endQuadratic(ClpSimplexPrimalQuadratic * quadraticModel, |
---|
61 | ClpQuadraticInfo & info); |
---|
62 | /// Checks complementarity and computes infeasibilities |
---|
63 | int checkComplementarity (ClpQuadraticInfo * info, |
---|
64 | CoinIndexedVector * array1, CoinIndexedVector * array2); |
---|
65 | /// Fills in reduced costs |
---|
66 | void createDjs (ClpQuadraticInfo * info, |
---|
67 | CoinIndexedVector * array1, CoinIndexedVector * array2); |
---|
68 | /** Main part. |
---|
69 | phase - 0 normal, 1 getting complementary solution, |
---|
70 | 2 getting basic solution. */ |
---|
71 | int whileIterating (ClpQuadraticInfo * info); |
---|
72 | /** |
---|
73 | Row array has pivot column |
---|
74 | This chooses pivot row. |
---|
75 | Rhs array is used for distance to next bound (for speed) |
---|
76 | For speed, we may need to go to a bucket approach when many |
---|
77 | variables go through bounds |
---|
78 | On exit rhsArray will have changes in costs of basic variables |
---|
79 | Initially no go thru |
---|
80 | Returns 0 - can do normal iteration |
---|
81 | 1 - losing complementarity |
---|
82 | cleanupIteration - 0 no, 1 yes, 2 restoring one of x/s in basis |
---|
83 | */ |
---|
84 | int primalRow(CoinIndexedVector * rowArray, |
---|
85 | CoinIndexedVector * rhsArray, |
---|
86 | CoinIndexedVector * spareArray, |
---|
87 | CoinIndexedVector * spareArray2, |
---|
88 | ClpQuadraticInfo * info, |
---|
89 | int cleanupIteration); |
---|
90 | /** Refactorizes if necessary |
---|
91 | Checks if finished. Updates status. |
---|
92 | lastCleaned refers to iteration at which some objective/feasibility |
---|
93 | cleaning too place. |
---|
94 | |
---|
95 | type - 0 initial so set up save arrays etc |
---|
96 | - 1 normal -if good update save |
---|
97 | - 2 restoring from saved |
---|
98 | */ |
---|
99 | void statusOfProblemInPrimal(int & lastCleaned, int type, |
---|
100 | ClpSimplexProgress * progress, |
---|
101 | ClpQuadraticInfo * info); |
---|
102 | //@} |
---|
103 | |
---|
104 | }; |
---|
105 | |
---|
106 | /** Trivial class to keep quadratic iterating info around |
---|
107 | |
---|
108 | */ |
---|
109 | |
---|
110 | class ClpQuadraticInfo { |
---|
111 | |
---|
112 | public: |
---|
113 | |
---|
114 | public: |
---|
115 | |
---|
116 | /**@name Constructors, destructor */ |
---|
117 | //@{ |
---|
118 | /// Default constructor. |
---|
119 | ClpQuadraticInfo(); |
---|
120 | /** Constructor from original model |
---|
121 | */ |
---|
122 | ClpQuadraticInfo(const ClpSimplex * model); |
---|
123 | /// Destructor |
---|
124 | ~ClpQuadraticInfo(); |
---|
125 | // Copy |
---|
126 | ClpQuadraticInfo(const ClpQuadraticInfo&); |
---|
127 | // Assignment |
---|
128 | ClpQuadraticInfo& operator=(const ClpQuadraticInfo&); |
---|
129 | //@} |
---|
130 | |
---|
131 | |
---|
132 | /**@name Gets and sets */ |
---|
133 | //@{ |
---|
134 | /// Number of Original columns |
---|
135 | inline int numberXColumns() const |
---|
136 | {return numberXColumns_;}; |
---|
137 | /// Number of Quadratic columns |
---|
138 | inline int numberQuadraticColumns() const |
---|
139 | {return numberQuadraticColumns_;}; |
---|
140 | /// Number of Original rows |
---|
141 | inline int numberXRows() const |
---|
142 | {return numberXRows_;}; |
---|
143 | /// Number of Quadratic rows |
---|
144 | inline int numberQuadraticRows() const |
---|
145 | {return numberQuadraticRows_;}; |
---|
146 | /// Sequence number incoming |
---|
147 | inline int sequenceIn() const |
---|
148 | {return currentSequenceIn_;}; |
---|
149 | inline void setSequenceIn(int sequence) |
---|
150 | {currentSequenceIn_=sequence;}; |
---|
151 | /// Sequence number of binding Sj |
---|
152 | inline int crucialSj() const |
---|
153 | {return crucialSj_;}; |
---|
154 | inline void setCrucialSj(int sequence) |
---|
155 | {crucialSj_=sequence;}; |
---|
156 | /// Current phase |
---|
157 | inline int currentPhase() const |
---|
158 | {return currentPhase_;}; |
---|
159 | inline void setCurrentPhase(int phase) |
---|
160 | {currentPhase_=phase;}; |
---|
161 | /// Current saved solution |
---|
162 | inline const double * currentSolution() const |
---|
163 | {return currentSolution_;}; |
---|
164 | void setCurrentSolution(const double * solution); |
---|
165 | /// Returns pointer to original objective |
---|
166 | inline ClpQuadraticObjective * originalObjective() const |
---|
167 | { return originalObjective_;}; |
---|
168 | inline void setOriginalObjective( ClpQuadraticObjective * obj) |
---|
169 | { originalObjective_ = obj;}; |
---|
170 | /// Quadratic objective |
---|
171 | CoinPackedMatrix * quadraticObjective() const; |
---|
172 | /// Linear objective |
---|
173 | double * linearObjective() const; |
---|
174 | /// Save current In and Sj status |
---|
175 | void saveStatus(); |
---|
176 | /// Restore previous |
---|
177 | void restoreStatus(); |
---|
178 | ///Dj weights |
---|
179 | inline double * djWeight() const |
---|
180 | { return djWeight_;}; |
---|
181 | /// create gradient |
---|
182 | void createGradient(ClpSimplex * model); |
---|
183 | /// Current gradient |
---|
184 | inline double * gradient() const |
---|
185 | { return gradient_;}; |
---|
186 | /// Infeas cost |
---|
187 | inline double infeasCost() const |
---|
188 | { return infeasCost_;}; |
---|
189 | inline void setInfeasCost(double value) |
---|
190 | { infeasCost_ = value;}; |
---|
191 | /// Backward pointer to basis (inverse of pivotVariable_) |
---|
192 | inline int * basicRow() const |
---|
193 | { return basicRow_;}; |
---|
194 | /// Set if Sj variable is implied |
---|
195 | inline int * impliedSj() const |
---|
196 | { return impliedSj_;}; |
---|
197 | //@} |
---|
198 | |
---|
199 | private: |
---|
200 | /**@name Data members */ |
---|
201 | //@{ |
---|
202 | /// Objective |
---|
203 | ClpQuadraticObjective * originalObjective_; |
---|
204 | /// Backward pointer to basis (inverse of pivotVariable_) |
---|
205 | int * basicRow_; |
---|
206 | /// Set if Sj variable is implied |
---|
207 | int * impliedSj_; |
---|
208 | /// Current sequenceIn |
---|
209 | int currentSequenceIn_; |
---|
210 | /// Crucial Sj |
---|
211 | int crucialSj_; |
---|
212 | /// Valid sequenceIn (for valid factorization) |
---|
213 | int validSequenceIn_; |
---|
214 | /// Valid crucial Sj |
---|
215 | int validCrucialSj_; |
---|
216 | /// Current phase |
---|
217 | int currentPhase_; |
---|
218 | /// Current saved solution |
---|
219 | double * currentSolution_; |
---|
220 | /// Valid phase |
---|
221 | int validPhase_; |
---|
222 | /// Valid saved solution |
---|
223 | double * validSolution_; |
---|
224 | /// Dj weights to stop looping |
---|
225 | double * djWeight_; |
---|
226 | /// Current gradient |
---|
227 | double * gradient_; |
---|
228 | /// Number of original rows |
---|
229 | int numberXRows_; |
---|
230 | /// Number of original columns |
---|
231 | int numberXColumns_; |
---|
232 | /// Number of quadratic columns |
---|
233 | int numberQuadraticColumns_; |
---|
234 | /// Number of quadratic rows |
---|
235 | int numberQuadraticRows_; |
---|
236 | /// Infeasibility cost |
---|
237 | double infeasCost_; |
---|
238 | //@} |
---|
239 | }; |
---|
240 | #endif |
---|
241 | |
---|