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

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

fixes for various ideas

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 8.9 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 if looks plausible
166      (defaults will always create model)
167      fractionRowRanges is fraction of rows allowed to have ranges
168      fractionColumnRanges is fraction of columns allowed to have ranges
169  */
170  ClpSimplex * dualOfModel(double fractionRowRanges=1.0,double fractionColumnRanges=1.0) const;
171  /** Restores solution from dualized problem
172      non-zero return code indicates minor problems
173  */
174  int restoreFromDual(const ClpSimplex * dualProblem);
175  /** Does very cursory presolve.
176      rhs is numberRows, whichRows is 3*numberRows and whichColumns is 2*numberColumns.
177  */
178  ClpSimplex * crunch(double * rhs, int * whichRows, int * whichColumns,
179                      int & nBound, bool moreBounds=false, bool tightenBounds=false);
180  /** After very cursory presolve.
181      rhs is numberRows, whichRows is 3*numberRows and whichColumns is 2*numberColumns.
182  */
183  void afterCrunch(const ClpSimplex & small,
184                   const int * whichRows, const int * whichColumns,
185                   int nBound);
186  /** Tightens integer bounds - returns number tightened or -1 if infeasible
187  */
188  int tightenIntegerBounds(double * rhsSpace); 
189  /** Expands out all possible combinations for a knapsack
190      If buildObj NULL then just computes space needed - returns number elements
191      On entry numberOutput is maximum allowed, on exit it is number needed or
192      -1 (as will be number elements) if maximum exceeded.  numberOutput will have at
193      least space to return values which reconstruct input.
194      Rows returned will be original rows but no entries will be returned for
195      any rows all of whose entries are in knapsack.  So up to user to allow for this.
196      If reConstruct >=0 then returns number of entrie which make up item "reConstruct"
197      in expanded knapsack.  Values in buildRow and buildElement;
198  */
199  int expandKnapsack(int knapsackRow, int & numberOutput,
200                     double * buildObj, CoinBigIndex * buildStart,
201                     int * buildRow, double * buildElement,int reConstruct=-1) const;
202  //@}
203};
204#endif
Note: See TracBrowser for help on using the repository browser.