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

Last change on this file since 1780 was 1780, checked in by forrest, 9 years ago

stuff for parametrics

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 11.4 KB
Line 
1/* $Id: ClpSimplexOther.hpp 1780 2011-08-11 07:15:40Z forrest $ */
2// Copyright (C) 2004, 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 ClpSimplexOther_H
12#define ClpSimplexOther_H
13
14#include "ClpSimplex.hpp"
15
16/** This is for Simplex stuff which is neither dual nor primal
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 ClpSimplexOther : public ClpSimplex {
24
25public:
26
27     /**@name Methods */
28     //@{
29     /** Dual ranging.
30         This computes increase/decrease in cost for each given variable and corresponding
31         sequence numbers which would change basis.  Sequence numbers are 0..numberColumns
32         and numberColumns.. for artificials/slacks.
33         For non-basic variables the information is trivial to compute and the change in cost is just minus the
34         reduced cost and the sequence number will be that of the non-basic variables.
35         For basic variables a ratio test is between the reduced costs for non-basic variables
36         and the row of the tableau corresponding to the basic variable.
37         The increase/decrease value is always >= 0.0
38
39         Up to user to provide correct length arrays where each array is of length numberCheck.
40         which contains list of variables for which information is desired.  All other
41         arrays will be filled in by function.  If fifth entry in which is variable 7 then fifth entry in output arrays
42         will be information for variable 7.
43
44         If valueIncrease/Decrease not NULL (both must be NULL or both non NULL) then these are filled with
45         the value of variable if such a change in cost were made (the existing bounds are ignored)
46
47         When here - guaranteed optimal
48     */
49     void dualRanging(int numberCheck, const int * which,
50                      double * costIncrease, int * sequenceIncrease,
51                      double * costDecrease, int * sequenceDecrease,
52                      double * valueIncrease = NULL, double * valueDecrease = NULL);
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);
87     /** Version of parametrics which reads from file
88         See CbcClpParam.cpp for details of format
89         Returns -2 if unable to open file */
90     int parametrics(const char * dataFile);
91     /** Parametrics
92         This is an initial slow version.
93         The code uses current bounds + theta * change (if change array not NULL)
94         It starts at startingTheta and returns ending theta in endingTheta.
95         If it can not reach input endingTheta return code will be 1 for infeasible,
96         2 for unbounded, if error on ranges -1,  otherwise 0.
97         Event handler may do more
98         On exit endingTheta is maximum reached (can be used for next startingTheta)
99     */
100     int parametrics(double startingTheta, double & endingTheta, 
101                     const double * changeLowerBound, const double * changeUpperBound,
102                     const double * changeLowerRhs, const double * changeUpperRhs);
103    /// Finds best possible pivot
104    double bestPivot(bool justColumns=false);
105
106private:
107     /** Parametrics - inner loop
108         This first attempt is when reportIncrement non zero and may
109         not report endingTheta correctly
110         If it can not reach input endingTheta return code will be 1 for infeasible,
111         2 for unbounded,  otherwise 0.
112         Normal report is just theta and objective but
113         if event handler exists it may do more
114     */
115     int parametricsLoop(double startingTheta, double & endingTheta, double reportIncrement,
116                         const double * changeLower, const double * changeUpper,
117                         const double * changeObjective, ClpDataSave & data,
118                         bool canTryQuick);
119     int parametricsLoop(double & startingTheta, double & endingTheta,
120                         ClpDataSave & data,bool canSkipFactorization=false);
121     /**  Refactorizes if necessary
122          Checks if finished.  Updates status.
123
124          type - 0 initial so set up save arrays etc
125               - 1 normal -if good update save
126           - 2 restoring from saved
127     */
128     void statusOfProblemInParametrics(int type, ClpDataSave & saveData);
129     /** This has the flow between re-factorizations
130
131         Reasons to come out:
132         -1 iterations etc
133         -2 inaccuracy
134         -3 slight inaccuracy (and done iterations)
135         +0 looks optimal (might be unbounded - but we will investigate)
136         +1 looks infeasible
137         +3 max iterations
138      */
139     int whileIterating(double & startingTheta, double & endingTheta, double reportIncrement,
140                        const double * changeLower, const double * changeUpper,
141                        const double * changeObjective);
142     /** Computes next theta and says if objective or bounds (0= bounds, 1 objective, -1 none).
143         theta is in theta_.
144         type 1 bounds, 2 objective, 3 both.
145     */
146     int nextTheta(int type, double maxTheta, 
147                   const double * changeLower, const double * changeUpper,
148                   const double * changeObjective);
149     /// Restores bound to original bound
150     void originalBound(int iSequence, double theta, const double * changeLower,
151                     const double * changeUpper);
152     /**
153         Row array has row part of pivot row
154         Column array has column part.
155         This is used in dual ranging
156     */
157     void checkDualRatios(CoinIndexedVector * rowArray,
158                          CoinIndexedVector * columnArray,
159                          double & costIncrease, int & sequenceIncrease, double & alphaIncrease,
160                          double & costDecrease, int & sequenceDecrease, double & alphaDecrease);
161     /**
162         Row array has pivot column
163         This is used in primal ranging
164     */
165     void checkPrimalRatios(CoinIndexedVector * rowArray,
166                            int direction);
167     /// Returns new value of whichOther when whichIn enters basis
168     double primalRanging1(int whichIn, int whichOther);
169
170public:
171     /** Write the basis in MPS format to the specified file.
172     If writeValues true writes values of structurals
173     (and adds VALUES to end of NAME card)
174
175     Row and column names may be null.
176     formatType is
177     <ul>
178       <li> 0 - normal
179       <li> 1 - extra accuracy
180       <li> 2 - IEEE hex (later)
181     </ul>
182
183     Returns non-zero on I/O error
184     */
185     int writeBasis(const char *filename,
186                    bool writeValues = false,
187                    int formatType = 0) const;
188     /// Read a basis from the given filename
189     int readBasis(const char *filename);
190     /** Creates dual of a problem if looks plausible
191         (defaults will always create model)
192         fractionRowRanges is fraction of rows allowed to have ranges
193         fractionColumnRanges is fraction of columns allowed to have ranges
194     */
195     ClpSimplex * dualOfModel(double fractionRowRanges = 1.0, double fractionColumnRanges = 1.0) const;
196     /** Restores solution from dualized problem
197         non-zero return code indicates minor problems
198     */
199     int restoreFromDual(const ClpSimplex * dualProblem);
200     /** Does very cursory presolve.
201         rhs is numberRows, whichRows is 3*numberRows and whichColumns is 2*numberColumns.
202     */
203     ClpSimplex * crunch(double * rhs, int * whichRows, int * whichColumns,
204                         int & nBound, bool moreBounds = false, bool tightenBounds = false);
205     /** After very cursory presolve.
206         rhs is numberRows, whichRows is 3*numberRows and whichColumns is 2*numberColumns.
207     */
208     void afterCrunch(const ClpSimplex & small,
209                      const int * whichRows, const int * whichColumns,
210                      int nBound);
211     /** Returns gub version of model or NULL
212         whichRows has to be numberRows
213         whichColumns has to be numberRows+numberColumns */
214     ClpSimplex * gubVersion(int * whichRows, int * whichColumns,
215                             int neededGub,
216                             int factorizationFrequency=50);
217     /// Sets basis from original
218     void setGubBasis(ClpSimplex &original,const int * whichRows,
219                      const int * whichColumns);
220     /// Restores basis to original
221     void getGubBasis(ClpSimplex &original,const int * whichRows,
222                      const int * whichColumns) const;
223     /// Quick try at cleaning up duals if postsolve gets wrong
224     void cleanupAfterPostsolve();
225     /** Tightens integer bounds - returns number tightened or -1 if infeasible
226     */
227     int tightenIntegerBounds(double * rhsSpace);
228     /** Expands out all possible combinations for a knapsack
229         If buildObj NULL then just computes space needed - returns number elements
230         On entry numberOutput is maximum allowed, on exit it is number needed or
231         -1 (as will be number elements) if maximum exceeded.  numberOutput will have at
232         least space to return values which reconstruct input.
233         Rows returned will be original rows but no entries will be returned for
234         any rows all of whose entries are in knapsack.  So up to user to allow for this.
235         If reConstruct >=0 then returns number of entrie which make up item "reConstruct"
236         in expanded knapsack.  Values in buildRow and buildElement;
237     */
238     int expandKnapsack(int knapsackRow, int & numberOutput,
239                        double * buildObj, CoinBigIndex * buildStart,
240                        int * buildRow, double * buildElement, int reConstruct = -1) const;
241     //@}
242};
243#endif
Note: See TracBrowser for help on using the repository browser.