source: branches/devel/Clp/src/ClpSimplexOther.hpp @ 911

Last change on this file since 911 was 911, checked in by forrest, 13 years ago

ranging

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 7.7 KB
Line 
1// Copyright (C) 2004, International Business Machines
2// Corporation and others.  All Rights Reserved.
3
4/*
5   Authors
6   
7   John Forrest
8
9 */
10#ifndef ClpSimplexOther_H
11#define ClpSimplexOther_H
12
13#include "ClpSimplex.hpp"
14
15/** This is for Simplex stuff which is neither dual nor primal
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 ClpSimplexOther : public ClpSimplex {
23
24public:
25
26  /**@name Methods */
27  //@{
28  /** Dual ranging.
29      This computes increase/decrease in cost for each given variable and corresponding
30      sequence numbers which would change basis.  Sequence numbers are 0..numberColumns
31      and numberColumns.. for artificials/slacks.
32      For non-basic variables the information is trivial to compute and the change in cost is just minus the
33      reduced cost and the sequence number will be that of the non-basic variables.
34      For basic variables a ratio test is between the reduced costs for non-basic variables
35      and the row of the tableau corresponding to the basic variable.
36      The increase/decrease value is always >= 0.0
37
38      Up to user to provide correct length arrays where each array is of length numberCheck.
39      which contains list of variables for which information is desired.  All other
40      arrays will be filled in by function.  If fifth entry in which is variable 7 then fifth entry in output arrays
41      will be information for variable 7.
42
43      If valueIncrease/Decrease not NULL (both must be NULL or both non NULL) then these are filled with
44      the value of variable if such a change in cost were made (the existing bounds are ignored)
45
46      When here - guaranteed optimal
47  */
48  void dualRanging(int numberCheck,const int * which,
49                   double * costIncrease, int * sequenceIncrease,
50                   double * costDecrease, int * sequenceDecrease,
51                   double * valueIncrease=NULL, double * valueDecrease=NULL);
52  /** Primal ranging.
53      This computes increase/decrease in value for each given variable and corresponding
54      sequence numbers which would change basis.  Sequence numbers are 0..numberColumns
55      and numberColumns.. for artificials/slacks.
56      This should only be used for non-basic variabls as otherwise information is pretty useless
57      For basic variables the sequence number will be that of the basic variables.
58
59      Up to user to provide correct length arrays where each array is of length numberCheck.
60      which contains list of variables for which information is desired.  All other
61      arrays will be filled in by function.  If fifth entry in which is variable 7 then fifth entry in output arrays
62      will be information for variable 7.
63
64      When here - guaranteed optimal
65  */
66  void primalRanging(int numberCheck,const int * which,
67                  double * valueIncrease, int * sequenceIncrease,
68                  double * valueDecrease, int * sequenceDecrease);
69  /** Parametrics
70      This is an initial slow version.
71      The code uses current bounds + theta * change (if change array not NULL)
72      and similarly for objective.
73      It starts at startingTheta and returns ending theta in endingTheta.
74      If reportIncrement 0.0 it will report on any movement
75      If reportIncrement >0.0 it will report at startingTheta+k*reportIncrement.
76      If it can not reach input endingTheta return code will be 1 for infeasible,
77      2 for unbounded, if error on ranges -1,  otherwise 0.
78      Normal report is just theta and objective but
79      if event handler exists it may do more
80      On exit endingTheta is maximum reached (can be used for next startingTheta)
81  */
82  int parametrics(double startingTheta, double & endingTheta,double reportIncrement,
83                  const double * changeLowerBound, const double * changeUpperBound,
84                  const double * changeLowerRhs, const double * changeUpperRhs,
85                  const double * changeObjective);
86private:
87  /** Parametrics - inner loop
88      This first attempt is when reportIncrement non zero and may
89      not report endingTheta correctly
90      If it can not reach input endingTheta return code will be 1 for infeasible,
91      2 for unbounded,  otherwise 0.
92      Normal report is just theta and objective but
93      if event handler exists it may do more
94  */
95  int parametricsLoop(double startingTheta, double & endingTheta,double reportIncrement,
96                      const double * changeLower, const double * changeUpper,
97                      const double * changeObjective, ClpDataSave & data,
98                      bool canTryQuick);
99  /**  Refactorizes if necessary
100       Checks if finished.  Updates status.
101
102       type - 0 initial so set up save arrays etc
103            - 1 normal -if good update save
104            - 2 restoring from saved
105  */
106  void statusOfProblemInParametrics(int type,ClpDataSave & saveData);
107  /** This has the flow between re-factorizations
108
109      Reasons to come out:
110      -1 iterations etc
111      -2 inaccuracy
112      -3 slight inaccuracy (and done iterations)
113      +0 looks optimal (might be unbounded - but we will investigate)
114      +1 looks infeasible
115      +3 max iterations
116   */
117  int whileIterating(double startingTheta, double & endingTheta,double reportIncrement,
118                      const double * changeLower, const double * changeUpper,
119                      const double * changeObjective);
120  /** Computes next theta and says if objective or bounds (0= bounds, 1 objective, -1 none).
121      theta is in theta_.
122      type 1 bounds, 2 objective, 3 both.
123  */
124  int nextTheta(int type, double maxTheta, double * primalChange, double * dualChange,
125                      const double * changeLower, const double * changeUpper,
126                      const double * changeObjective);
127  /**
128      Row array has row part of pivot row
129      Column array has column part.
130      This is used in dual ranging
131  */
132  void checkDualRatios(CoinIndexedVector * rowArray,
133                   CoinIndexedVector * columnArray,
134                       double & costIncrease, int & sequenceIncrease, double & alphaIncrease,
135                       double & costDecrease, int & sequenceDecrease, double & alphaDecrease);
136  /**
137      Row array has pivot column
138      This is used in primal ranging
139  */
140  void checkPrimalRatios(CoinIndexedVector * rowArray,
141                         int direction);
142  /// Returns new value of whichOther when whichIn enters basis
143  double primalRanging1(int whichIn, int whichOther);
144
145public:
146    /** Write the basis in MPS format to the specified file.
147        If writeValues true writes values of structurals
148        (and adds VALUES to end of NAME card)
149
150        Row and column names may be null.
151        formatType is
152        <ul>
153          <li> 0 - normal
154          <li> 1 - extra accuracy
155          <li> 2 - IEEE hex (later)
156        </ul>
157
158        Returns non-zero on I/O error
159    */
160    int writeBasis(const char *filename,
161                 bool writeValues=false,
162                 int formatType=0) const;
163    /// Read a basis from the given filename
164    int readBasis(const char *filename);
165  /// Creates dual of a problem
166  ClpSimplex * dualOfModel() const;
167  /** Restores solution from dualized problem
168      non-zero return code indicates minor problems
169  */
170  int restoreFromDual(const ClpSimplex * dualProblem);
171  /** Does very cursory presolve.
172      rhs is numberRows, whichRows is 3*numberRows and whichColumns is 2*numberColumns.
173  */
174  ClpSimplex * crunch(double * rhs, int * whichRows, int * whichColumns,
175                      int & nBound, bool moreBounds=false, bool tightenBounds=false);
176  /** After very cursory presolve.
177      rhs is numberRows, whichRows is 3*numberRows and whichColumns is 2*numberColumns.
178  */
179  void afterCrunch(const ClpSimplex & small,
180                   const int * whichRows, const int * whichColumns,
181                   int nBound);
182  /** Tightens integer bounds - returns number tightened or -1 if infeasible
183  */
184  int tightenIntegerBounds(double * rhsSpace); 
185  //@}
186};
187#endif
Note: See TracBrowser for help on using the repository browser.