source: trunk/Clp/src/ClpSimplexDual.hpp @ 2385

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

formatting

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 11.6 KB
Line 
1/* $Id: ClpSimplexDual.hpp 2385 2019-01-06 19:43:06Z unxusr $ */
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   Authors
7
8   John Forrest
9
10 */
11#ifndef ClpSimplexDual_H
12#define ClpSimplexDual_H
13
14#include "ClpSimplex.hpp"
15
16/** This solves LPs using the dual simplex method
17
18    It inherits from ClpSimplex.  It has no data of its own and
19    is never created - only cast from a ClpSimplex object at algorithm time.
20
21*/
22
23class ClpSimplexDual : public ClpSimplex {
24
25public:
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        for use of exotic parameter startFinishoptions see Clpsimplex.hpp
115     */
116
117  int dual(int ifValuesPass, int startFinishOptions = 0);
118  /** For strong branching.  On input lower and upper are new bounds
119         while on output they are change in objective function values
120         (>1.0e50 infeasible).
121         Return code is 0 if nothing interesting, -1 if infeasible both
122         ways and +1 if infeasible one way (check values to see which one(s))
123         Solutions are filled in as well - even down, odd up - also
124         status and number of iterations
125     */
126  int strongBranching(int numberVariables, const int *variables,
127    double *newLower, double *newUpper,
128    double **outputSolution,
129    int *outputStatus, int *outputIterations,
130    bool stopOnFirstInfeasible = true,
131    bool alwaysFinish = false,
132    int startFinishOptions = 0);
133  /// This does first part of StrongBranching
134  ClpFactorization *setupForStrongBranching(char *arrays, int numberRows,
135    int numberColumns, bool solveLp = false);
136  /// This cleans up after strong branching
137  void cleanupAfterStrongBranching(ClpFactorization *factorization);
138  //@}
139
140  /**@name Functions used in dual */
141  //@{
142  /** This has the flow between re-factorizations
143         Broken out for clarity and will be used by strong branching
144
145         Reasons to come out:
146         -1 iterations etc
147         -2 inaccuracy
148         -3 slight inaccuracy (and done iterations)
149         +0 looks optimal (might be unbounded - but we will investigate)
150         +1 looks infeasible
151         +3 max iterations
152
153         If givenPi not NULL then in values pass
154      */
155  int whileIterating(double *&givenPi, int ifValuesPass);
156  /** The duals are updated by the given arrays.
157         Returns number of infeasibilities.
158         After rowArray and columnArray will just have those which
159         have been flipped.
160         Variables may be flipped between bounds to stay dual feasible.
161         The output vector has movement of primal
162         solution (row length array) */
163  int updateDualsInDual(CoinIndexedVector *rowArray,
164    CoinIndexedVector *columnArray,
165    CoinIndexedVector *outputArray,
166    double theta,
167    double &objectiveChange,
168    bool fullRecompute);
169  /** The duals are updated by the given arrays.
170         This is in values pass - so no changes to primal is made
171     */
172  void updateDualsInValuesPass(CoinIndexedVector *rowArray,
173    CoinIndexedVector *columnArray,
174    double theta);
175  /** While updateDualsInDual sees what effect is of flip
176         this does actual flipping.
177     */
178  void flipBounds(CoinIndexedVector *rowArray,
179    CoinIndexedVector *columnArray);
180  /**
181         Row array has row part of pivot row
182         Column array has column part.
183         This chooses pivot column.
184         Spare arrays are used to save pivots which will go infeasible
185         We will check for basic so spare array will never overflow.
186         If necessary will modify costs
187         For speed, we may need to go to a bucket approach when many
188         variables are being flipped.
189         Returns best possible pivot value
190     */
191  double dualColumn(CoinIndexedVector *rowArray,
192    CoinIndexedVector *columnArray,
193    CoinIndexedVector *spareArray,
194    CoinIndexedVector *spareArray2,
195    double accpetablePivot,
196    CoinBigIndex *dubiousWeights);
197  /// Does first bit of dualColumn
198  int dualColumn0(const CoinIndexedVector *rowArray,
199    const CoinIndexedVector *columnArray,
200    CoinIndexedVector *spareArray,
201    double acceptablePivot,
202    double &upperReturn, double &badFree);
203  /**
204         Row array has row part of pivot row
205         Column array has column part.
206         This sees what is best thing to do in dual values pass
207         if sequenceIn==sequenceOut can change dual on chosen row and leave variable in basis
208     */
209  void checkPossibleValuesMove(CoinIndexedVector *rowArray,
210    CoinIndexedVector *columnArray,
211    double acceptablePivot);
212  /**
213         Row array has row part of pivot row
214         Column array has column part.
215         This sees what is best thing to do in branch and bound cleanup
216         If sequenceIn_ < 0 then can't do anything
217     */
218  void checkPossibleCleanup(CoinIndexedVector *rowArray,
219    CoinIndexedVector *columnArray,
220    double acceptablePivot);
221  /**
222         This sees if we can move duals in dual values pass.
223         This is done before any pivoting
224     */
225  void doEasyOnesInValuesPass(double *givenReducedCosts);
226  /**
227         Chooses dual pivot row
228         Would be faster with separate region to scan
229         and will have this (with square of infeasibility) when steepest
230         For easy problems we can just choose one of the first rows we look at
231
232         If alreadyChosen >=0 then in values pass and that row has been
233         selected
234     */
235  void dualRow(int alreadyChosen);
236  /** Checks if any fake bounds active - if so returns number and modifies
237         updatedDualBound_ and everything.
238         Free variables will be left as free
239         Returns number of bounds changed if >=0
240         Returns -1 if not initialize and no effect
241         Fills in changeVector which can be used to see if unbounded
242         and cost of change vector
243         If 2 sets to original (just changed)
244     */
245  int changeBounds(int initialize, CoinIndexedVector *outputArray,
246    double &changeCost);
247  /// Just checks if any fake bounds active - if so returns number
248  int checkFakeBounds() const;
249  /** As changeBounds but just changes new bounds for a single variable.
250         Returns true if change */
251  bool changeBound(int iSequence);
252  /// Restores bound to original bound
253  void originalBound(int iSequence);
254  /** Checks if tentative optimal actually means unbounded in dual
255         Returns -3 if not, 2 if is unbounded */
256  int checkUnbounded(CoinIndexedVector *ray, CoinIndexedVector *spare,
257    double changeCost);
258  /**  Refactorizes if necessary
259          Checks if finished.  Updates status.
260          lastCleaned refers to iteration at which some objective/feasibility
261          cleaning too place.
262
263          type - 0 initial so set up save arrays etc
264               - 1 normal -if good update save
265           - 2 restoring from saved
266     */
267  void statusOfProblemInDual(int &lastCleaned, int type,
268    double *givenDjs, ClpDataSave &saveData,
269    int ifValuesPass);
270  /** Perturbs problem (method depends on perturbation())
271         returns nonzero if should go to dual */
272  int perturb();
273  /** Fast iterations.  Misses out a lot of initialization.
274         Normally stops on maximum iterations, first re-factorization
275         or tentative optimum.  If looks interesting then continues as
276         normal.  Returns 0 if finished properly, 1 otherwise.
277     */
278  int fastDual(bool alwaysFinish = false);
279  /** Checks number of variables at fake bounds.  This is used by fastDual
280         so can exit gracefully before end */
281  int numberAtFakeBound();
282
283  /** Pivot in a variable and choose an outgoing one.  Assumes dual
284         feasible - will not go through a reduced cost.  Returns step length in theta
285         Return codes as before but -1 means no acceptable pivot
286     */
287  int pivotResultPart1();
288  /** Get next free , -1 if none */
289  int nextSuperBasic();
290  /** Startup part of dual (may be extended to other algorithms)
291         returns 0 if good, 1 if bad */
292  int startupSolve(int ifValuesPass, double *saveDuals, int startFinishOptions);
293  void finishSolve(int startFinishOptions);
294  void gutsOfDual(int ifValuesPass, double *&saveDuals, int initialStatus,
295    ClpDataSave &saveData);
296  //int dual2(int ifValuesPass,int startFinishOptions=0);
297  void resetFakeBounds(int type);
298
299  //@}
300};
301#endif
302
303/* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2
304*/
Note: See TracBrowser for help on using the repository browser.