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

Last change on this file since 754 was 754, checked in by andreasw, 14 years ago

first version

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 8.4 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  /** Reduce weight after this many major iterations.  It may
139      get reduced before this but this is a maximum.
140      Default 3.  3-10 plausible. */
141  inline int getReduceIterations() const
142  { return maxBigIts_;};
143  inline void setReduceIterations(int value)
144  { maxBigIts_ = value;};
145  /// Amount of information - default of 1 should be okay
146  inline int getLogLevel() const
147  { return logLevel_;};
148  inline void setLogLevel(int value)
149  { logLevel_ = value;};
150  /// How lightweight - 0 not, 1 yes, 2 very lightweight
151  inline int getLightweight() const
152  { return lightWeight_;};
153  inline void setLightweight(int value)
154  { lightWeight_ = value;};
155  /// strategy
156  inline int getStrategy() const
157  { return strategy_;};
158  inline void setStrategy(int value)
159  { strategy_ = value;};
160  /// Fine tuning - okay if feasibility drop this factor
161  inline double getDropEnoughFeasibility() const
162  { return dropEnoughFeasibility_;};
163  inline void setDropEnoughFeasibility(double value)
164  { dropEnoughFeasibility_=value;};
165  /// Fine tuning - okay if weighted obj drop this factor
166  inline double getDropEnoughWeighted() const
167  { return dropEnoughWeighted_;};
168  inline void setDropEnoughWeighted(double value)
169  { dropEnoughWeighted_=value;};
170  //@}
171
172
173/// Stuff for internal use
174private:
175
176  /// Does actual work
177  void solve2(CoinMessageHandler * handler,const CoinMessages *messages);
178IdiotResult IdiSolve(
179                     int nrows, int ncols, double * rowsol , double * colsol,
180                     double * pi, double * djs, const double * origcost , 
181                     double * rowlower,
182                     double * rowupper, const double * lower,
183                     const double * upper, const double * element, 
184                     const int * row, const CoinBigIndex * colcc,
185                     const int * length, double * lambda,
186                     int maxIts,double mu,double drop,
187                     double maxmin, double offset,
188                     int strategy,double djTol,double djExit,double djFlag);
189int dropping(IdiotResult result,
190             double tolerance,
191             double small,
192             int *nbad);
193IdiotResult objval(int nrows, int ncols, double * rowsol , double * colsol,
194                   double * pi, double * djs, const double * cost , 
195                   const double * rowlower,
196                   const double * rowupper, const double * lower,
197                   const double * upper, const double * elemnt, 
198                   const int * row, const CoinBigIndex * columnStart,
199                   const int * length, int extraBlock, int * rowExtra,
200                   double * solExtra, double * elemExtra, double * upperExtra,
201                   double * costExtra,double weight);
202
203private:
204  /// Underlying model
205  OsiSolverInterface * model_;
206
207  double djTolerance_;
208  double mu_;  /* starting mu */
209  double drop_; /* exit if drop over 5 checks less than this */
210  double muFactor_; /* reduce mu by this */
211  double stopMu_; /* exit if mu gets smaller than this */
212  double smallInfeas_; /* feasibility tolerance */
213  double reasonableInfeas_; /* use lambdas if feasibility less than this */
214  double exitDrop_; /* candidate for stopping after a major iteration */
215  double muAtExit_; /* mu on exit */
216  double exitFeasibility_; /* exit if infeasibility less than this */
217  double dropEnoughFeasibility_; /* okay if feasibility drop this factor */
218  double dropEnoughWeighted_; /* okay if weighted obj drop this factor */
219  int * whenUsed_; /* array to say what was used */
220  int maxBigIts_; /* always reduce mu after this */
221  int maxIts_; /* do this many iterations on first go */
222  int majorIterations_;
223  int logLevel_;
224  int logFreq_;
225  int checkFrequency_; /* can exit after 5 * this iterations (on drop) */
226  int lambdaIterations_; /* do at least this many lambda iterations */ 
227  int maxIts2_; /* do this many iterations on subsequent goes */
228  int strategy_;   /* 0 - default strategy
229                     1 - do accelerator step but be cautious
230                     2 - do not do accelerator step
231                     4 - drop, exitDrop and djTolerance all relative
232                     8 - keep accelerator step to theta=10.0
233
234                    32 - Scale
235                   512 - crossover
236                  2048 - keep lambda across mu change
237                  4096 - return best solution (not last found) */
238  int lightWeight_; // 0 - normal, 1 lightweight
239};
240#endif
Note: See TracBrowser for help on using the repository browser.