- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

KnapTreeNode.h
Go to the documentation of this file.
1 /*===========================================================================*
2 * This file is part of the Abstract Library for Parallel Search (ALPS). *
3 * *
4 * ALPS is distributed under the Eclipse Public License as part of the *
5 * COIN-OR repository (http://www.coin-or.org). *
6 * *
7 * Authors: Yan Xu, Lehigh University *
8 * Ted Ralphs, Lehigh University *
9 * Laszlo Ladanyi, IBM T.J. Watson Research Center *
10 * Matthew Saltzman, Clemson University *
11 * *
12 * *
13 * Copyright (C) 2001-2013, Lehigh University, Yan Xu, and Ted Ralphs. *
14 *===========================================================================*/
15
16 #ifndef KnapTreeNode_h_
17 #define KnapTreeNode_h_
18
19 #include <utility>
20
21 #include "AlpsTreeNode.h"
22
23 #include "KnapModel.h"
24
25
26 //#############################################################################
27
28 enum KnapVarStatus {
29 KnapVarFree,
30 KnapVarFixedToOne,
31 KnapVarFixedToZero
32 };
33
34 //#############################################################################
35
36 class KnapNodeDesc : public AlpsNodeDesc {
37
38 private:
39
40 /* Here, we need to fill in what the node description will look
41 like. For now, we will not use differencing -- just explicitly
42 represent it. Probably this means that we will just store the
43 original problem data and a list of the variables that have been
44 fixed. */
45
48 // In the constructor, we should allocate this array to be the right
49 // length.
50 KnapVarStatus* varStatus_;
51
53 int usedCapacity_;
54 int usedValue_;
55
56 public:
57 #if 0
58 KnapNodeDesc()
59 :
60 usedCapacity_(0),
61 usedValue_(0)
62 {
63 const int n =
64 dynamic_cast<const KnapModel*>(model_)->getNumItems();
65 varStatus_ = new KnapVarStatus[n];
66 std::fill(varStatus_, varStatus_ + n, KnapVarFree);
67 }
68 #endif
69
70 KnapNodeDesc(KnapModel* m)
71 :
72 AlpsNodeDesc(m),
73 usedCapacity_(0),
74 usedValue_(0)
75 {
76 //model_ = m; // data member declared in Alps
77 const int n = dynamic_cast<KnapModel* >(model_)->getNumItems();
78 varStatus_ = new KnapVarStatus[n];
79 std::fill(varStatus_, varStatus_ + n, KnapVarFree);
80 }
81
82 KnapNodeDesc(KnapModel* m, KnapVarStatus *& st, int cap, int val)
83 :
84 // model_(m), varStatus_(0), usedCapacity_(cap), usedValue_(val) {
85 AlpsNodeDesc(m),
86 varStatus_(0),
87 usedCapacity_(cap),
88 usedValue_(val)
89 {
90 // model_ = m;
91 std::swap(varStatus_, st);
92 }
93
94 virtual ~KnapNodeDesc() { delete[] varStatus_; }
95
96 // inline KnapModel* getModel() { return model_; }
97 // inline const KnapModel* getModel() const { return model_; }// move Alps
98
99 inline void setVarStatus(const int i, const KnapVarStatus status)
100 { varStatus_[i] = status; }
101
102 inline KnapVarStatus getVarStatus(const int i)
103 { return varStatus_[i]; }
104
105 inline const KnapVarStatus* getVarStati() const
106 { return varStatus_; }
107
108 inline int getUsedCapacity() const { return usedCapacity_; }
109 inline int getUsedValue() const { return usedValue_; }
110 };
111
112 //#############################################################################
113
114 class KnapTreeNode : public AlpsTreeNode {
115 private:
116 // NO: default constructor, copy constructor, assignment operator
117 KnapTreeNode(const KnapTreeNode&);
118 KnapTreeNode& operator=(const KnapTreeNode&);
119
120 private:
122 int branchedOn_;
123
124 public:
125 KnapTreeNode() : branchedOn_(-1) {
126 desc_ = new KnapNodeDesc(dynamic_cast<KnapModel* >
127 (getKnowledgeBroker()->getModel()));
128 }
129
130 KnapTreeNode(KnapModel* model) : branchedOn_(-1) {
131 desc_ = new KnapNodeDesc(model);
132 }
133
134 KnapTreeNode(KnapNodeDesc*& desc) : branchedOn_(-1) {
135 desc_ = desc;
136 desc = 0;
137 // At the time of registering node, that node hasn't set broker
138 // desc_->setModel(getKnowledgeBroker()->getDataPool()->getModel());
139 }
140
141 ~KnapTreeNode() { }
142
143 void setBranchOn(int b) { branchedOn_ = b; }
144
145 virtual AlpsTreeNode* createNewTreeNode(AlpsNodeDesc*& desc) const;
146
147 virtual int process(bool isRoot = false, bool rampUp = false);
148
149 virtual std::vector< CoinTriple<AlpsNodeDesc*, AlpsNodeStatus, double> >
150 branch();
151
152 // We only need these for parallel execution I think...
153 virtual AlpsEncoded* encode() const;
154
155 virtual AlpsKnowledge* decode(AlpsEncoded&) const;
156 };
157
158 #endif
KnapTreeNode::operator=
KnapTreeNode & operator=(const KnapTreeNode &)
KnapTreeNode::branchedOn_
int branchedOn_
The index of the branching variable.
Definition: KnapTreeNode.h:122
KnapTreeNode::~KnapTreeNode
~KnapTreeNode()
Definition: KnapTreeNode.h:141
KnapTreeNode::KnapTreeNode
KnapTreeNode()
Definition: KnapTreeNode.h:125
KnapNodeDesc::KnapNodeDesc
KnapNodeDesc(KnapModel *m)
Definition: KnapTreeNode.h:70
KnapNodeDesc::~KnapNodeDesc
virtual ~KnapNodeDesc()
Definition: KnapTreeNode.h:94
KnapTreeNode::KnapTreeNode
KnapTreeNode(KnapModel *model)
Definition: KnapTreeNode.h:130
AlpsTreeNode::getKnowledgeBroker
AlpsKnowledgeBroker * getKnowledgeBroker() const
Functions to access/set the knwoledge broker.
Definition: AlpsTreeNode.h:160
KnapNodeDesc::getUsedCapacity
int getUsedCapacity() const
Definition: KnapTreeNode.h:108
KnapTreeNode::setBranchOn
void setBranchOn(int b)
Definition: KnapTreeNode.h:143
KnapNodeDesc
Definition: KnapTreeNode.h:36
AlpsEncoded
This data structure is to contain the packed form of an encodable knowledge.
Definition: AlpsEncoded.h:25
KnapNodeDesc::varStatus_
KnapVarStatus * varStatus_
This array keeps track of which variables have been fixed by branching and which are still free...
Definition: KnapTreeNode.h:50
KnapNodeDesc::usedValue_
int usedValue_
Definition: KnapTreeNode.h:54
KnapNodeDesc::getUsedValue
int getUsedValue() const
Definition: KnapTreeNode.h:109
KnapVarStatus
KnapVarStatus
Definition: KnapTreeNode.h:28
AlpsTreeNode
This class holds one node of the search tree.
Definition: AlpsTreeNode.h:50
KnapNodeDesc::getVarStatus
KnapVarStatus getVarStatus(const int i)
Definition: KnapTreeNode.h:102
KnapNodeDesc::getVarStati
const KnapVarStatus * getVarStati() const
Definition: KnapTreeNode.h:105
KnapNodeDesc::usedCapacity_
int usedCapacity_
The total size of the items fixed to be put into the knapsack.
Definition: KnapTreeNode.h:53
KnapTreeNode::process
virtual int process(bool isRoot=false, bool rampUp=false)
KnapNodeDesc::setVarStatus
void setVarStatus(const int i, const KnapVarStatus status)
Definition: KnapTreeNode.h:99
KnapTreeNode::KnapTreeNode
KnapTreeNode(KnapNodeDesc *&desc)
Definition: KnapTreeNode.h:134
KnapNodeDesc::KnapNodeDesc
KnapNodeDesc(KnapModel *m, KnapVarStatus *&st, int cap, int val)
Definition: KnapTreeNode.h:82
KnapModel.h
AlpsKnowledge
The abstract base class of any user-defined class that Alps has to know about in order to encode/deco...
Definition: AlpsKnowledge.h:51
AlpsNodeDesc::model_
AlpsModel * model_
A pointer to model.
Definition: AlpsNodeDesc.h:41
AlpsTreeNode.h
KnapTreeNode::createNewTreeNode
virtual AlpsTreeNode * createNewTreeNode(AlpsNodeDesc *&desc) const
The purpose of this function is be able to create the children of a node after branching.
KnapTreeNode
Definition: KnapTreeNode.h:114
KnapTreeNode::decode
virtual AlpsKnowledge * decode(AlpsEncoded &) const
This method should decode and return a pointer to a brand new object, i.e., the method must create a ...
KnapVarFree
Definition: KnapTreeNode.h:29
KnapVarFixedToZero
Definition: KnapTreeNode.h:31
KnapVarFixedToOne
Definition: KnapTreeNode.h:30
KnapTreeNode::encode
virtual AlpsEncoded * encode() const
This method should encode the content of the object and return a pointer to the encoded form...
AlpsNodeDesc
A class to refer to the description of a search tree node.
Definition: AlpsNodeDesc.h:35
KnapTreeNode::branch
virtual std::vector< CoinTriple< AlpsNodeDesc *, AlpsNodeStatus, double > > branch()
AlpsTreeNode::desc_
AlpsNodeDesc * desc_
The actual description of the tree node.
Definition: AlpsTreeNode.h:95
KnapModel
Definition: KnapModel.h:26