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

Last change on this file since 2470 was 2385, checked in by unxusr, 10 months ago

formatting

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 9.6 KB
Line 
1/* $Id: Idiot.hpp 2385 2019-01-06 19:43:06Z 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  /**@name Constructors and destructor
52        Just a pointer to model is kept
53      */
54  //@{
55  /// Default constructor
56  Idiot();
57  /// Constructor with model
58  Idiot(OsiSolverInterface &model);
59
60  /// Copy constructor.
61  Idiot(const Idiot &);
62  /// Assignment operator. This copies the data
63  Idiot &operator=(const Idiot &rhs);
64  /// Destructor
65  ~Idiot();
66  //@}
67
68  /**@name Algorithmic calls
69      */
70  //@{
71  /// Get an approximate solution with the idiot code
72  void solve();
73  /// Lightweight "crash"
74  void crash(int numberPass, CoinMessageHandler *handler,
75    const CoinMessages *messages, bool doCrossover = true);
76  /** Use simplex to get an optimal solution
77         mode is how many steps the simplex crossover should take to
78         arrive to an extreme point:
79         0 - chosen,all ever used, all
80         1 - chosen, all
81         2 - all
82         3 - do not do anything  - maybe basis
83         + 16 do presolves
84     */
85  void crossOver(int mode);
86  //@}
87
88  /**@name Gets and sets of most useful data
89      */
90  //@{
91  /** Starting weight - small emphasizes feasibility,
92         default 1.0e-4 */
93  inline double getStartingWeight() const
94  {
95    return mu_;
96  }
97  inline void setStartingWeight(double value)
98  {
99    mu_ = value;
100  }
101  /** Weight factor - weight multiplied by this when changes,
102         default 0.333 */
103  inline double getWeightFactor() const
104  {
105    return muFactor_;
106  }
107  inline void setWeightFactor(double value)
108  {
109    muFactor_ = value;
110  }
111  /** Feasibility tolerance - problem essentially feasible if
112         individual infeasibilities less than this.
113         default 0.1 */
114  inline double getFeasibilityTolerance() const
115  {
116    return smallInfeas_;
117  }
118  inline void setFeasibilityTolerance(double value)
119  {
120    smallInfeas_ = value;
121  }
122  /** Reasonably feasible.  Dubious method concentrates more on
123         objective when sum of infeasibilities less than this.
124         Very dubious default value of (Number of rows)/20 */
125  inline double getReasonablyFeasible() const
126  {
127    return reasonableInfeas_;
128  }
129  inline void setReasonablyFeasible(double value)
130  {
131    reasonableInfeas_ = value;
132  }
133  /** Exit infeasibility - exit if sum of infeasibilities less than this.
134         Default -1.0 (i.e. switched off) */
135  inline double getExitInfeasibility() const
136  {
137    return exitFeasibility_;
138  }
139  inline void setExitInfeasibility(double value)
140  {
141    exitFeasibility_ = value;
142  }
143  /** Major iterations.  stop after this number.
144         Default 30.  Use 2-5 for "crash" 50-100 for serious crunching */
145  inline int getMajorIterations() const
146  {
147    return majorIterations_;
148  }
149  inline void setMajorIterations(int value)
150  {
151    majorIterations_ = value;
152  }
153  /** Minor iterations.  Do this number of tiny steps before
154         deciding whether to change weights etc.
155         Default - dubious sqrt(Number of Rows).
156         Good numbers 105 to 405 say (5 is dubious method of making sure
157         idiot is not trying to be clever which it may do every 10 minor
158         iterations) */
159  inline int getMinorIterations() const
160  {
161    return maxIts2_;
162  }
163  inline void setMinorIterations(int value)
164  {
165    maxIts2_ = value;
166  }
167  // minor iterations for first time
168  inline int getMinorIterations0() const
169  {
170    return maxIts_;
171  }
172  inline void setMinorIterations0(int value)
173  {
174    maxIts_ = value;
175  }
176  /** Reduce weight after this many major iterations.  It may
177         get reduced before this but this is a maximum.
178         Default 3.  3-10 plausible. */
179  inline int getReduceIterations() const
180  {
181    return maxBigIts_;
182  }
183  inline void setReduceIterations(int value)
184  {
185    maxBigIts_ = value;
186  }
187  /// Amount of information - default of 1 should be okay
188  inline int getLogLevel() const
189  {
190    return logLevel_;
191  }
192  inline void setLogLevel(int value)
193  {
194    logLevel_ = value;
195  }
196  /// How lightweight - 0 not, 1 yes, 2 very lightweight
197  inline int getLightweight() const
198  {
199    return lightWeight_;
200  }
201  inline void setLightweight(int value)
202  {
203    lightWeight_ = value;
204  }
205  /// strategy
206  inline int getStrategy() const
207  {
208    return strategy_;
209  }
210  inline void setStrategy(int value)
211  {
212    strategy_ = value;
213  }
214  /// Fine tuning - okay if feasibility drop this factor
215  inline double getDropEnoughFeasibility() const
216  {
217    return dropEnoughFeasibility_;
218  }
219  inline void setDropEnoughFeasibility(double value)
220  {
221    dropEnoughFeasibility_ = value;
222  }
223  /// Fine tuning - okay if weighted obj drop this factor
224  inline double getDropEnoughWeighted() const
225  {
226    return dropEnoughWeighted_;
227  }
228  inline void setDropEnoughWeighted(double value)
229  {
230    dropEnoughWeighted_ = value;
231  }
232  /// Set model
233  inline void setModel(OsiSolverInterface *model)
234  {
235    model_ = model;
236  };
237  //@}
238
239  /// Stuff for internal use
240private:
241  /// Does actual work
242  // allow public!
243public:
244  void solve2(CoinMessageHandler *handler, const CoinMessages *messages);
245
246private:
247  IdiotResult IdiSolve(
248    int nrows, int ncols, double *rowsol, double *colsol,
249    double *pi, double *djs, const double *origcost,
250    double *rowlower,
251    double *rowupper, const double *lower,
252    const double *upper, const double *element,
253    const int *row, const CoinBigIndex *colcc,
254    const int *length, double *lambda,
255    int maxIts, double mu, double drop,
256    double maxmin, double offset,
257    int strategy, double djTol, double djExit, double djFlag,
258    CoinThreadRandom *randomNumberGenerator);
259  int dropping(IdiotResult result,
260    double tolerance,
261    double small,
262    int *nbad);
263  IdiotResult objval(int nrows, int ncols, double *rowsol, double *colsol,
264    double *pi, double *djs, const double *cost,
265    const double *rowlower,
266    const double *rowupper, const double *lower,
267    const double *upper, const double *elemnt,
268    const int *row, const CoinBigIndex *columnStart,
269    const int *length, int extraBlock, int *rowExtra,
270    double *solExtra, double *elemExtra, double *upperExtra,
271    double *costExtra, double weight);
272  // Deals with whenUsed and slacks
273  int cleanIteration(int iteration, int ordinaryStart, int ordinaryEnd,
274    double *colsol, const double *lower, const double *upper,
275    const double *rowLower, const double *rowUpper,
276    const double *cost, const double *element, double fixTolerance, double &objChange,
277    double &infChange, double &maxInfeasibility);
278
279private:
280  /// Underlying model
281  OsiSolverInterface *model_;
282
283  double djTolerance_;
284  double mu_; /* starting mu */
285  double drop_; /* exit if drop over 5 checks less than this */
286  double muFactor_; /* reduce mu by this */
287  double stopMu_; /* exit if mu gets smaller than this */
288  double smallInfeas_; /* feasibility tolerance */
289  double reasonableInfeas_; /* use lambdas if feasibility less than this */
290  double exitDrop_; /* candidate for stopping after a major iteration */
291  double muAtExit_; /* mu on exit */
292  double exitFeasibility_; /* exit if infeasibility less than this */
293  double dropEnoughFeasibility_; /* okay if feasibility drop this factor */
294  double dropEnoughWeighted_; /* okay if weighted obj drop this factor */
295  int *whenUsed_; /* array to say what was used */
296  int maxBigIts_; /* always reduce mu after this */
297  int maxIts_; /* do this many iterations on first go */
298  int majorIterations_;
299  int logLevel_;
300  int logFreq_;
301  int checkFrequency_; /* can exit after 5 * this iterations (on drop) */
302  int lambdaIterations_; /* do at least this many lambda iterations */
303  int maxIts2_; /* do this many iterations on subsequent goes */
304  int strategy_; /* 0 - default strategy
305                     1 - do accelerator step but be cautious
306                     2 - do not do accelerator step
307                     4 - drop, exitDrop and djTolerance all relative
308                     8 - keep accelerator step to theta=10.0
309
310                    32 - Scale
311                   512 - crossover
312                  2048 - keep lambda across mu change
313                  4096 - return best solution (not last found)
314                  8192 - always do a presolve in crossover
315                 16384 - costed slacks found - so whenUsed_ longer
316                 32768 - experimental 1
317                 65536 - experimental 2
318                 131072 - experimental 3
319                 262144 - just values pass etc
320                 524288 - don't treat structural slacks as slacks */
321
322  int lightWeight_; // 0 - normal, 1 lightweight
323};
324#endif
325
326/* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2
327*/
Note: See TracBrowser for help on using the repository browser.