source: stable/1.15/Clp/src/Idiot.hpp @ 1995

Last change on this file since 1995 was 1665, checked in by lou, 9 years ago

Add EPL license notice in src.

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