source: stable/2.5/Cbc/src/CbcNWay.cpp @ 1510

Last change on this file since 1510 was 1432, checked in by bjarni, 10 years ago

Added extra return at end of each source file where needed, to remove possible linefeed conflicts (NightlyBuild? errors)

File size: 12.1 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}
269
270// Default Constructor
271CbcNWayBranchingObject::CbcNWayBranchingObject()
272        : CbcBranchingObject()
273{
274    order_ = NULL;
275    object_ = NULL;
276    numberInSet_ = 0;
277    way_ = 0;
278}
279
280// Useful constructor
281CbcNWayBranchingObject::CbcNWayBranchingObject (CbcModel * model,
282        const CbcNWay * nway,
283        int number, const int * order)
284        : CbcBranchingObject(model, nway->id(), -1, 0.5)
285{
286    numberBranches_ = number;
287    order_ = new int [number];
288    object_ = nway;
289    numberInSet_ = number;
290    memcpy(order_, order, number*sizeof(int));
291}
292
293// Copy constructor
294CbcNWayBranchingObject::CbcNWayBranchingObject ( const CbcNWayBranchingObject & rhs) : CbcBranchingObject(rhs)
295{
296    numberInSet_ = rhs.numberInSet_;
297    object_ = rhs.object_;
298    if (numberInSet_) {
299        order_ = new int [numberInSet_];
300        memcpy(order_, rhs.order_, numberInSet_*sizeof(int));
301    } else {
302        order_ = NULL;
303    }
304}
305
306// Assignment operator
307CbcNWayBranchingObject &
308CbcNWayBranchingObject::operator=( const CbcNWayBranchingObject & rhs)
309{
310    if (this != &rhs) {
311        CbcBranchingObject::operator=(rhs);
312        object_ = rhs.object_;
313        delete [] order_;
314        numberInSet_ = rhs.numberInSet_;
315        if (numberInSet_) {
316            order_ = new int [numberInSet_];
317            memcpy(order_, rhs.order_, numberInSet_*sizeof(int));
318        } else {
319            order_ = NULL;
320        }
321    }
322    return *this;
323}
324CbcBranchingObject *
325CbcNWayBranchingObject::clone() const
326{
327    return (new CbcNWayBranchingObject(*this));
328}
329
330
331// Destructor
332CbcNWayBranchingObject::~CbcNWayBranchingObject ()
333{
334    delete [] order_;
335}
336double
337CbcNWayBranchingObject::branch()
338{
339    int which = branchIndex_;
340    branchIndex_++;
341    assert (numberBranchesLeft() >= 0);
342    if (which == 0) {
343        // first branch so way_ may mean something
344        assert (way_ == -1 || way_ == 1);
345        if (way_ == -1)
346            which++;
347    } else if (which == 1) {
348        // second branch so way_ may mean something
349        assert (way_ == -1 || way_ == 1);
350        if (way_ == -1)
351            which--;
352        // switch way off
353        way_ = 0;
354    }
355    const double * lower = model_->solver()->getColLower();
356    const double * upper = model_->solver()->getColUpper();
357    const int * members = object_->members();
358    for (int j = 0; j < numberInSet_; j++) {
359        int iSequence = order_[j];
360        int iColumn = members[iSequence];
361        if (j != which) {
362            model_->solver()->setColUpper(iColumn, lower[iColumn]);
363            //model_->solver()->setColLower(iColumn,lower[iColumn]);
364            assert (lower[iColumn] > -1.0e20);
365            // apply any consequences
366            object_->applyConsequence(iSequence, -9999);
367        } else {
368            model_->solver()->setColLower(iColumn, upper[iColumn]);
369            //model_->solver()->setColUpper(iColumn,upper[iColumn]);
370#ifdef FULL_PRINT
371            printf("Up Fix %d to %g\n", iColumn, upper[iColumn]);
372#endif
373            assert (upper[iColumn] < 1.0e20);
374            // apply any consequences
375            object_->applyConsequence(iSequence, 9999);
376        }
377    }
378    return 0.0;
379}
380void
381CbcNWayBranchingObject::print()
382{
383    printf("NWay - Up Fix ");
384    const int * members = object_->members();
385    for (int j = 0; j < way_; j++) {
386        int iColumn = members[order_[j]];
387        printf("%d ", iColumn);
388    }
389    printf("\n");
390}
391
392/** Compare the original object of \c this with the original object of \c
393    brObj. Assumes that there is an ordering of the original objects.
394    This method should be invoked only if \c this and brObj are of the same
395    type.
396    Return negative/0/positive depending on whether \c this is
397    smaller/same/larger than the argument.
398*/
399int
400CbcNWayBranchingObject::compareOriginalObject
401(const CbcBranchingObject* /*brObj*/) const
402{
403    throw("must implement");
404}
405
406/** Compare the \c this with \c brObj. \c this and \c brObj must be os the
407    same type and must have the same original object, but they may have
408    different feasible regions.
409    Return the appropriate CbcRangeCompare value (first argument being the
410    sub/superset if that's the case). In case of overlap (and if \c
411    replaceIfOverlap is true) replace the current branching object with one
412    whose feasible region is the overlap.
413*/
414CbcRangeCompare
415CbcNWayBranchingObject::compareBranchingObject
416(const CbcBranchingObject* /*brObj*/, const bool /*replaceIfOverlap*/)
417{
418    throw("must implement");
419}
420
Note: See TracBrowser for help on using the repository browser.