source: branches/sandbox/Cbc/src/CbcNWay.cpp @ 1293

Last change on this file since 1293 was 1293, checked in by EdwinStraver, 10 years ago
File size: 7.9 KB
Line 
1// Edwin 11/9/2009-- carved out of CbcBranchActual
2
3#if defined(_MSC_VER)
4// Turn off compiler warning about long names
5#  pragma warning(disable:4786)
6#endif
7#include <cassert>
8#include <cstdlib>
9#include <cmath>
10#include <cfloat>
11//#define CBC_DEBUG
12
13#include "CoinTypes.hpp"
14#include "OsiSolverInterface.hpp"
15#include "OsiSolverBranch.hpp"
16#include "CbcModel.hpp"
17#include "CbcMessage.hpp"
18#include "CbcNWay.hpp"
19#include "CbcBranchActual.hpp"
20#include "CoinSort.hpp"
21#include "CoinError.hpp"
22
23//##############################################################################
24
25// Default Constructor
26CbcNWay::CbcNWay ()
27        : CbcObject(),
28        numberMembers_(0),
29        members_(NULL),
30        consequence_(NULL)
31{
32}
33
34// Useful constructor (which are integer indices)
35CbcNWay::CbcNWay (CbcModel * model, int numberMembers,
36                  const int * which, int identifier)
37        : CbcObject(model)
38{
39    id_ = identifier;
40    numberMembers_ = numberMembers;
41    if (numberMembers_) {
42        members_ = new int[numberMembers_];
43        memcpy(members_, which, numberMembers_*sizeof(int));
44    } else {
45        members_ = NULL;
46    }
47    consequence_ = NULL;
48}
49
50// Copy constructor
51CbcNWay::CbcNWay ( const CbcNWay & rhs)
52        : CbcObject(rhs)
53{
54    numberMembers_ = rhs.numberMembers_;
55    consequence_ = NULL;
56    if (numberMembers_) {
57        members_ = new int[numberMembers_];
58        memcpy(members_, rhs.members_, numberMembers_*sizeof(int));
59        if (rhs.consequence_) {
60            consequence_ = new CbcConsequence * [numberMembers_];
61            for (int i = 0; i < numberMembers_; i++) {
62                if (rhs.consequence_[i])
63                    consequence_[i] = rhs.consequence_[i]->clone();
64                else
65                    consequence_[i] = NULL;
66            }
67        }
68    } else {
69        members_ = NULL;
70    }
71}
72
73// Clone
74CbcObject *
75CbcNWay::clone() const
76{
77    return new CbcNWay(*this);
78}
79
80// Assignment operator
81CbcNWay &
82CbcNWay::operator=( const CbcNWay & rhs)
83{
84    if (this != &rhs) {
85        CbcObject::operator=(rhs);
86        delete [] members_;
87        numberMembers_ = rhs.numberMembers_;
88        if (consequence_) {
89            for (int i = 0; i < numberMembers_; i++)
90                delete consequence_[i];
91            delete [] consequence_;
92            consequence_ = NULL;
93        }
94        if (numberMembers_) {
95            members_ = new int[numberMembers_];
96            memcpy(members_, rhs.members_, numberMembers_*sizeof(int));
97        } else {
98            members_ = NULL;
99        }
100        if (rhs.consequence_) {
101            consequence_ = new CbcConsequence * [numberMembers_];
102            for (int i = 0; i < numberMembers_; i++) {
103                if (rhs.consequence_[i])
104                    consequence_[i] = rhs.consequence_[i]->clone();
105                else
106                    consequence_[i] = NULL;
107            }
108        }
109    }
110    return *this;
111}
112
113// Destructor
114CbcNWay::~CbcNWay ()
115{
116    delete [] members_;
117    if (consequence_) {
118        for (int i = 0; i < numberMembers_; i++)
119            delete consequence_[i];
120        delete [] consequence_;
121    }
122}
123// Set up a consequence for a single member
124void
125CbcNWay::setConsequence(int iColumn, const CbcConsequence & consequence)
126{
127    if (!consequence_) {
128        consequence_ = new CbcConsequence * [numberMembers_];
129        for (int i = 0; i < numberMembers_; i++)
130            consequence_[i] = NULL;
131    }
132    for (int i = 0; i < numberMembers_; i++) {
133        if (members_[i] == iColumn) {
134            consequence_[i] = consequence.clone();
135            break;
136        }
137    }
138}
139
140// Applies a consequence for a single member
141void
142CbcNWay::applyConsequence(int iSequence, int state) const
143{
144    assert (state == -9999 || state == 9999);
145    if (consequence_) {
146        CbcConsequence * consequence = consequence_[iSequence];
147        if (consequence)
148            consequence->applyToSolver(model_->solver(), state);
149    }
150}
151double
152CbcNWay::infeasibility(const OsiBranchingInformation * /*info*/,
153                       int &preferredWay) const
154{
155    int numberUnsatis = 0;
156    int j;
157    OsiSolverInterface * solver = model_->solver();
158    const double * solution = model_->testSolution();
159    const double * lower = solver->getColLower();
160    const double * upper = solver->getColUpper();
161    double largestValue = 0.0;
162
163    double integerTolerance =
164        model_->getDblParam(CbcModel::CbcIntegerTolerance);
165
166    for (j = 0; j < numberMembers_; j++) {
167        int iColumn = members_[j];
168        double value = solution[iColumn];
169        value = CoinMax(value, lower[iColumn]);
170        value = CoinMin(value, upper[iColumn]);
171        double distance = CoinMin(value - lower[iColumn], upper[iColumn] - value);
172        if (distance > integerTolerance) {
173            numberUnsatis++;
174            largestValue = CoinMax(distance, largestValue);
175        }
176    }
177    preferredWay = 1;
178    if (numberUnsatis) {
179        return largestValue;
180    } else {
181        return 0.0; // satisfied
182    }
183}
184
185// This looks at solution and sets bounds to contain solution
186void
187CbcNWay::feasibleRegion()
188{
189    int j;
190    OsiSolverInterface * solver = model_->solver();
191    const double * solution = model_->testSolution();
192    const double * lower = solver->getColLower();
193    const double * upper = solver->getColUpper();
194    double integerTolerance =
195        model_->getDblParam(CbcModel::CbcIntegerTolerance);
196    for (j = 0; j < numberMembers_; j++) {
197        int iColumn = members_[j];
198        double value = solution[iColumn];
199        value = CoinMax(value, lower[iColumn]);
200        value = CoinMin(value, upper[iColumn]);
201        if (value >= upper[iColumn] - integerTolerance) {
202            solver->setColLower(iColumn, upper[iColumn]);
203        } else {
204            assert (value <= lower[iColumn] + integerTolerance);
205            solver->setColUpper(iColumn, lower[iColumn]);
206        }
207    }
208}
209// Redoes data when sequence numbers change
210void
211CbcNWay::redoSequenceEtc(CbcModel * model, int numberColumns, const int * originalColumns)
212{
213    model_ = model;
214    int n2 = 0;
215    for (int j = 0; j < numberMembers_; j++) {
216        int iColumn = members_[j];
217        int i;
218        for (i = 0; i < numberColumns; i++) {
219            if (originalColumns[i] == iColumn)
220                break;
221        }
222        if (i < numberColumns) {
223            members_[n2] = i;
224            consequence_[n2++] = consequence_[j];
225        } else {
226            delete consequence_[j];
227        }
228    }
229    if (n2 < numberMembers_) {
230        printf("** NWay number of members reduced from %d to %d!\n", numberMembers_, n2);
231        numberMembers_ = n2;
232    }
233}
234CbcBranchingObject *
235CbcNWay::createCbcBranch(OsiSolverInterface * solver, const OsiBranchingInformation * /*info*/, int /*way*/)
236{
237    int numberFree = 0;
238    int j;
239
240    //OsiSolverInterface * solver = model_->solver();
241    const double * solution = model_->testSolution();
242    const double * lower = solver->getColLower();
243    const double * upper = solver->getColUpper();
244    int * list = new int[numberMembers_];
245    double * sort = new double[numberMembers_];
246
247    for (j = 0; j < numberMembers_; j++) {
248        int iColumn = members_[j];
249        double value = solution[iColumn];
250        value = CoinMax(value, lower[iColumn]);
251        value = CoinMin(value, upper[iColumn]);
252        if (upper[iColumn] > lower[iColumn]) {
253            double distance = upper[iColumn] - value;
254            list[numberFree] = j;
255            sort[numberFree++] = distance;
256        }
257    }
258    assert (numberFree);
259    // sort
260    CoinSort_2(sort, sort + numberFree, list);
261    // create object
262    CbcBranchingObject * branch;
263    branch = new CbcNWayBranchingObject(model_, this, numberFree, list);
264    branch->setOriginalObject(this);
265    delete [] list;
266    delete [] sort;
267    return branch;
268}
Note: See TracBrowser for help on using the repository browser.