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

Last change on this file since 1525 was 1525, checked in by mjs, 10 years ago

Formatted .cpp, .hpp, .c, .h files with "astyle -A4 -p". This matches the formatting used in the grand CBC reorganization.

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