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

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

changes for priorities etc

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