1 | /* $Id: ClpPredictorCorrector.hpp 2385 2019-01-06 19:43:06Z stefan $ */ |
---|
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 | /**@name Description of algorithm */ |
---|
41 | //@{ |
---|
42 | /** Primal Dual Predictor Corrector algorithm |
---|
43 | |
---|
44 | Method |
---|
45 | |
---|
46 | Big TODO |
---|
47 | */ |
---|
48 | |
---|
49 | int solve(); |
---|
50 | //@} |
---|
51 | |
---|
52 | /**@name Functions used in algorithm */ |
---|
53 | //@{ |
---|
54 | /// findStepLength. |
---|
55 | //phase - 0 predictor |
---|
56 | // 1 corrector |
---|
57 | // 2 primal dual |
---|
58 | CoinWorkDouble findStepLength(int phase); |
---|
59 | /// findDirectionVector. |
---|
60 | CoinWorkDouble findDirectionVector(const int phase); |
---|
61 | /// createSolution. Creates solution from scratch (- code if no memory) |
---|
62 | int createSolution(); |
---|
63 | /// complementarityGap. Computes gap |
---|
64 | //phase 0=as is , 1 = after predictor , 2 after corrector |
---|
65 | CoinWorkDouble complementarityGap(int &numberComplementarityPairs, int &numberComplementarityItems, |
---|
66 | const int phase); |
---|
67 | /// setupForSolve. |
---|
68 | //phase 0=affine , 1 = corrector , 2 = primal-dual |
---|
69 | void setupForSolve(const int phase); |
---|
70 | /** Does solve. region1 is for deltaX (columns+rows), region2 for deltaPi (rows) */ |
---|
71 | void solveSystem(CoinWorkDouble *region1, CoinWorkDouble *region2, |
---|
72 | const CoinWorkDouble *region1In, const CoinWorkDouble *region2In, |
---|
73 | const CoinWorkDouble *saveRegion1, const CoinWorkDouble *saveRegion2, |
---|
74 | bool gentleRefine); |
---|
75 | /// sees if looks plausible change in complementarity |
---|
76 | bool checkGoodMove(const bool doCorrector, CoinWorkDouble &bestNextGap, |
---|
77 | bool allowIncreasingGap); |
---|
78 | ///: checks for one step size |
---|
79 | bool checkGoodMove2(CoinWorkDouble move, CoinWorkDouble &bestNextGap, |
---|
80 | bool allowIncreasingGap); |
---|
81 | /// updateSolution. Updates solution at end of iteration |
---|
82 | //returns number fixed |
---|
83 | int updateSolution(CoinWorkDouble nextGap); |
---|
84 | /// Save info on products of affine deltaT*deltaW and deltaS*deltaZ |
---|
85 | CoinWorkDouble affineProduct(); |
---|
86 | ///See exactly what would happen given current deltas |
---|
87 | void debugMove(int phase, CoinWorkDouble primalStep, CoinWorkDouble dualStep); |
---|
88 | //@} |
---|
89 | }; |
---|
90 | #endif |
---|
91 | |
---|
92 | /* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2 |
---|
93 | */ |
---|