source: branches/pre/include/ClpPdco.hpp @ 212

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

lots of stuff

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 9.6 KB
Line 
1// Copyright (C) 2003, International Business Machines
2// Corporation and others.  All Rights Reserved.
3
4/*
5   Authors
6   
7   John Tomlin
8
9 */
10#ifndef ClpPdco_H
11#define ClpPdco_H
12
13#include "ClpSimplex.hpp"
14
15/** This solves LPs using the dual simplex method
16
17    It inherits from ClpSimplex.  It has no data of its own and
18    is never created - only cast from a ClpSimplex object at algorithm time.
19
20*/
21
22class ClpPdco : public ClpSimplex {
23
24public:
25
26  /**@name Description of algorithm */
27  //@{
28  /** Dual algorithm
29
30      Method
31
32     It tries to be a single phase approach with a weight of 1.0 being
33     given to getting optimal and a weight of updatedDualBound_ being
34     given to getting dual feasible.  In this version I have used the
35     idea that this weight can be thought of as a fake bound.  If the
36     distance between the lower and upper bounds on a variable is less
37     than the feasibility weight then we are always better off flipping
38     to other bound to make dual feasible.  If the distance is greater
39     then we make up a fake bound updatedDualBound_ away from one bound.
40     If we end up optimal or primal infeasible, we check to see if
41     bounds okay.  If so we have finished, if not we increase updatedDualBound_
42     and continue (after checking if unbounded). I am undecided about
43     free variables - there is coding but I am not sure about it.  At
44     present I put them in basis anyway.
45
46     The code is designed to take advantage of sparsity so arrays are
47     seldom zeroed out from scratch or gone over in their entirety.
48     The only exception is a full scan to find outgoing variable for
49     Dantzig row choice.  For steepest edge we keep an updated list
50     of infeasibilities (actually squares). 
51     On easy problems we don't need full scan - just
52     pick first reasonable.
53
54     One problem is how to tackle degeneracy and accuracy.  At present
55     I am using the modification of costs which I put in OSL and some
56     of what I think is the dual analog of Gill et al.
57     I am still not sure of the exact details.
58
59     The flow of dual is three while loops as follows:
60
61     while (not finished) {
62
63       while (not clean solution) {
64
65          Factorize and/or clean up solution by flipping variables so
66          dual feasible.  If looks finished check fake dual bounds.
67          Repeat until status is iterating (-1) or finished (0,1,2)
68
69       }
70
71       while (status==-1) {
72
73         Iterate until no pivot in or out or time to re-factorize.
74
75         Flow is:
76
77         choose pivot row (outgoing variable).  if none then
78         we are primal feasible so looks as if done but we need to
79         break and check bounds etc.
80
81         Get pivot row in tableau
82
83         Choose incoming column.  If we don't find one then we look
84         primal infeasible so break and check bounds etc.  (Also the
85         pivot tolerance is larger after any iterations so that may be
86         reason)
87
88         If we do find incoming column, we may have to adjust costs to
89         keep going forwards (anti-degeneracy).  Check pivot will be stable
90         and if unstable throw away iteration and break to re-factorize.
91         If minor error re-factorize after iteration.
92
93         Update everything (this may involve flipping variables to stay
94         dual feasible.
95
96       }
97
98     }
99
100     TODO's (or maybe not)
101
102     At present we never check we are going forwards.  I overdid that in
103     OSL so will try and make a last resort.
104
105     Needs partial scan pivot out option.
106
107     May need other anti-degeneracy measures, especially if we try and use
108     loose tolerances as a way to solve in fewer iterations.
109
110     I like idea of dynamic scaling.  This gives opportunity to decouple
111     different implications of scaling for accuracy, iteration count and
112     feasibility tolerance.
113
114  */
115
116  int dual(int ifValuesPass);
117  /** For strong branching.  On input lower and upper are new bounds
118      while on output they are change in objective function values
119      (>1.0e50 infeasible).
120      Return code is 0 if nothing interesting, -1 if infeasible both
121      ways and +1 if infeasible one way (check values to see which one(s))
122      Solutions are filled in as well - even down, odd up - also
123      status and number of iterations
124  */
125  int strongBranching(int numberVariables,const int * variables,
126                      double * newLower, double * newUpper,
127                      double ** outputSolution,
128                      int * outputStatus, int * outputIterations,
129                      bool stopOnFirstInfeasible=true,
130                      bool alwaysFinish=false);
131  //@}
132
133  /**@name Functions used in dual */
134  //@{
135  /** This has the flow between re-factorizations
136      Broken out for clarity and will be used by strong branching
137
138      Reasons to come out:
139      -1 iterations etc
140      -2 inaccuracy
141      -3 slight inaccuracy (and done iterations)
142      +0 looks optimal (might be unbounded - but we will investigate)
143      +1 looks infeasible
144      +3 max iterations
145
146      If givenPi not NULL then in values pass
147   */
148  int whileIterating(double * & givenPi); 
149  /** The duals are updated by the given arrays.
150      Returns number of infeasibilities.
151      After rowArray and columnArray will just have those which
152      have been flipped.
153      Variables may be flipped between bounds to stay dual feasible.
154      The output vector has movement of primal
155      solution (row length array) */
156  int updateDualsInDual(CoinIndexedVector * rowArray,
157                  CoinIndexedVector * columnArray,
158                  CoinIndexedVector * outputArray,
159                  double theta,
160                  double & objectiveChange,
161                        bool fullRecompute);
162  /** The duals are updated by the given arrays.
163      This is in values pass - so no changes to primal is made
164  */
165  void updateDualsInValuesPass(CoinIndexedVector * rowArray,
166                  CoinIndexedVector * columnArray,
167                  double theta);
168  /** While updateDualsInDual sees what effect is of flip
169      this does actuall flipping.
170      If change >0.0 then value in array >0.0 => from lower to upper
171  */
172  void flipBounds(CoinIndexedVector * rowArray,
173                  CoinIndexedVector * columnArray,
174                  double change);
175  /**
176      Row array has row part of pivot row
177      Column array has column part.
178      This chooses pivot column.
179      Spare arrays are used to save pivots which will go infeasible
180      We will check for basic so spare array will never overflow.
181      If necessary will modify costs
182      For speed, we may need to go to a bucket approach when many
183      variables are being flipped
184
185  */
186  void dualColumn(CoinIndexedVector * rowArray,
187                  CoinIndexedVector * columnArray,
188                  CoinIndexedVector * spareArray,
189                  CoinIndexedVector * spareArray2,
190                  double accpetablePivot,
191                  CoinBigIndex * dubiousWeights);
192  /**
193      Row array has row part of pivot row
194      Column array has column part.
195      This sees what is best thing to do in dual values pass
196      Returns 0 if theta_ move will put basic variable out to bound,
197      1 if can change dual on chosen row and leave variable in basis
198  */
199  int checkPossibleValuesMove(CoinIndexedVector * rowArray,
200                               CoinIndexedVector * columnArray,
201                              double acceptablePivot,
202                              CoinBigIndex * dubiousWeights);
203  /**
204      This sees if we can move duals in dual values pass.
205      This is done before any pivoting
206  */
207  void doEasyOnesInValuesPass(double * givenReducedCosts);
208  /**
209      Chooses dual pivot row
210      Would be faster with separate region to scan
211      and will have this (with square of infeasibility) when steepest
212      For easy problems we can just choose one of the first rows we look at
213     
214      If alreadyChosen >=0 then in values pass and that row has been
215      selected
216  */
217  void dualRow(int alreadyChosen);
218  /** Checks if any fake bounds active - if so returns number and modifies
219      updatedDualBound_ and everything.
220      Free variables will be left as free
221      Returns number of bounds changed if >=0
222      Returns -1 if not initialize and no effect
223      Fills in changeVector which can be used to see if unbounded
224      and cost of change vector
225  */
226  int changeBounds(bool initialize,CoinIndexedVector * outputArray,
227                   double & changeCost);
228  /** As changeBounds but just changes new bounds for a single variable.
229      Returns true if change */
230  bool changeBound( int iSequence);
231  /// Restores bound to original bound
232  void originalBound(int iSequence);
233  /** Checks if tentative optimal actually means unbounded in dual
234      Returns -3 if not, 2 if is unbounded */
235  int checkUnbounded(CoinIndexedVector * ray,CoinIndexedVector * spare,
236                     double changeCost);
237  /**  Refactorizes if necessary
238       Checks if finished.  Updates status.
239       lastCleaned refers to iteration at which some objective/feasibility
240       cleaning too place.
241
242       type - 0 initial so set up save arrays etc
243            - 1 normal -if good update save
244            - 2 restoring from saved
245  */
246  void statusOfProblemInDual(int & lastCleaned, int type,
247                             ClpSimplexProgress * progress,
248                             double * givenDjs);
249  /// Perturbs problem (method depends on perturbation())
250  void perturb();
251  /** Fast iterations.  Misses out a lot of initialization.
252      Normally stops on maximum iterations, first re-factorization
253      or tentative optimum.  If looks interesting then continues as
254      normal.  Returns 0 if finished properly, 1 otherwise.
255  */
256  int fastDual(bool alwaysFinish=false);
257  /** Checks number of variables at fake bounds.  This is used by fastDual
258      so can exit gracefully before end */
259  int numberAtFakeBound();
260
261  /** Pivot in a variable and choose an outgoing one.  Assumes dual
262      feasible - will not go through a reduced cost.  Returns step length in theta
263      Returns ray in ray_ (or NULL if no pivot)
264      Return codes as before but -1 means no acceptable pivot
265  */
266  int pivotResult();
267  /** Get next free , -1 if none */
268  int nextSuperBasic();
269 
270  //@}
271};
272#endif
Note: See TracBrowser for help on using the repository browser.