1 | /* $Id: ClpPredictorCorrector.hpp 1665 2011-01-04 17:55:54Z forrest $ */ |
---|
2 | // Copyright (C) 2003, 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 | Authors |
---|
7 | |
---|
8 | John Forrest |
---|
9 | |
---|
10 | */ |
---|
11 | #ifndef ClpPredictorCorrector_H |
---|
12 | #define ClpPredictorCorrector_H |
---|
13 | |
---|
14 | #include "ClpInterior.hpp" |
---|
15 | |
---|
16 | /** This solves LPs using the predictor-corrector method due to Mehrotra. |
---|
17 | It also uses multiple centrality corrections as in Gondzio. |
---|
18 | |
---|
19 | See; |
---|
20 | S. Mehrotra, "On the implementation of a primal-dual interior point method", |
---|
21 | SIAM Journal on optimization, 2 (1992) |
---|
22 | J. Gondzio, "Multiple centraility corrections in a primal-dual method for linear programming", |
---|
23 | Computational Optimization and Applications",6 (1996) |
---|
24 | |
---|
25 | |
---|
26 | It is rather basic as Interior point is not my speciality |
---|
27 | |
---|
28 | It inherits from ClpInterior. It has no data of its own and |
---|
29 | is never created - only cast from a ClpInterior object at algorithm time. |
---|
30 | |
---|
31 | It can also solve QPs |
---|
32 | |
---|
33 | |
---|
34 | |
---|
35 | */ |
---|
36 | |
---|
37 | class ClpPredictorCorrector : public ClpInterior { |
---|
38 | |
---|
39 | public: |
---|
40 | |
---|
41 | /**@name Description of algorithm */ |
---|
42 | //@{ |
---|
43 | /** Primal Dual Predictor Corrector algorithm |
---|
44 | |
---|
45 | Method |
---|
46 | |
---|
47 | Big TODO |
---|
48 | */ |
---|
49 | |
---|
50 | int solve(); |
---|
51 | //@} |
---|
52 | |
---|
53 | /**@name Functions used in algorithm */ |
---|
54 | //@{ |
---|
55 | /// findStepLength. |
---|
56 | //phase - 0 predictor |
---|
57 | // 1 corrector |
---|
58 | // 2 primal dual |
---|
59 | CoinWorkDouble findStepLength( int phase); |
---|
60 | /// findDirectionVector. |
---|
61 | CoinWorkDouble findDirectionVector(const int phase); |
---|
62 | /// createSolution. Creates solution from scratch (- code if no memory) |
---|
63 | int createSolution(); |
---|
64 | /// complementarityGap. Computes gap |
---|
65 | //phase 0=as is , 1 = after predictor , 2 after corrector |
---|
66 | CoinWorkDouble complementarityGap(int & numberComplementarityPairs, int & numberComplementarityItems, |
---|
67 | const int phase); |
---|
68 | /// setupForSolve. |
---|
69 | //phase 0=affine , 1 = corrector , 2 = primal-dual |
---|
70 | void setupForSolve(const int phase); |
---|
71 | /** Does solve. region1 is for deltaX (columns+rows), region2 for deltaPi (rows) */ |
---|
72 | void solveSystem(CoinWorkDouble * region1, CoinWorkDouble * region2, |
---|
73 | const CoinWorkDouble * region1In, const CoinWorkDouble * region2In, |
---|
74 | const CoinWorkDouble * saveRegion1, const CoinWorkDouble * saveRegion2, |
---|
75 | bool gentleRefine); |
---|
76 | /// sees if looks plausible change in complementarity |
---|
77 | bool checkGoodMove(const bool doCorrector, CoinWorkDouble & bestNextGap, |
---|
78 | bool allowIncreasingGap); |
---|
79 | ///: checks for one step size |
---|
80 | bool checkGoodMove2(CoinWorkDouble move, CoinWorkDouble & bestNextGap, |
---|
81 | bool allowIncreasingGap); |
---|
82 | /// updateSolution. Updates solution at end of iteration |
---|
83 | //returns number fixed |
---|
84 | int updateSolution(CoinWorkDouble nextGap); |
---|
85 | /// Save info on products of affine deltaT*deltaW and deltaS*deltaZ |
---|
86 | CoinWorkDouble affineProduct(); |
---|
87 | ///See exactly what would happen given current deltas |
---|
88 | void debugMove(int phase, CoinWorkDouble primalStep, CoinWorkDouble dualStep); |
---|
89 | //@} |
---|
90 | |
---|
91 | }; |
---|
92 | #endif |
---|