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

Last change on this file since 1370 was 1370, checked in by forrest, 10 years ago

add ids

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