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

Last change on this file since 1899 was 1899, checked in by stefan, 6 years ago

fixup svn properties

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