1 | // Copyright (C) 2002, International Business Machines |
---|
2 | // Corporation and others. All Rights Reserved. |
---|
3 | |
---|
4 | /* |
---|
5 | Authors |
---|
6 | |
---|
7 | John Forrest |
---|
8 | |
---|
9 | */ |
---|
10 | #ifndef ClpSimplexPrimal_H |
---|
11 | #define ClpSimplexPrimal_H |
---|
12 | |
---|
13 | #include "ClpSimplex.hpp" |
---|
14 | |
---|
15 | /** This solves LPs using the primal simplex method |
---|
16 | |
---|
17 | It inherits from ClpSimplex. It has no data of its own and |
---|
18 | is never created - only cast from a ClpSimplex object at algorithm time. |
---|
19 | |
---|
20 | */ |
---|
21 | |
---|
22 | class ClpSimplexPrimal : public ClpSimplex { |
---|
23 | |
---|
24 | public: |
---|
25 | |
---|
26 | /**@name Description of algorithm */ |
---|
27 | //@{ |
---|
28 | /** Primal algorithm |
---|
29 | |
---|
30 | Method |
---|
31 | |
---|
32 | It tries to be a single phase approach with a weight of 1.0 being |
---|
33 | given to getting optimal and a weight of infeasibilityCost_ being |
---|
34 | given to getting primal feasible. In this version I have tried to |
---|
35 | be clever in a stupid way. The idea of fake bounds in dual |
---|
36 | seems to work so the primal analogue would be that of getting |
---|
37 | bounds on reduced costs (by a presolve approach) and using |
---|
38 | these for being above or below feasible region. I decided to waste |
---|
39 | memory and keep these explicitly. This allows for non-linear |
---|
40 | costs! I have not tested non-linear costs but will be glad |
---|
41 | to do something if a reasonable example is provided. |
---|
42 | |
---|
43 | The code is designed to take advantage of sparsity so arrays are |
---|
44 | seldom zeroed out from scratch or gone over in their entirety. |
---|
45 | The only exception is a full scan to find incoming variable for |
---|
46 | Dantzig row choice. For steepest edge we keep an updated list |
---|
47 | of dual infeasibilities (actually squares). |
---|
48 | On easy problems we don't need full scan - just |
---|
49 | pick first reasonable. This method has not been coded. |
---|
50 | |
---|
51 | One problem is how to tackle degeneracy and accuracy. At present |
---|
52 | I am using the modification of costs which I put in OSL and which was |
---|
53 | extended by Gill et al. I am still not sure whether we will also |
---|
54 | need explicit perturbation. |
---|
55 | |
---|
56 | The flow of primal is three while loops as follows: |
---|
57 | |
---|
58 | while (not finished) { |
---|
59 | |
---|
60 | while (not clean solution) { |
---|
61 | |
---|
62 | Factorize and/or clean up solution by changing bounds so |
---|
63 | primal feasible. If looks finished check fake primal bounds. |
---|
64 | Repeat until status is iterating (-1) or finished (0,1,2) |
---|
65 | |
---|
66 | } |
---|
67 | |
---|
68 | while (status==-1) { |
---|
69 | |
---|
70 | Iterate until no pivot in or out or time to re-factorize. |
---|
71 | |
---|
72 | Flow is: |
---|
73 | |
---|
74 | choose pivot column (incoming variable). if none then |
---|
75 | we are primal feasible so looks as if done but we need to |
---|
76 | break and check bounds etc. |
---|
77 | |
---|
78 | Get pivot column in tableau |
---|
79 | |
---|
80 | Choose outgoing row. If we don't find one then we look |
---|
81 | primal unbounded so break and check bounds etc. (Also the |
---|
82 | pivot tolerance is larger after any iterations so that may be |
---|
83 | reason) |
---|
84 | |
---|
85 | If we do find outgoing row, we may have to adjust costs to |
---|
86 | keep going forwards (anti-degeneracy). Check pivot will be stable |
---|
87 | and if unstable throw away iteration and break to re-factorize. |
---|
88 | If minor error re-factorize after iteration. |
---|
89 | |
---|
90 | Update everything (this may involve changing bounds on |
---|
91 | variables to stay primal feasible. |
---|
92 | |
---|
93 | } |
---|
94 | |
---|
95 | } |
---|
96 | |
---|
97 | TODO's (or maybe not) |
---|
98 | |
---|
99 | At present we never check we are going forwards. I overdid that in |
---|
100 | OSL so will try and make a last resort. |
---|
101 | |
---|
102 | Needs partial scan pivot in option. |
---|
103 | |
---|
104 | May need other anti-degeneracy measures, especially if we try and use |
---|
105 | loose tolerances as a way to solve in fewer iterations. |
---|
106 | |
---|
107 | I like idea of dynamic scaling. This gives opportunity to decouple |
---|
108 | different implications of scaling for accuracy, iteration count and |
---|
109 | feasibility tolerance. |
---|
110 | |
---|
111 | */ |
---|
112 | |
---|
113 | int primal(int ifValuesPass=0); |
---|
114 | //@} |
---|
115 | |
---|
116 | /**@name For advanced users */ |
---|
117 | //@{ |
---|
118 | /// Do not change infeasibility cost and always say optimal |
---|
119 | void alwaysOptimal(bool onOff); |
---|
120 | bool alwaysOptimal() const; |
---|
121 | /** Normally outgoing variables can go out to slightly negative |
---|
122 | values (but within tolerance) - this is to help stability and |
---|
123 | and degeneracy. This can be switched off |
---|
124 | */ |
---|
125 | void exactOutgoing(bool onOff); |
---|
126 | bool exactOutgoing() const; |
---|
127 | //@} |
---|
128 | |
---|
129 | /**@name Functions used in primal */ |
---|
130 | //@{ |
---|
131 | /** This has the flow between re-factorizations |
---|
132 | |
---|
133 | Returns a code to say where decision to exit was made |
---|
134 | Problem status set to: |
---|
135 | |
---|
136 | -2 re-factorize |
---|
137 | -4 Looks optimal/infeasible |
---|
138 | -5 Looks unbounded |
---|
139 | +3 max iterations |
---|
140 | |
---|
141 | valuesOption has original value of valuesPass |
---|
142 | */ |
---|
143 | int whileIterating(int valuesOption); |
---|
144 | |
---|
145 | /** Do last half of an iteration. This is split out so people can |
---|
146 | force incoming variable. If solveType_ is 2 then this may |
---|
147 | re-factorize while normally it would exit to re-factorize. |
---|
148 | Return codes |
---|
149 | Reasons to come out (normal mode/user mode): |
---|
150 | -1 normal |
---|
151 | -2 factorize now - good iteration/ NA |
---|
152 | -3 slight inaccuracy - refactorize - iteration done/ same but factor done |
---|
153 | -4 inaccuracy - refactorize - no iteration/ NA |
---|
154 | -5 something flagged - go round again/ pivot not possible |
---|
155 | +2 looks unbounded |
---|
156 | +3 max iterations (iteration done) |
---|
157 | |
---|
158 | With solveType_ ==2 this should |
---|
159 | Pivot in a variable and choose an outgoing one. Assumes primal |
---|
160 | feasible - will not go through a bound. Returns step length in theta |
---|
161 | Returns ray in ray_ |
---|
162 | */ |
---|
163 | int pivotResult(int ifValuesPass=0); |
---|
164 | |
---|
165 | |
---|
166 | /** The primals are updated by the given array. |
---|
167 | Returns number of infeasibilities. |
---|
168 | After rowArray will have cost changes for use next iteration |
---|
169 | */ |
---|
170 | int updatePrimalsInPrimal(CoinIndexedVector * rowArray, |
---|
171 | double theta, |
---|
172 | double & objectiveChange); |
---|
173 | /** |
---|
174 | Row array has pivot column |
---|
175 | This chooses pivot row. |
---|
176 | Rhs array is used for distance to next bound (for speed) |
---|
177 | For speed, we may need to go to a bucket approach when many |
---|
178 | variables go through bounds |
---|
179 | On exit rhsArray will have changes in costs of basic variables |
---|
180 | If valuesPass non-zero then compute dj for direction |
---|
181 | */ |
---|
182 | void primalRow(CoinIndexedVector * rowArray, |
---|
183 | CoinIndexedVector * rhsArray, |
---|
184 | CoinIndexedVector * spareArray, |
---|
185 | CoinIndexedVector * spareArray2, |
---|
186 | int valuesPass); |
---|
187 | /** |
---|
188 | Chooses primal pivot column |
---|
189 | updateArray has cost updates (also use pivotRow_ from last iteration) |
---|
190 | Would be faster with separate region to scan |
---|
191 | and will have this (with square of infeasibility) when steepest |
---|
192 | For easy problems we can just choose one of the first columns we look at |
---|
193 | */ |
---|
194 | void primalColumn(CoinIndexedVector * updateArray, |
---|
195 | CoinIndexedVector * spareRow1, |
---|
196 | CoinIndexedVector * spareRow2, |
---|
197 | CoinIndexedVector * spareColumn1, |
---|
198 | CoinIndexedVector * spareColumn2); |
---|
199 | |
---|
200 | /** Checks if tentative optimal actually means unbounded in primal |
---|
201 | Returns -3 if not, 2 if is unbounded */ |
---|
202 | int checkUnbounded(CoinIndexedVector * ray,CoinIndexedVector * spare, |
---|
203 | double changeCost); |
---|
204 | /** Refactorizes if necessary |
---|
205 | Checks if finished. Updates status. |
---|
206 | lastCleaned refers to iteration at which some objective/feasibility |
---|
207 | cleaning too place. |
---|
208 | |
---|
209 | type - 0 initial so set up save arrays etc |
---|
210 | - 1 normal -if good update save |
---|
211 | - 2 restoring from saved |
---|
212 | */ |
---|
213 | void statusOfProblemInPrimal(int & lastCleaned, int type, |
---|
214 | ClpSimplexProgress * progress); |
---|
215 | /// Perturbs problem (method depends on perturbation()) |
---|
216 | void perturb(int type); |
---|
217 | /// Take off effect of perturbation and say whether to try dual |
---|
218 | bool unPerturb(); |
---|
219 | /// Unflag all variables and return number unflagged |
---|
220 | int unflag(); |
---|
221 | /** Get next superbasic -1 if none, |
---|
222 | Normal type is 1 |
---|
223 | If type is 3 then initializes sorted list |
---|
224 | if 2 uses list. |
---|
225 | */ |
---|
226 | int nextSuperBasic(int superBasicType,CoinIndexedVector * columnArray); |
---|
227 | |
---|
228 | /// Create primal ray |
---|
229 | void primalRay(CoinIndexedVector * rowArray); |
---|
230 | |
---|
231 | //@} |
---|
232 | }; |
---|
233 | #endif |
---|
234 | |
---|