1 | // Copyright (C) 2002, International Business Machines |
---|
2 | // Corporation and others. All Rights Reserved. |
---|
3 | #ifndef Idiot_H |
---|
4 | #define Idiot_H |
---|
5 | #ifdef CLP_IDIOT |
---|
6 | #include "ClpSimplex.hpp" |
---|
7 | #define OsiSolverInterface ClpSimplex |
---|
8 | #else |
---|
9 | #include "OsiSolverInterface.hpp" |
---|
10 | typedef int CoinBigIndex; |
---|
11 | #endif |
---|
12 | class CoinMessageHandler; |
---|
13 | class CoinMessages; |
---|
14 | // for use internally |
---|
15 | typedef struct { |
---|
16 | double infeas; |
---|
17 | double objval; |
---|
18 | double dropThis; |
---|
19 | double weighted; |
---|
20 | double sumSquared; |
---|
21 | double djAtBeginning; |
---|
22 | double djAtEnd; |
---|
23 | int iteration; |
---|
24 | } IdiotResult; |
---|
25 | /** This class implements a very silly algorithm. It has no merit |
---|
26 | apart from the fact that it gets an approximate solution to |
---|
27 | some classes of problems. Better if vaguely homogeneous. |
---|
28 | It works on problems where volume algorithm works and often |
---|
29 | gets a better primal solution but it has no dual solution. |
---|
30 | |
---|
31 | It can also be used as a "crash" to get a problem started. This |
---|
32 | is probably its most useful function. |
---|
33 | |
---|
34 | It is based on the idea that algorithms with terrible convergence |
---|
35 | properties may be okay at first. Throw in some random dubious tricks |
---|
36 | and the resulting code may be worth keeping as long as you don't |
---|
37 | look at it. |
---|
38 | |
---|
39 | */ |
---|
40 | |
---|
41 | class Idiot { |
---|
42 | |
---|
43 | public: |
---|
44 | |
---|
45 | /**@name Constructors and destructor |
---|
46 | Just a pointer to model is kept |
---|
47 | */ |
---|
48 | //@{ |
---|
49 | /// Default constructor |
---|
50 | Idiot ( ); |
---|
51 | /// Constructor with model |
---|
52 | Idiot ( OsiSolverInterface & model ); |
---|
53 | |
---|
54 | /// Copy constructor. |
---|
55 | Idiot(const Idiot &); |
---|
56 | /// Assignment operator. This copies the data |
---|
57 | Idiot & operator=(const Idiot & rhs); |
---|
58 | /// Destructor |
---|
59 | ~Idiot ( ); |
---|
60 | //@} |
---|
61 | |
---|
62 | |
---|
63 | /**@name Algorithmic calls |
---|
64 | */ |
---|
65 | //@{ |
---|
66 | /// Get an approximate solution with the idiot code |
---|
67 | void solve(); |
---|
68 | /// Lightweight "crash" |
---|
69 | void crash(int numberPass,CoinMessageHandler * handler ,const CoinMessages * messages); |
---|
70 | /** Use simplex to get an optimal solution |
---|
71 | mode is how many steps the simplex crossover should take to |
---|
72 | arrive to an extreme point: |
---|
73 | 0 - chosen,all ever used, all |
---|
74 | 1 - chosen, all |
---|
75 | 2 - all |
---|
76 | 3 - do not do anything - maybe basis |
---|
77 | + 16 do presolves |
---|
78 | */ |
---|
79 | void crossOver(int mode); |
---|
80 | //@} |
---|
81 | |
---|
82 | |
---|
83 | /**@name Gets and sets of most useful data |
---|
84 | */ |
---|
85 | //@{ |
---|
86 | /** Starting weight - small emphasizes feasibility, |
---|
87 | default 1.0e-4 */ |
---|
88 | inline double getStartingWeight() const |
---|
89 | { return mu_;}; |
---|
90 | inline void setStartingWeight(double value) |
---|
91 | { mu_ = value;}; |
---|
92 | /** Weight factor - weight multiplied by this when changes, |
---|
93 | default 0.333 */ |
---|
94 | inline double getWeightFactor() const |
---|
95 | { return muFactor_;}; |
---|
96 | inline void setWeightFactor(double value) |
---|
97 | { muFactor_ = value;}; |
---|
98 | /** Feasibility tolerance - problem essentially feasible if |
---|
99 | individual infeasibilities less than this. |
---|
100 | default 0.1 */ |
---|
101 | inline double getFeasibilityTolerance() const |
---|
102 | { return smallInfeas_;}; |
---|
103 | inline void setFeasibilityTolerance(double value) |
---|
104 | { smallInfeas_ = value;}; |
---|
105 | /** Reasonably feasible. Dubious method concentrates more on |
---|
106 | objective when sum of infeasibilities less than this. |
---|
107 | Very dubious default value of (Number of rows)/20 */ |
---|
108 | inline double getReasonablyFeasible() const |
---|
109 | { return reasonableInfeas_;}; |
---|
110 | inline void setReasonablyFeasible(double value) |
---|
111 | { reasonableInfeas_ = value;}; |
---|
112 | /** Exit infeasibility - exit if sum of infeasibilities less than this. |
---|
113 | Default -1.0 (i.e. switched off) */ |
---|
114 | inline double getExitInfeasibility() const |
---|
115 | { return exitFeasibility_;}; |
---|
116 | inline void setExitInfeasibility(double value) |
---|
117 | { exitFeasibility_ = value;}; |
---|
118 | /** Major iterations. stop after this number. |
---|
119 | Default 30. Use 2-5 for "crash" 50-100 for serious crunching */ |
---|
120 | inline int getMajorIterations() const |
---|
121 | { return majorIterations_;}; |
---|
122 | inline void setMajorIterations(int value) |
---|
123 | { majorIterations_ = value;}; |
---|
124 | /** Minor iterations. Do this number of tiny steps before |
---|
125 | deciding whether to change weights etc. |
---|
126 | Default - dubious sqrt(Number of Rows). |
---|
127 | Good numbers 105 to 405 say (5 is dubious method of making sure |
---|
128 | idiot is not trying to be clever which it may do every 10 minor |
---|
129 | iterations) */ |
---|
130 | inline int getMinorIterations() const |
---|
131 | { return maxIts2_;}; |
---|
132 | inline void setMinorIterations(int value) |
---|
133 | { maxIts2_ = value;}; |
---|
134 | /** Reduce weight after this many major iterations. It may |
---|
135 | get reduced before this but this is a maximum. |
---|
136 | Default 3. 3-10 plausible. */ |
---|
137 | inline int getReduceIterations() const |
---|
138 | { return maxBigIts_;}; |
---|
139 | inline void setReduceIterations(int value) |
---|
140 | { maxBigIts_ = value;}; |
---|
141 | /// Amount of information - default of 1 should be okay |
---|
142 | inline int getLogLevel() const |
---|
143 | { return logLevel_;}; |
---|
144 | inline void setLogLevel(int value) |
---|
145 | { logLevel_ = value;}; |
---|
146 | /// How lightweight - 0 not, 1 yes, 2 very lightweight |
---|
147 | inline int getLightweight() const |
---|
148 | { return lightWeight_;}; |
---|
149 | inline void setLightweight(int value) |
---|
150 | { lightWeight_ = value;}; |
---|
151 | //@} |
---|
152 | |
---|
153 | |
---|
154 | /// Stuff for internal use |
---|
155 | private: |
---|
156 | |
---|
157 | /// Does actual work |
---|
158 | void solve2(CoinMessageHandler * handler,const CoinMessages *messages); |
---|
159 | IdiotResult IdiSolve( |
---|
160 | int nrows, int ncols, double * rowsol , double * colsol, |
---|
161 | double * pi, double * djs, const double * origcost , |
---|
162 | const double * rowlower, |
---|
163 | double * rowupper, const double * lower, |
---|
164 | const double * upper, const double * element, |
---|
165 | const int * row, const CoinBigIndex * colcc, |
---|
166 | const int * length, double * lambda, |
---|
167 | int maxIts,double mu,double drop, |
---|
168 | double maxmin, double offset, |
---|
169 | int strategy,double djTol,double djExit,double djFlag); |
---|
170 | int dropping(IdiotResult result, |
---|
171 | double tolerance, |
---|
172 | double small, |
---|
173 | int *nbad); |
---|
174 | IdiotResult objval(int nrows, int ncols, double * rowsol , double * colsol, |
---|
175 | double * pi, double * djs, const double * cost , |
---|
176 | const double * rowlower, |
---|
177 | const double * rowupper, const double * lower, |
---|
178 | const double * upper, const double * elemnt, |
---|
179 | const int * row, const CoinBigIndex * columnStart, |
---|
180 | const int * length, int extraBlock, int * rowExtra, |
---|
181 | double * solExtra, double * elemExtra, double * upperExtra, |
---|
182 | double * costExtra,double weight); |
---|
183 | |
---|
184 | private: |
---|
185 | /// Underlying model |
---|
186 | OsiSolverInterface * model_; |
---|
187 | |
---|
188 | double djTolerance_; |
---|
189 | double mu_; /* starting mu */ |
---|
190 | double drop_; /* exit if drop over 5 checks less than this */ |
---|
191 | double muFactor_; /* reduce mu by this */ |
---|
192 | double stopMu_; /* exit if mu gets smaller than this */ |
---|
193 | double smallInfeas_; /* feasibility tolerance */ |
---|
194 | double reasonableInfeas_; /* use lambdas if feasibility less than this */ |
---|
195 | double exitDrop_; /* candidate for stopping after a major iteration */ |
---|
196 | double muAtExit_; /* mu on exit */ |
---|
197 | double exitFeasibility_; /* exit if infeasibility less than this */ |
---|
198 | double dropEnoughFeasibility_; /* okay if feasibility drop this factor */ |
---|
199 | double dropEnoughWeighted_; /* okay if weighted obj drop this factor */ |
---|
200 | int * whenUsed_; /* array to say what was used */ |
---|
201 | int maxBigIts_; /* always reduce mu after this */ |
---|
202 | int maxIts_; /* do this many iterations on first go */ |
---|
203 | int majorIterations_; |
---|
204 | int logLevel_; |
---|
205 | int logFreq_; |
---|
206 | int checkFrequency_; /* can exit after 5 * this iterations (on drop) */ |
---|
207 | int lambdaIterations_; /* do at least this many lambda iterations */ |
---|
208 | int maxIts2_; /* do this many iterations on subsequent goes */ |
---|
209 | int strategy_; /* 0 - default strategy |
---|
210 | 1 - do accelerator step but be cautious |
---|
211 | 2 - do not do accelerator step |
---|
212 | 4 - drop, exitDrop and djTolerance all relative |
---|
213 | 8 - keep accelerator step to theta=10.0 |
---|
214 | |
---|
215 | 32 - "intelligent?" reduction of mu and reasonableInfeas |
---|
216 | 2048 - keep lambda across mu change |
---|
217 | 4096 - return best solution (not last found) */ |
---|
218 | int lightWeight_; // 0 - normal, 1 lightweight |
---|
219 | }; |
---|
220 | #endif |
---|