source: trunk/Clp/src/Idiot.hpp @ 1525

Last change on this file since 1525 was 1525, checked in by mjs, 10 years ago

Formatted .cpp, .hpp, .c, .h files with "astyle -A4 -p". This matches the formatting used in the grand CBC reorganization.

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