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

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

changes for fathoming

  • Property svn:executable set to *
  • Property svn:keywords set to Id
File size: 8.4 KB
Line 
1/* $Id: ClpNode.hpp 1430 2009-09-15 15:51:17Z 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 * priority,
189                       const int * numberDown, const int * numberUp,
190                       const int * numberDownInfeasible, const int * numberUpInfeasible,
191                       int number);
192  /// Update pseudo costs
193  void update(int way,int sequence,double change,bool feasible);
194  /// Return maximum number of nodes
195  int maximumNodes() const;
196  /// Return maximum space for nodes
197  int maximumSpace() const;
198  //@}
199 
200public:
201  /**@name Data */
202  //@{
203  /// Integer tolerance
204  double integerTolerance_;
205  /// Integer increment
206  double integerIncrement_;
207  /// Small chnage in branch
208  double smallChange_;
209  /// Down pseudo costs
210  double * downPseudo_;
211  /// Up pseudo costs
212  double * upPseudo_;
213  /// Priority
214  int * priority_;
215  /// Number of times down
216  int * numberDown_;
217  /// Number of times up
218  int * numberUp_;
219  /// Number of times down infeasible
220  int * numberDownInfeasible_;
221  /// Number of times up infeasible
222  int * numberUpInfeasible_;
223  /// Copy of costs (local)
224  double * saveCosts_;
225  /// Array of ClpNodes
226  ClpNode ** nodeInfo_;
227  /// Large model if crunched
228  ClpSimplex * large_;
229  /// Which rows in large model
230  int * whichRow_;
231  /// Which columns in large model
232  int * whichColumn_;
233  /// Number bounds in large model
234  int nBound_;
235  /// Save of specialOptions_ (local)
236  int saveOptions_;
237  /** Options to pass to solver
238      1 - create external reduced costs for columns
239      2 - create external reduced costs for rows
240      4 - create external row activity (columns always done)
241      Above only done if feasible
242      32 - just create up to nDepth_+1 nodes
243      65536 - set if activated
244  */
245  int solverOptions_;
246  /// Maximum number of nodes to do
247  int maximumNodes_;
248  /// Number before trust from CbcModel
249  int numberBeforeTrust_;
250  /// State of search from CbcModel
251  int stateOfSearch_;
252  /// Number deep
253  int nDepth_;
254  /// Number nodes returned (-1 if fathom aborted)
255  int nNodes_;
256  /// Number of nodes explored
257  int numberNodesExplored_;
258  /// Number of iterations
259  int numberIterations_;
260  /// Type of presolve - 0 none, 1 crunch
261  int presolveType_;
262  //@}
263};
264class ClpHashValue {
265 
266public:
267  /**@name Useful methods */
268  //@{
269  /// Return index or -1 if not found
270  int index(double value) const;
271  /// Add value to list and return index
272  int addValue(double value) ;
273  /// Number of different entries
274  inline int numberEntries() const
275  { return numberHash_;}
276  //@}
277
278  /**@name Constructors, destructor */
279  //@{
280  /** Default constructor. */
281  ClpHashValue();
282  /** Useful constructor. */
283  ClpHashValue(ClpSimplex * model);
284  /** Destructor */
285  virtual ~ClpHashValue();
286  //@}
287 
288  /**@name Copy method */
289  //@{
290  /** The copy constructor. */
291  ClpHashValue(const ClpHashValue&);
292  /// =
293  ClpHashValue& operator=(const ClpHashValue&);
294  //@}
295private:
296  /**@name private stuff */
297  //@{
298  /** returns hash */
299  int hash(double value) const;
300  /// Resizes
301  void resize(bool increaseMax);
302  //@}
303   
304protected:
305  /**@name Data members
306     The data members are protected to allow access for derived classes. */
307  //@{
308  /// Data
309  // for hashing
310  typedef struct {
311    double value;
312    int index, next;
313  } CoinHashLink;
314  /// Hash table
315  mutable CoinHashLink *hash_;
316  /// Number of entries in hash table
317  int numberHash_;
318  /// Maximum number of entries in hash table i.e. size
319  int maxHash_;
320  /// Last used space
321  int lastUsed_;
322  //@}
323};
324#endif
Note: See TracBrowser for help on using the repository browser.