source: trunk/Cbc/src/CbcBranchAllDifferent.cpp @ 1433

Last change on this file since 1433 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: 4.1 KB
Line 
1// Edwin 11/13/2009-- carved out of CbcBranchCut
2#if defined(_MSC_VER)
3// Turn off compiler warning about long names
4#  pragma warning(disable:4786)
5#endif
6#include <cassert>
7#include <cstdlib>
8#include <cmath>
9#include <cfloat>
10//#define CBC_DEBUG
11
12#include "OsiSolverInterface.hpp"
13#include "CbcModel.hpp"
14#include "CbcMessage.hpp"
15#include "CbcBranchCut.hpp"
16#include "CoinSort.hpp"
17#include "CoinError.hpp"
18#include "CbcBranchAllDifferent.hpp"
19
20/** Default Constructor
21*/
22CbcBranchAllDifferent::CbcBranchAllDifferent ()
23        : CbcBranchCut(),
24        numberInSet_(0),
25        which_(NULL)
26{
27}
28
29/* Useful constructor - passed set of variables
30*/
31CbcBranchAllDifferent::CbcBranchAllDifferent (CbcModel * model, int numberInSet,
32        const int * members)
33        : CbcBranchCut(model)
34{
35    numberInSet_ = numberInSet;
36    which_ = CoinCopyOfArray(members, numberInSet_);
37}
38// Copy constructor
39CbcBranchAllDifferent::CbcBranchAllDifferent ( const CbcBranchAllDifferent & rhs)
40        : CbcBranchCut(rhs)
41{
42    numberInSet_ = rhs.numberInSet_;
43    which_ = CoinCopyOfArray(rhs.which_, numberInSet_);
44}
45
46// Clone
47CbcObject *
48CbcBranchAllDifferent::clone() const
49{
50    return new CbcBranchAllDifferent(*this);
51}
52
53// Assignment operator
54CbcBranchAllDifferent &
55CbcBranchAllDifferent::operator=( const CbcBranchAllDifferent & rhs)
56{
57    if (this != &rhs) {
58        CbcBranchCut::operator=(rhs);
59        delete [] which_;
60        numberInSet_ = rhs.numberInSet_;
61        which_ = CoinCopyOfArray(rhs.which_, numberInSet_);
62    }
63    return *this;
64}
65
66// Destructor
67CbcBranchAllDifferent::~CbcBranchAllDifferent ()
68{
69    delete [] which_;
70}
71CbcBranchingObject *
72CbcBranchAllDifferent::createCbcBranch(OsiSolverInterface * /*solver*/
73                                       , const OsiBranchingInformation * /*info*/,
74                                       int /*way*/)
75{
76    // by default way must be -1
77    //assert (way==-1);
78    const double * solution = model_->testSolution();
79    double * values = new double[numberInSet_];
80    int * which = new int[numberInSet_];
81    int i;
82    for (i = 0; i < numberInSet_; i++) {
83        int iColumn = which_[i];
84        values[i] = solution[iColumn];
85        which[i] = iColumn;
86    }
87    CoinSort_2(values, values + numberInSet_, which);
88    double last = -1.0;
89    double closest = 1.0;
90    int worst = -1;
91    for (i = 0; i < numberInSet_; i++) {
92        if (values[i] - last < closest) {
93            closest = values[i] - last;
94            worst = i - 1;
95        }
96        last = values[i];
97    }
98    assert (closest <= 0.99999);
99    OsiRowCut down;
100    down.setLb(-COIN_DBL_MAX);
101    down.setUb(-1.0);
102    int pair[2];
103    double elements[] = {1.0, -1.0};
104    pair[0] = which[worst];
105    pair[1] = which[worst+1];
106    delete [] values;
107    delete [] which;
108    down.setRow(2, pair, elements);
109    // up is same - just with rhs changed
110    OsiRowCut up = down;
111    up.setLb(1.0);
112    up.setUb(COIN_DBL_MAX);
113    // Say is not a fix type branch
114    CbcCutBranchingObject * newObject =
115        new CbcCutBranchingObject(model_, down, up, false);
116    if (model_->messageHandler()->logLevel() > 1)
117        printf("creating cut in CbcBranchCut\n");
118    return newObject;
119}
120double
121CbcBranchAllDifferent::infeasibility(const OsiBranchingInformation * /*info*/,
122                                     int &preferredWay) const
123{
124    preferredWay = -1;
125    //OsiSolverInterface * solver = model_->solver();
126    const double * solution = model_->testSolution();
127    //const double * lower = solver->getColLower();
128    //const double * upper = solver->getColUpper();
129    double * values = new double[numberInSet_];
130    int i;
131    for (i = 0; i < numberInSet_; i++) {
132        int iColumn = which_[i];
133        values[i] = solution[iColumn];
134    }
135    std::sort(values, values + numberInSet_);
136    double last = -1.0;
137    double closest = 1.0;
138    for (i = 0; i < numberInSet_; i++) {
139        if (values[i] - last < closest) {
140            closest = values[i] - last;
141        }
142        last = values[i];
143    }
144    delete [] values;
145    if (closest > 0.99999)
146        return 0.0;
147    else
148        return 0.5*(1.0 - closest);
149}
150
Note: See TracBrowser for help on using the repository browser.