source: trunk/Clp/src/ClpSimplexOther.hpp @ 912

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