source: branches/pre/include/Idiot.hpp @ 208

Last change on this file since 208 was 208, checked in by forrest, 17 years ago

Trying to make faster

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