source: trunk/include/Idiot.hpp @ 225

Last change on this file since 225 was 225, checked in by forrest, 16 years ago

This should break everything

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 7.8 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#ifdef CLP_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  //@}
156
157
158/// Stuff for internal use
159private:
160
161  /// Does actual work
162  void solve2(CoinMessageHandler * handler,const CoinMessages *messages);
163IdiotResult IdiSolve(
164                     int nrows, int ncols, double * rowsol , double * colsol,
165                     double * pi, double * djs, const double * origcost , 
166                     const double * rowlower,
167                     double * rowupper, const double * lower,
168                     const double * upper, const double * element, 
169                     const int * row, const CoinBigIndex * colcc,
170                     const int * length, double * lambda,
171                     int maxIts,double mu,double drop,
172                     double maxmin, double offset,
173                     int strategy,double djTol,double djExit,double djFlag);
174int dropping(IdiotResult result,
175             double tolerance,
176             double small,
177             int *nbad);
178IdiotResult objval(int nrows, int ncols, double * rowsol , double * colsol,
179                   double * pi, double * djs, const double * cost , 
180                   const double * rowlower,
181                   const double * rowupper, const double * lower,
182                   const double * upper, const double * elemnt, 
183                   const int * row, const CoinBigIndex * columnStart,
184                   const int * length, int extraBlock, int * rowExtra,
185                   double * solExtra, double * elemExtra, double * upperExtra,
186                   double * costExtra,double weight);
187
188private:
189  /// Underlying model
190  OsiSolverInterface * model_;
191
192  double djTolerance_;
193  double mu_;  /* starting mu */
194  double drop_; /* exit if drop over 5 checks less than this */
195  double muFactor_; /* reduce mu by this */
196  double stopMu_; /* exit if mu gets smaller than this */
197  double smallInfeas_; /* feasibility tolerance */
198  double reasonableInfeas_; /* use lambdas if feasibility less than this */
199  double exitDrop_; /* candidate for stopping after a major iteration */
200  double muAtExit_; /* mu on exit */
201  double exitFeasibility_; /* exit if infeasibility less than this */
202  double dropEnoughFeasibility_; /* okay if feasibility drop this factor */
203  double dropEnoughWeighted_; /* okay if weighted obj drop this factor */
204  int * whenUsed_; /* array to say what was used */
205  int maxBigIts_; /* always reduce mu after this */
206  int maxIts_; /* do this many iterations on first go */
207  int majorIterations_;
208  int logLevel_;
209  int logFreq_;
210  int checkFrequency_; /* can exit after 5 * this iterations (on drop) */
211  int lambdaIterations_; /* do at least this many lambda iterations */ 
212  int maxIts2_; /* do this many iterations on subsequent goes */
213  int strategy_;   /* 0 - default strategy
214                     1 - do accelerator step but be cautious
215                     2 - do not do accelerator step
216                     4 - drop, exitDrop and djTolerance all relative
217                     8 - keep accelerator step to theta=10.0
218
219                    32 - "intelligent?" reduction of mu and reasonableInfeas
220                  2048 - keep lambda across mu change
221                  4096 - return best solution (not last found) */
222  int lightWeight_; // 0 - normal, 1 lightweight
223};
224#endif
Note: See TracBrowser for help on using the repository browser.