1 | // Copyright (C) 2008, International Business Machines |
---|
2 | // Corporation and others. All Rights Reserved. |
---|
3 | |
---|
4 | #include "CoinPragma.hpp" |
---|
5 | #include "ClpSimplex.hpp" |
---|
6 | #include "ClpNode.hpp" |
---|
7 | #include "ClpFactorization.hpp" |
---|
8 | #include "ClpDualRowSteepest.hpp" |
---|
9 | |
---|
10 | //############################################################################# |
---|
11 | // Constructors / Destructor / Assignment |
---|
12 | //############################################################################# |
---|
13 | |
---|
14 | //------------------------------------------------------------------- |
---|
15 | // Default Constructor |
---|
16 | //------------------------------------------------------------------- |
---|
17 | ClpNode::ClpNode () : |
---|
18 | branchingValue_(0.5), |
---|
19 | factorization_(NULL), |
---|
20 | weights_(NULL), |
---|
21 | status_(NULL), |
---|
22 | primalSolution_(NULL), |
---|
23 | dualSolution_(NULL), |
---|
24 | pivotVariables_(NULL), |
---|
25 | fixed_(NULL), |
---|
26 | sequence_(1), |
---|
27 | numberFixed_(0) |
---|
28 | { |
---|
29 | branchState_.firstBranch=0; |
---|
30 | branchState_.branch=0; |
---|
31 | } |
---|
32 | //------------------------------------------------------------------- |
---|
33 | // Useful Constructor from model |
---|
34 | //------------------------------------------------------------------- |
---|
35 | ClpNode::ClpNode (const ClpSimplex * model, const ClpNodeStuff * stuff) : |
---|
36 | branchingValue_(0.5), |
---|
37 | factorization_(NULL), |
---|
38 | weights_(NULL), |
---|
39 | status_(NULL), |
---|
40 | primalSolution_(NULL), |
---|
41 | dualSolution_(NULL), |
---|
42 | pivotVariables_(NULL), |
---|
43 | fixed_(NULL), |
---|
44 | sequence_(1), |
---|
45 | numberFixed_(0) |
---|
46 | { |
---|
47 | branchState_.firstBranch=0; |
---|
48 | branchState_.branch=0; |
---|
49 | gutsOfConstructor(model,stuff); |
---|
50 | } |
---|
51 | |
---|
52 | //------------------------------------------------------------------- |
---|
53 | // Most of work of constructor from model |
---|
54 | //------------------------------------------------------------------- |
---|
55 | void |
---|
56 | ClpNode::gutsOfConstructor (const ClpSimplex * model, const ClpNodeStuff * stuff) |
---|
57 | { |
---|
58 | // save stuff |
---|
59 | factorization_ = new ClpFactorization(*model->factorization()); |
---|
60 | int numberRows = model->numberRows(); |
---|
61 | int numberColumns = model->numberColumns(); |
---|
62 | int numberTotal = numberRows+numberColumns; |
---|
63 | status_ = CoinCopyOfArray(model->statusArray(),numberTotal); |
---|
64 | primalSolution_ = CoinCopyOfArray(model->solutionRegion(),numberTotal); |
---|
65 | dualSolution_ = CoinCopyOfArray(model->djRegion(),numberTotal); //? has duals as well? |
---|
66 | pivotVariables_ = CoinCopyOfArray(model->pivotVariable(),numberRows); |
---|
67 | ClpDualRowSteepest* pivot = |
---|
68 | dynamic_cast< ClpDualRowSteepest*>(model->dualRowPivot()); |
---|
69 | if (pivot) |
---|
70 | weights_ = new ClpDualRowSteepest(*pivot); |
---|
71 | const double * lower = model->columnLower(); |
---|
72 | const double * upper = model->columnUpper(); |
---|
73 | const double * solution = model->primalColumnSolution(); |
---|
74 | const char * integerType = model->integerInformation(); |
---|
75 | int iColumn; |
---|
76 | sequence_=-1; |
---|
77 | double integerTolerance = stuff->integerTolerance_; |
---|
78 | double mostAway=integerTolerance; |
---|
79 | int numberAway=0; |
---|
80 | for (iColumn=0;iColumn<numberColumns;iColumn++) { |
---|
81 | if (integerType[iColumn]) { |
---|
82 | double value = solution[iColumn]; |
---|
83 | value = max(value,(double) lower[iColumn]); |
---|
84 | value = min(value,(double) upper[iColumn]); |
---|
85 | double nearest = floor(value+0.5); |
---|
86 | if (fabs(value-nearest)>integerTolerance) |
---|
87 | numberAway++; |
---|
88 | if (fabs(value-nearest)>mostAway) { |
---|
89 | mostAway=fabs(value-nearest); |
---|
90 | sequence_=iColumn; |
---|
91 | branchingValue_=value; |
---|
92 | branchState_.branch=0; |
---|
93 | if (value<=nearest) |
---|
94 | branchState_.firstBranch=1; // up |
---|
95 | else |
---|
96 | branchState_.firstBranch=0; // down |
---|
97 | } |
---|
98 | } |
---|
99 | } |
---|
100 | } |
---|
101 | |
---|
102 | //------------------------------------------------------------------- |
---|
103 | // Copy constructor |
---|
104 | //------------------------------------------------------------------- |
---|
105 | ClpNode::ClpNode (const ClpNode & source) |
---|
106 | { |
---|
107 | printf("ClpNode copy not implemented\n"); |
---|
108 | abort(); |
---|
109 | } |
---|
110 | |
---|
111 | //------------------------------------------------------------------- |
---|
112 | // Destructor |
---|
113 | //------------------------------------------------------------------- |
---|
114 | ClpNode::~ClpNode () |
---|
115 | { |
---|
116 | delete factorization_; |
---|
117 | delete weights_; |
---|
118 | delete [] status_; |
---|
119 | delete [] primalSolution_; |
---|
120 | delete [] dualSolution_; |
---|
121 | delete [] pivotVariables_; |
---|
122 | delete [] fixed_; |
---|
123 | } |
---|
124 | |
---|
125 | //---------------------------------------------------------------- |
---|
126 | // Assignment operator |
---|
127 | //------------------------------------------------------------------- |
---|
128 | ClpNode & |
---|
129 | ClpNode::operator=(const ClpNode& rhs) |
---|
130 | { |
---|
131 | if (this != &rhs) { |
---|
132 | printf("ClpNode = not implemented\n"); |
---|
133 | abort(); |
---|
134 | } |
---|
135 | return *this; |
---|
136 | } |
---|
137 | // Applies node to model |
---|
138 | void |
---|
139 | ClpNode::applyNode(ClpSimplex * model, bool justBounds ) |
---|
140 | { |
---|
141 | // current bound |
---|
142 | int way=branchState_.firstBranch; |
---|
143 | if (branchState_.branch>0) |
---|
144 | way=1-way; |
---|
145 | if (!way) { |
---|
146 | // This should also do underlying internal bound |
---|
147 | model->setColumnUpper(sequence_,floor(branchingValue_)); |
---|
148 | } else { |
---|
149 | // This should also do underlying internal bound |
---|
150 | model->setColumnLower(sequence_,ceil(branchingValue_)); |
---|
151 | } |
---|
152 | const double * lower = model->columnLower(); |
---|
153 | const double * upper = model->columnUpper(); |
---|
154 | // apply dj fixings |
---|
155 | for (int i=0;i<numberFixed_;i++) { |
---|
156 | int iColumn = fixed_[i]; |
---|
157 | if ((iColumn&0x10000000)!=0) { |
---|
158 | iColumn &= 0xfffffff; |
---|
159 | model->setColumnLower(iColumn,upper[iColumn]); |
---|
160 | } else { |
---|
161 | model->setColumnUpper(iColumn,lower[iColumn]); |
---|
162 | } |
---|
163 | } |
---|
164 | if (!justBounds) { |
---|
165 | model->setFactorization(*factorization_); |
---|
166 | ClpDualRowSteepest* pivot = |
---|
167 | dynamic_cast< ClpDualRowSteepest*>(model->dualRowPivot()); |
---|
168 | if (pivot) |
---|
169 | *pivot=*weights_; // may be better to copy stuff |
---|
170 | int numberRows = model->numberRows(); |
---|
171 | int numberColumns = model->numberColumns(); |
---|
172 | int numberTotal = numberRows+numberColumns; |
---|
173 | CoinMemcpyN(status_,numberTotal,model->statusArray()); |
---|
174 | CoinMemcpyN(primalSolution_,numberTotal,model->solutionRegion()); |
---|
175 | CoinMemcpyN(dualSolution_,numberTotal,model->djRegion()); //? has duals as well? |
---|
176 | CoinMemcpyN(pivotVariables_,numberRows,model->pivotVariable()); |
---|
177 | } |
---|
178 | } |
---|
179 | // Fix on reduced costs |
---|
180 | int |
---|
181 | ClpNode::fixOnReducedCosts(ClpSimplex * model) |
---|
182 | { |
---|
183 | return 0; |
---|
184 | } |
---|
185 | /* Way for integer variable -1 down , +1 up */ |
---|
186 | int |
---|
187 | ClpNode::way() const |
---|
188 | { |
---|
189 | int way=branchState_.firstBranch; |
---|
190 | if (branchState_.branch>0) |
---|
191 | way=1-way; |
---|
192 | return way ? -1 : +1; |
---|
193 | } |
---|
194 | // Return true if branch exhausted |
---|
195 | bool |
---|
196 | ClpNode::fathomed() const |
---|
197 | { |
---|
198 | return branchState_.branch>=1 |
---|
199 | ; |
---|
200 | } |
---|
201 | // Change state of variable i.e. go other way |
---|
202 | void |
---|
203 | ClpNode::changeState() |
---|
204 | { |
---|
205 | branchState_.branch++; |
---|
206 | assert (branchState_.branch<=2); |
---|
207 | } |
---|
208 | //############################################################################# |
---|
209 | // Constructors / Destructor / Assignment |
---|
210 | //############################################################################# |
---|
211 | |
---|
212 | //------------------------------------------------------------------- |
---|
213 | // Default Constructor |
---|
214 | //------------------------------------------------------------------- |
---|
215 | ClpNodeStuff::ClpNodeStuff () : |
---|
216 | integerTolerance_(1.0e-7), |
---|
217 | integerIncrement_(1.0e-8) |
---|
218 | { |
---|
219 | |
---|
220 | } |
---|
221 | |
---|
222 | //------------------------------------------------------------------- |
---|
223 | // Copy constructor |
---|
224 | //------------------------------------------------------------------- |
---|
225 | ClpNodeStuff::ClpNodeStuff (const ClpNodeStuff & source) |
---|
226 | { |
---|
227 | printf("ClpNodeStuff copy not implemented\n"); |
---|
228 | abort(); |
---|
229 | } |
---|
230 | //---------------------------------------------------------------- |
---|
231 | // Assignment operator |
---|
232 | //------------------------------------------------------------------- |
---|
233 | ClpNodeStuff & |
---|
234 | ClpNodeStuff::operator=(const ClpNodeStuff& rhs) |
---|
235 | { |
---|
236 | if (this != &rhs) { |
---|
237 | printf("ClpNodeStuff = not implemented\n"); |
---|
238 | abort(); |
---|
239 | } |
---|
240 | return *this; |
---|
241 | } |
---|
242 | |
---|
243 | //------------------------------------------------------------------- |
---|
244 | // Destructor |
---|
245 | //------------------------------------------------------------------- |
---|
246 | ClpNodeStuff::~ClpNodeStuff () |
---|
247 | { |
---|
248 | } |
---|