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

Last change on this file since 2384 was 2384, checked in by forrest, 5 months ago

Allow a strategy for initial solve where code analyzes problem and guesses at parameters

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 13.0 KB
Line 
1/* $Id: ClpSimplexOther.hpp 2384 2018-12-24 16:07:36Z 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     int parametricsObj(double startingTheta, double & endingTheta, 
104                        const double * changeObjective);
105    /// Finds best possible pivot
106    double bestPivot(bool justColumns=false);
107  typedef struct {
108    double startingTheta;
109    double endingTheta;
110    double maxTheta;
111    double acceptableMaxTheta; // if this far then within tolerances
112    double * lowerChange; // full array of lower bound changes
113    int * lowerList; // list of lower bound changes
114    double * upperChange; // full array of upper bound changes
115    int * upperList; // list of upper bound changes
116    char * markDone; // mark which ones looked at
117    int * backwardBasic; // from sequence to pivot row
118    int * lowerActive;
119    double * lowerGap;
120    double * lowerCoefficient;
121    int * upperActive;
122    double * upperGap;
123    double * upperCoefficient;
124    int unscaledChangesOffset; 
125    bool firstIteration; // so can update rhs for accuracy
126  } parametricsData;
127
128private:
129     /** Parametrics - inner loop
130         This first attempt is when reportIncrement non zero and may
131         not report endingTheta correctly
132         If it can not reach input endingTheta return code will be 1 for infeasible,
133         2 for unbounded,  otherwise 0.
134         Normal report is just theta and objective but
135         if event handler exists it may do more
136     */
137     int parametricsLoop(parametricsData & paramData, double reportIncrement,
138                         const double * changeLower, const double * changeUpper,
139                         const double * changeObjective, ClpDataSave & data,
140                         bool canTryQuick);
141     int parametricsLoop(parametricsData & paramData,
142                         ClpDataSave & data,bool canSkipFactorization=false);
143     int parametricsObjLoop(parametricsData & paramData,
144                         ClpDataSave & data,bool canSkipFactorization=false);
145     /**  Refactorizes if necessary
146          Checks if finished.  Updates status.
147
148          type - 0 initial so set up save arrays etc
149               - 1 normal -if good update save
150           - 2 restoring from saved
151     */
152     void statusOfProblemInParametrics(int type, ClpDataSave & saveData);
153     void statusOfProblemInParametricsObj(int type, ClpDataSave & saveData);
154     /** This has the flow between re-factorizations
155
156         Reasons to come out:
157         -1 iterations etc
158         -2 inaccuracy
159         -3 slight inaccuracy (and done iterations)
160         +0 looks optimal (might be unbounded - but we will investigate)
161         +1 looks infeasible
162         +3 max iterations
163      */
164     int whileIterating(parametricsData & paramData, double reportIncrement,
165                        const double * changeObjective);
166     /** Computes next theta and says if objective or bounds (0= bounds, 1 objective, -1 none).
167         theta is in theta_.
168         type 1 bounds, 2 objective, 3 both.
169     */
170     int nextTheta(int type, double maxTheta, parametricsData & paramData,
171                   const double * changeObjective);
172     int whileIteratingObj(parametricsData & paramData);
173     int nextThetaObj(double maxTheta, parametricsData & paramData);
174     /// Restores bound to original bound
175     void originalBound(int iSequence, double theta, const double * changeLower,
176                     const double * changeUpper);
177     /// Compute new rowLower_ etc (return negative if infeasible - otherwise largest change)
178     double computeRhsEtc(parametricsData & paramData);
179     /// Redo lower_ from rowLower_ etc
180     void redoInternalArrays();
181     /**
182         Row array has row part of pivot row
183         Column array has column part.
184         This is used in dual ranging
185     */
186     void checkDualRatios(CoinIndexedVector * rowArray,
187                          CoinIndexedVector * columnArray,
188                          double & costIncrease, int & sequenceIncrease, double & alphaIncrease,
189                          double & costDecrease, int & sequenceDecrease, double & alphaDecrease);
190     /**
191         Row array has pivot column
192         This is used in primal ranging
193     */
194     void checkPrimalRatios(CoinIndexedVector * rowArray,
195                            int direction);
196     /// Returns new value of whichOther when whichIn enters basis
197     double primalRanging1(int whichIn, int whichOther);
198
199public:
200     /** Write the basis in MPS format to the specified file.
201     If writeValues true writes values of structurals
202     (and adds VALUES to end of NAME card)
203
204     Row and column names may be null.
205     formatType is
206     <ul>
207       <li> 0 - normal
208       <li> 1 - extra accuracy
209       <li> 2 - IEEE hex (later)
210     </ul>
211
212     Returns non-zero on I/O error
213     */
214     int writeBasis(const char *filename,
215                    bool writeValues = false,
216                    int formatType = 0) const;
217     /// Read a basis from the given filename
218     int readBasis(const char *filename);
219     /** Creates dual of a problem if looks plausible
220         (defaults will always create model)
221         fractionRowRanges is fraction of rows allowed to have ranges
222         fractionColumnRanges is fraction of columns allowed to have ranges
223     */
224     ClpSimplex * dualOfModel(double fractionRowRanges = 1.0, double fractionColumnRanges = 1.0) const;
225     /** Restores solution from dualized problem
226         non-zero return code indicates minor problems
227     */
228     int restoreFromDual(const ClpSimplex * dualProblem,
229                         bool checkAccuracy=false);
230     /** Sets solution in dualized problem
231         non-zero return code indicates minor problems
232     */
233     int setInDual(ClpSimplex * dualProblem);
234     /** Does very cursory presolve.
235         rhs is numberRows, whichRows is 3*numberRows and whichColumns is 2*numberColumns.
236     */
237     ClpSimplex * crunch(double * rhs, int * whichRows, int * whichColumns,
238                         int & nBound, bool moreBounds = false, bool tightenBounds = false);
239     /** After very cursory presolve.
240         rhs is numberRows, whichRows is 3*numberRows and whichColumns is 2*numberColumns.
241     */
242     void afterCrunch(const ClpSimplex & small,
243                      const int * whichRows, const int * whichColumns,
244                      int nBound);
245     /** Returns gub version of model or NULL
246         whichRows has to be numberRows
247         whichColumns has to be numberRows+numberColumns */
248     ClpSimplex * gubVersion(int * whichRows, int * whichColumns,
249                             int neededGub,
250                             int factorizationFrequency=50);
251     /// Sets basis from original
252     void setGubBasis(ClpSimplex &original,const int * whichRows,
253                      const int * whichColumns);
254     /// Restores basis to original
255     void getGubBasis(ClpSimplex &original,const int * whichRows,
256                      const int * whichColumns) const;
257     /// Quick try at cleaning up duals if postsolve gets wrong
258     void cleanupAfterPostsolve();
259     /** Tightens integer bounds - returns number tightened or -1 if infeasible
260     */
261     int tightenIntegerBounds(double * rhsSpace);
262     /** Expands out all possible combinations for a knapsack
263         If buildObj NULL then just computes space needed - returns number elements
264         On entry numberOutput is maximum allowed, on exit it is number needed or
265         -1 (as will be number elements) if maximum exceeded.  numberOutput will have at
266         least space to return values which reconstruct input.
267         Rows returned will be original rows but no entries will be returned for
268         any rows all of whose entries are in knapsack.  So up to user to allow for this.
269         If reConstruct >=0 then returns number of entrie which make up item "reConstruct"
270         in expanded knapsack.  Values in buildRow and buildElement;
271     */
272     int expandKnapsack(int knapsackRow, int & numberOutput,
273                        double * buildObj, CoinBigIndex * buildStart,
274                        int * buildRow, double * buildElement, int reConstruct = -1) const;
275     /// Create a string of commands to guess at best strategy for model
276     /// At present mode is ignored
277     char * guess(int mode) const;
278     //@}
279};
280#endif
Note: See TracBrowser for help on using the repository browser.