source: trunk/Clp/src/ClpNode.hpp @ 1344

Last change on this file since 1344 was 1344, checked in by forrest, 11 years ago

changes to simplex and lots of stuff and start Mumps cholesky

  • Property svn:executable set to *
File size: 8.1 KB
Line 
1// Copyright (C) 2008, International Business Machines
2// Corporation and others.  All Rights Reserved.
3#ifndef ClpNode_H
4#define ClpNode_H
5
6#include "CoinPragma.hpp"
7
8// This implements all stuff for Clp fathom
9/** This contains what is in a Clp "node"
10   
11 */
12
13class ClpFactorization;
14class ClpDualRowSteepest;
15class ClpNodeStuff;
16class ClpNode {
17 
18public:
19  /**@name Useful methods */
20  //@{
21  /** Applies node to model
22      0 - just tree bounds
23      1 - tree bounds and basis etc
24      2 - saved bounds and basis etc
25  */
26  void applyNode(ClpSimplex * model, int doBoundsEtc );
27  /// Choose a new variable
28  void chooseVariable(ClpSimplex * model, ClpNodeStuff * info);
29  /// Fix on reduced costs
30  int fixOnReducedCosts(ClpSimplex * model);
31  /// Create odd arrays
32  void createArrays(ClpSimplex * model);
33  /// Clean up as crunch is different model
34  void cleanUpForCrunch();
35  //@}
36 
37  /**@name Gets and sets */
38  //@{
39  /// Objective value
40  inline double objectiveValue() const
41  { return objectiveValue_;}
42  /// Set objective value
43  inline void setObjectiveValue(double value)
44  { objectiveValue_=value;}
45  /// Primal solution
46  inline const double * primalSolution() const
47  { return primalSolution_;}
48  /// Dual solution
49  inline const double * dualSolution() const
50  { return dualSolution_;}
51  /// Initial value of integer variable
52  inline double branchingValue() const
53  { return branchingValue_;}
54  /// Sum infeasibilities
55  inline double sumInfeasibilities() const
56  { return sumInfeasibilities_;}
57  /// Number infeasibilities
58  inline int numberInfeasibilities() const
59  { return numberInfeasibilities_;}
60  /// Relative depth
61  inline int depth() const
62  { return depth_;}
63  /// Estimated solution value
64  inline double estimatedSolution() const
65  { return estimatedSolution_;}
66  /** Way for integer variable -1 down , +1 up */
67  int way() const;
68  /// Return true if branch exhausted
69  bool fathomed() const;
70  /// Change state of variable i.e. go other way
71  void changeState();
72  /// Sequence number of integer variable (-1 if none)
73  inline int sequence() const
74  { return sequence_;}
75  /// If odd arrays exist
76  inline bool oddArraysExist() const
77  { return lower_!=NULL;}
78  /// Status array
79  inline const unsigned char * statusArray() const 
80  { return status_; }
81  //@}
82 
83  /**@name Constructors, destructor */
84  //@{
85  /** Default constructor. */
86  ClpNode();
87  /// Constructor from model
88  ClpNode (ClpSimplex * model, const ClpNodeStuff * stuff,int depth);
89  /// Does work of constructor (partly so gdb will work)
90  void gutsOfConstructor(ClpSimplex * model, const ClpNodeStuff * stuff,
91                         int arraysExist,int depth);
92  /** Destructor */
93  virtual ~ClpNode();
94  //@}
95 
96  /**@name Copy methods (at present illegal - will abort) */
97  //@{
98  /** The copy constructor. */
99  ClpNode(const ClpNode&);
100  /// Operator =
101  ClpNode& operator=(const ClpNode&);
102  //@}
103 
104protected:
105// For state of branch
106typedef struct {
107  unsigned int firstBranch:1; //  nonzero if first branch on variable is up
108  unsigned int branch:2; //  0 means do first branch next, 1 second, 2 finished
109  unsigned int spare:29;
110} branchState;
111  /**@name Data */
112  //@{
113  /// Initial value of integer variable
114  double branchingValue_;
115  /// Value of objective
116  double objectiveValue_;
117  /// Sum of infeasibilities
118  double sumInfeasibilities_;
119  /// Estimated solution value
120  double estimatedSolution_;
121  /// Factorization
122  ClpFactorization * factorization_;
123  /// Steepest edge weights
124  ClpDualRowSteepest * weights_;
125  /// Status vector
126  unsigned char * status_;
127  /// Primal solution
128  double * primalSolution_;
129  /// Dual solution
130  double * dualSolution_;
131  /// Integer lower bounds (only used in fathomMany)
132  int * lower_;
133  /// Integer upper bounds (only used in fathomMany)
134  int * upper_;
135  /// Pivot variables for factorization
136  int * pivotVariables_;
137  /// Variables fixed by reduced costs (at end of branch) 0x10000000 added if fixed to UB
138  int * fixed_;
139  /// State of branch
140  branchState branchState_;
141  /// Sequence number of integer variable (-1 if none)
142  int sequence_;
143  /// Number of infeasibilities
144  int numberInfeasibilities_;
145  /// Relative depth
146  int depth_;
147  /// Number fixed by reduced cost
148  int numberFixed_;
149  /// Flags - 1 duals scaled
150  int flags_;
151  /// Maximum number fixed by reduced cost
152  int maximumFixed_;
153  /// Maximum rows so far
154  int maximumRows_;
155  /// Maximum columns so far
156  int maximumColumns_;
157  /// Maximum Integers so far
158  int maximumIntegers_;
159  //@}
160};
161class ClpNodeStuff {
162 
163public:
164  /**@name Constructors, destructor */
165  //@{
166  /** Default constructor. */
167  ClpNodeStuff();
168  /** Destructor */
169  virtual ~ClpNodeStuff();
170  //@}
171 
172  /**@name Copy methods (only copies ints etc, nulls arrays) */
173  //@{
174  /** The copy constructor. */
175  ClpNodeStuff(const ClpNodeStuff&);
176  /// Operator =
177  ClpNodeStuff& operator=(const ClpNodeStuff&);
178  /// Zaps stuff 1 - arrays, 2 ints, 3 both
179  void zap(int type);
180  //@}
181 
182 
183  /**@name Fill methods */
184  //@{
185  /** Fill with pseudocosts */
186  void fillPseudoCosts(const double * down, const double * up, 
187                       const int * numberDown, const int * numberUp,
188                       const int * numberDownInfeasible, const int * numberUpInfeasible,
189                       int number);
190  /// Update pseudo costs
191  void update(int way,int sequence,double change,bool feasible);
192  /// Return maximum number of nodes
193  int maximumNodes() const;
194  /// Return maximum space for nodes
195  int maximumSpace() const;
196  //@}
197 
198public:
199  /**@name Data */
200  //@{
201  /// Integer tolerance
202  double integerTolerance_;
203  /// Integer increment
204  double integerIncrement_;
205  /// Down pseudo costs
206  double * downPseudo_;
207  /// Up pseudo costs
208  double * upPseudo_;
209  /// Number of times down
210  int * numberDown_;
211  /// Number of times up
212  int * numberUp_;
213  /// Number of times down infeasible
214  int * numberDownInfeasible_;
215  /// Number of times up infeasible
216  int * numberUpInfeasible_;
217  /// Copy of costs (local)
218  double * saveCosts_;
219  /// Array of ClpNodes
220  ClpNode ** nodeInfo_;
221  /// Large model if crunched
222  ClpSimplex * large_;
223  /// Which rows in large model
224  int * whichRow_;
225  /// Which columns in large model
226  int * whichColumn_;
227  /// Number bounds in large model
228  int nBound_;
229  /// Save of specialOptions_ (local)
230  int saveOptions_;
231  /** Options to pass to solver
232      1 - create external reduced costs for columns
233      2 - create external reduced costs for rows
234      4 - create external row activity (columns always done)
235      Above only done if feasible
236      32 - just create up to nDepth_+1 nodes
237      65536 - set if activated
238  */
239  int solverOptions_;
240  /// Maximum number of nodes to do
241  int maximumNodes_;
242  /// Number deep
243  int nDepth_;
244  /// Number nodes returned (-1 if fathom aborted)
245  int nNodes_;
246  /// Number of nodes explored
247  int numberNodesExplored_;
248  /// Number of iterations
249  int numberIterations_;
250  /// Type of presolve - 0 none, 1 crunch
251  int presolveType_;
252  //@}
253};
254class ClpHashValue {
255 
256public:
257  /**@name Useful methods */
258  //@{
259  /// Return index or -1 if not found
260  int index(double value) const;
261  /// Add value to list and return index
262  int addValue(double value) ;
263  /// Number of different entries
264  inline int numberEntries() const
265  { return numberHash_;}
266  //@}
267
268  /**@name Constructors, destructor */
269  //@{
270  /** Default constructor. */
271  ClpHashValue();
272  /** Useful constructor. */
273  ClpHashValue(ClpSimplex * model);
274  /** Destructor */
275  virtual ~ClpHashValue();
276  //@}
277 
278  /**@name Copy method */
279  //@{
280  /** The copy constructor. */
281  ClpHashValue(const ClpHashValue&);
282  /// =
283  ClpHashValue& operator=(const ClpHashValue&);
284  //@}
285private:
286  /**@name private stuff */
287  //@{
288  /** returns hash */
289  int hash(double value) const;
290  /// Resizes
291  void resize(bool increaseMax);
292  //@}
293   
294protected:
295  /**@name Data members
296     The data members are protected to allow access for derived classes. */
297  //@{
298  /// Data
299  // for hashing
300  typedef struct {
301    double value;
302    int index, next;
303  } CoinHashLink;
304  /// Hash table
305  mutable CoinHashLink *hash_;
306  /// Number of entries in hash table
307  int numberHash_;
308  /// Maximum number of entries in hash table i.e. size
309  int maxHash_;
310  /// Last used space
311  int lastUsed_;
312  //@}
313};
314#endif
Note: See TracBrowser for help on using the repository browser.