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