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

Last change on this file since 1141 was 1141, checked in by forrest, 12 years ago

for threaded random numbers

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