[152] | 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 | |
---|
[225] | 13 | class ClpQuadraticInfo; |
---|
| 14 | class ClpQuadraticObjective; |
---|
| 15 | |
---|
[152] | 16 | #include "ClpSimplexPrimal.hpp" |
---|
| 17 | |
---|
[225] | 18 | /** This solves Quadratic LPs using the primal simplex method |
---|
[152] | 19 | |
---|
[166] | 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 |
---|
[152] | 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 | |
---|
[225] | 35 | a) Dantzig's algorithm |
---|
[152] | 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); |
---|
[225] | 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); |
---|
[166] | 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 |
---|
[225] | 82 | cleanupIteration - 0 no, 1 yes, 2 restoring one of x/s in basis |
---|
[166] | 83 | */ |
---|
| 84 | int primalRow(CoinIndexedVector * rowArray, |
---|
| 85 | CoinIndexedVector * rhsArray, |
---|
| 86 | CoinIndexedVector * spareArray, |
---|
| 87 | CoinIndexedVector * spareArray2, |
---|
[225] | 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); |
---|
[152] | 102 | //@} |
---|
| 103 | |
---|
| 104 | }; |
---|
[225] | 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 | }; |
---|
[152] | 240 | #endif |
---|
| 241 | |
---|