source: branches/devel/Clp/src/Idiot.hpp @ 982

Last change on this file since 982 was 982, checked in by forrest, 13 years ago

try a few more options

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 8.6 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  void solve2(CoinMessageHandler * handler,const CoinMessages *messages);
183IdiotResult IdiSolve(
184                     int nrows, int ncols, double * rowsol , double * colsol,
185                     double * pi, double * djs, const double * origcost , 
186                     double * rowlower,
187                     double * rowupper, const double * lower,
188                     const double * upper, const double * element, 
189                     const int * row, const CoinBigIndex * colcc,
190                     const int * length, double * lambda,
191                     int maxIts,double mu,double drop,
192                     double maxmin, double offset,
193                     int strategy,double djTol,double djExit,double djFlag);
194int dropping(IdiotResult result,
195             double tolerance,
196             double small,
197             int *nbad);
198IdiotResult objval(int nrows, int ncols, double * rowsol , double * colsol,
199                   double * pi, double * djs, const double * cost , 
200                   const double * rowlower,
201                   const double * rowupper, const double * lower,
202                   const double * upper, const double * elemnt, 
203                   const int * row, const CoinBigIndex * columnStart,
204                   const int * length, int extraBlock, int * rowExtra,
205                   double * solExtra, double * elemExtra, double * upperExtra,
206                   double * costExtra,double weight);
207
208private:
209  /// Underlying model
210  OsiSolverInterface * model_;
211
212  double djTolerance_;
213  double mu_;  /* starting mu */
214  double drop_; /* exit if drop over 5 checks less than this */
215  double muFactor_; /* reduce mu by this */
216  double stopMu_; /* exit if mu gets smaller than this */
217  double smallInfeas_; /* feasibility tolerance */
218  double reasonableInfeas_; /* use lambdas if feasibility less than this */
219  double exitDrop_; /* candidate for stopping after a major iteration */
220  double muAtExit_; /* mu on exit */
221  double exitFeasibility_; /* exit if infeasibility less than this */
222  double dropEnoughFeasibility_; /* okay if feasibility drop this factor */
223  double dropEnoughWeighted_; /* okay if weighted obj drop this factor */
224  int * whenUsed_; /* array to say what was used */
225  int maxBigIts_; /* always reduce mu after this */
226  int maxIts_; /* do this many iterations on first go */
227  int majorIterations_;
228  int logLevel_;
229  int logFreq_;
230  int checkFrequency_; /* can exit after 5 * this iterations (on drop) */
231  int lambdaIterations_; /* do at least this many lambda iterations */ 
232  int maxIts2_; /* do this many iterations on subsequent goes */
233  int strategy_;   /* 0 - default strategy
234                     1 - do accelerator step but be cautious
235                     2 - do not do accelerator step
236                     4 - drop, exitDrop and djTolerance all relative
237                     8 - keep accelerator step to theta=10.0
238
239                    32 - Scale
240                   512 - crossover
241                  2048 - keep lambda across mu change
242                  4096 - return best solution (not last found)
243                  8192 - always do a presolve in crossover */
244  int lightWeight_; // 0 - normal, 1 lightweight
245};
246#endif
Note: See TracBrowser for help on using the repository browser.