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

Last change on this file since 2470 was 2385, checked in by unxusr, 9 months ago

formatting

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