1/* $Id: ClpSimplexOther.hpp 1753 2011-06-19 16:27:26Z 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
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 = nullptr, double * valueDecrease = nullptr);
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
92private:
93 /** Parametrics - inner loop
94 This first attempt is when reportIncrement non zero and may
95 not report endingTheta correctly
96 If it can not reach input endingTheta return code will be 1 for infeasible,
97 2 for unbounded, otherwise 0.
98 Normal report is just theta and objective but
99 if event handler exists it may do more
100 */
101 int parametricsLoop(double startingTheta, double & endingTheta, double reportIncrement,
102 const double * changeLower, const double * changeUpper,
103 const double * changeObjective, ClpDataSave & data,
104 bool canTryQuick);
105 /** Refactorizes if necessary
106 Checks if finished. Updates status.
107
108 type - 0 initial so set up save arrays etc
109 - 1 normal -if good update save
110 - 2 restoring from saved
111 */
112 void statusOfProblemInParametrics(int type, ClpDataSave & saveData);
113 /** This has the flow between re-factorizations
114
115 Reasons to come out:
116 -1 iterations etc
117 -2 inaccuracy
118 -3 slight inaccuracy (and done iterations)
119 +0 looks optimal (might be unbounded - but we will investigate)
120 +1 looks infeasible
121 +3 max iterations
122 */
123 int whileIterating(double startingTheta, double & endingTheta, double reportIncrement,
124 const double * changeLower, const double * changeUpper,
125 const double * changeObjective);
126 /** Computes next theta and says if objective or bounds (0= bounds, 1 objective, -1 none).
127 theta is in theta_.
128 type 1 bounds, 2 objective, 3 both.
129 */
130 int nextTheta(int type, double maxTheta, double * primalChange, double * dualChange,
131 const double * changeLower, const double * changeUpper,
132 const double * changeObjective);
133 /**
134 Row array has row part of pivot row
135 Column array has column part.
136 This is used in dual ranging
137 */
138 void checkDualRatios(CoinIndexedVector * rowArray,
139 CoinIndexedVector * columnArray,
140 double & costIncrease, int & sequenceIncrease, double & alphaIncrease,
141 double & costDecrease, int & sequenceDecrease, double & alphaDecrease);
142 /**
143 Row array has pivot column
144 This is used in primal ranging
145 */
146 void checkPrimalRatios(CoinIndexedVector * rowArray,
147 int direction);
148 /// Returns new value of whichOther when whichIn enters basis
149 double primalRanging1(int whichIn, int whichOther);
150
151public:
152 /** Write the basis in MPS format to the specified file.
153 If writeValues true writes values of structurals
154 (and adds VALUES to end of NAME card)
155
156 Row and column names may be null.
157 formatType is
158 <ul>
159 <li> 0 - normal
160 <li> 1 - extra accuracy
161 <li> 2 - IEEE hex (later)
162 </ul>
163
164 Returns non-zero on I/O error
165 */
166 int writeBasis(const char *filename,
167 bool writeValues = false,
168 int formatType = 0) const;
169 /// Read a basis from the given filename
170 int readBasis(const char *filename);
171 /** Creates dual of a problem if looks plausible
172 (defaults will always create model)
173 fractionRowRanges is fraction of rows allowed to have ranges
174 fractionColumnRanges is fraction of columns allowed to have ranges
175 */
176 ClpSimplex * dualOfModel(double fractionRowRanges = 1.0, double fractionColumnRanges = 1.0) const;
177 /** Restores solution from dualized problem
178 non-zero return code indicates minor problems
179 */
180 int restoreFromDual(const ClpSimplex * dualProblem);
181 /** Does very cursory presolve.
182 rhs is numberRows, whichRows is 3*numberRows and whichColumns is 2*numberColumns.
183 */
184 ClpSimplex * crunch(double * rhs, int * whichRows, int * whichColumns,
185 int & nBound, bool moreBounds = false, bool tightenBounds = false);
186 /** After very cursory presolve.
187 rhs is numberRows, whichRows is 3*numberRows and whichColumns is 2*numberColumns.
188 */
189 void afterCrunch(const ClpSimplex & small,
190 const int * whichRows, const int * whichColumns,
191 int nBound);
192 /** Returns gub version of model or NULL
193 whichRows has to be numberRows
194 whichColumns has to be numberRows+numberColumns */
195 ClpSimplex * gubVersion(int * whichRows, int * whichColumns,
196 int neededGub,
197 int factorizationFrequency=50);
198 /// Sets basis from original
199 void setGubBasis(ClpSimplex &original,const int * whichRows,
200 const int * whichColumns);
201 /// Restores basis to original
202 void getGubBasis(ClpSimplex &original,const int * whichRows,
203 const int * whichColumns) const;
204 /// Quick try at cleaning up duals if postsolve gets wrong
205 void cleanupAfterPostsolve();
206 /** Tightens integer bounds - returns number tightened or -1 if infeasible
207 */
208 int tightenIntegerBounds(double * rhsSpace);
209 /** Expands out all possible combinations for a knapsack
210 If buildObj NULL then just computes space needed - returns number elements
211 On entry numberOutput is maximum allowed, on exit it is number needed or
212 -1 (as will be number elements) if maximum exceeded. numberOutput will have at
213 least space to return values which reconstruct input.
214 Rows returned will be original rows but no entries will be returned for
215 any rows all of whose entries are in knapsack. So up to user to allow for this.
216 If reConstruct >=0 then returns number of entrie which make up item "reConstruct"
217 in expanded knapsack. Values in buildRow and buildElement;
218 */
219 int expandKnapsack(int knapsackRow, int & numberOutput,
220 double * buildObj, CoinBigIndex * buildStart,
221 int * buildRow, double * buildElement, int reConstruct = -1) const;
222 //@}
223};
224#endif
225