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

Last change on this file since 1293 was 1293, checked in by EdwinStraver, 10 years ago
File size: 10.3 KB
Line 
1// Edwin 11/9/2009-- carved out of CbcBranchActual
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 "CoinTypes.hpp"
13#include "OsiSolverInterface.hpp"
14#include "OsiSolverBranch.hpp"
15#include "CbcModel.hpp"
16#include "CbcMessage.hpp"
17#include "CbcClique.hpp"
18#include "CbcBranchActual.hpp"
19#include "CoinSort.hpp"
20#include "CoinError.hpp"
21//##############################################################################
22
23// Default Constructor
24CbcClique::CbcClique ()
25        : CbcObject(),
26        numberMembers_(0),
27        numberNonSOSMembers_(0),
28        members_(NULL),
29        type_(NULL),
30        cliqueType_(-1),
31        slack_(-1)
32{
33}
34
35// Useful constructor (which are integer indices)
36CbcClique::CbcClique (CbcModel * model, int cliqueType, int numberMembers,
37                      const int * which, const char * type, int identifier, int slack)
38        : CbcObject(model)
39{
40    id_ = identifier;
41    numberMembers_ = numberMembers;
42    if (numberMembers_) {
43        members_ = new int[numberMembers_];
44        memcpy(members_, which, numberMembers_*sizeof(int));
45        type_ = new char[numberMembers_];
46        if (type) {
47            memcpy(type_, type, numberMembers_*sizeof(char));
48        } else {
49            for (int i = 0; i < numberMembers_; i++)
50                type_[i] = 1;
51        }
52    } else {
53        members_ = NULL;
54        type_ = NULL;
55    }
56    // Find out how many non sos
57    int i;
58    numberNonSOSMembers_ = 0;
59    for (i = 0; i < numberMembers_; i++)
60        if (!type_[i])
61            numberNonSOSMembers_++;
62    cliqueType_ = cliqueType;
63    slack_ = slack;
64}
65
66// Copy constructor
67CbcClique::CbcClique ( const CbcClique & rhs)
68        : CbcObject(rhs)
69{
70    numberMembers_ = rhs.numberMembers_;
71    numberNonSOSMembers_ = rhs.numberNonSOSMembers_;
72    if (numberMembers_) {
73        members_ = new int[numberMembers_];
74        memcpy(members_, rhs.members_, numberMembers_*sizeof(int));
75        type_ = new char[numberMembers_];
76        memcpy(type_, rhs.type_, numberMembers_*sizeof(char));
77    } else {
78        members_ = NULL;
79        type_ = NULL;
80    }
81    cliqueType_ = rhs.cliqueType_;
82    slack_ = rhs.slack_;
83}
84
85// Clone
86CbcObject *
87CbcClique::clone() const
88{
89    return new CbcClique(*this);
90}
91
92// Assignment operator
93CbcClique &
94CbcClique::operator=( const CbcClique & rhs)
95{
96    if (this != &rhs) {
97        CbcObject::operator=(rhs);
98        delete [] members_;
99        delete [] type_;
100        numberMembers_ = rhs.numberMembers_;
101        numberNonSOSMembers_ = rhs.numberNonSOSMembers_;
102        if (numberMembers_) {
103            members_ = new int[numberMembers_];
104            memcpy(members_, rhs.members_, numberMembers_*sizeof(int));
105            type_ = new char[numberMembers_];
106            memcpy(type_, rhs.type_, numberMembers_*sizeof(char));
107        } else {
108            members_ = NULL;
109            type_ = NULL;
110        }
111        cliqueType_ = rhs.cliqueType_;
112        slack_ = rhs.slack_;
113    }
114    return *this;
115}
116
117// Destructor
118CbcClique::~CbcClique ()
119{
120    delete [] members_;
121    delete [] type_;
122}
123double
124CbcClique::infeasibility(const OsiBranchingInformation * /*info*/,
125                         int &preferredWay) const
126{
127    int numberUnsatis = 0, numberFree = 0;
128    int j;
129    const int * integer = model_->integerVariable();
130    OsiSolverInterface * solver = model_->solver();
131    const double * solution = model_->testSolution();
132    const double * lower = solver->getColLower();
133    const double * upper = solver->getColUpper();
134    double largestValue = 0.0;
135    double integerTolerance =
136        model_->getDblParam(CbcModel::CbcIntegerTolerance);
137    double * sort = new double[numberMembers_];
138
139    double slackValue = 0.0;
140    for (j = 0; j < numberMembers_; j++) {
141        int sequence = members_[j];
142        int iColumn = integer[sequence];
143        double value = solution[iColumn];
144        value = CoinMax(value, lower[iColumn]);
145        value = CoinMin(value, upper[iColumn]);
146        double nearest = floor(value + 0.5);
147        double distance = fabs(value - nearest);
148        if (distance > integerTolerance) {
149            if (!type_[j])
150                value = 1.0 - value; // non SOS
151            // if slack then choose that
152            if (j == slack_ && value > 0.05)
153                slackValue = value;
154            largestValue = CoinMax(value, largestValue);
155            sort[numberUnsatis++] = -value;
156        } else if (upper[iColumn] > lower[iColumn]) {
157            numberFree++;
158        }
159    }
160    preferredWay = 1;
161    double otherWay = 0.0;
162    if (numberUnsatis) {
163        // sort
164        std::sort(sort, sort + numberUnsatis);
165        for (j = 0; j < numberUnsatis; j++) {
166            if ((j&1) != 0)
167                otherWay += -sort[j];
168        }
169        // Need to think more
170        double value = 0.2 * numberUnsatis + 0.01 * (numberMembers_ - numberFree);
171        if (fabs(largestValue - 0.5) < 0.1) {
172            // close to half
173            value += 0.1;
174        }
175        if (slackValue) {
176            // branching on slack
177            value += slackValue;
178        }
179        // scale other way
180        otherWay *= value / (1.0 - otherWay);
181        delete [] sort;
182        return value;
183    } else {
184        delete [] sort;
185        return 0.0; // satisfied
186    }
187}
188
189// This looks at solution and sets bounds to contain solution
190void
191CbcClique::feasibleRegion()
192{
193    int j;
194    const int * integer = model_->integerVariable();
195    OsiSolverInterface * solver = model_->solver();
196    const double * solution = model_->testSolution();
197    const double * lower = solver->getColLower();
198    const double * upper = solver->getColUpper();
199#ifndef NDEBUG
200    double integerTolerance =
201        model_->getDblParam(CbcModel::CbcIntegerTolerance);
202#endif
203    for (j = 0; j < numberMembers_; j++) {
204        int sequence = members_[j];
205        int iColumn = integer[sequence];
206        double value = solution[iColumn];
207        value = CoinMax(value, lower[iColumn]);
208        value = CoinMin(value, upper[iColumn]);
209        double nearest = floor(value + 0.5);
210#ifndef NDEBUG
211        double distance = fabs(value - nearest);
212        assert(distance <= integerTolerance);
213#endif
214        solver->setColLower(iColumn, nearest);
215        solver->setColUpper(iColumn, nearest);
216    }
217}
218// Redoes data when sequence numbers change
219void
220CbcClique::redoSequenceEtc(CbcModel * model, int numberColumns, const int * originalColumns)
221{
222    model_ = model;
223    int n2 = 0;
224    for (int j = 0; j < numberMembers_; j++) {
225        int iColumn = members_[j];
226        int i;
227        for (i = 0; i < numberColumns; i++) {
228            if (originalColumns[i] == iColumn)
229                break;
230        }
231        if (i < numberColumns) {
232            members_[n2] = i;
233            type_[n2++] = type_[j];
234        }
235    }
236    if (n2 < numberMembers_) {
237        //printf("** SOS number of members reduced from %d to %d!\n",numberMembers_,n2);
238        numberMembers_ = n2;
239    }
240    // Find out how many non sos
241    int i;
242    numberNonSOSMembers_ = 0;
243    for (i = 0; i < numberMembers_; i++)
244        if (!type_[i])
245            numberNonSOSMembers_++;
246}
247CbcBranchingObject *
248CbcClique::createCbcBranch(OsiSolverInterface * solver, const OsiBranchingInformation * /*info*/, int way)
249{
250    int numberUnsatis = 0;
251    int j;
252    int nUp = 0;
253    int nDown = 0;
254    int numberFree = numberMembers_;
255    const int * integer = model_->integerVariable();
256    //OsiSolverInterface * solver = model_->solver();
257    const double * solution = model_->testSolution();
258    const double * lower = solver->getColLower();
259    const double * upper = solver->getColUpper();
260    int * upList = new int[numberMembers_];
261    int * downList = new int[numberMembers_];
262    double * sort = new double[numberMembers_];
263    double integerTolerance =
264        model_->getDblParam(CbcModel::CbcIntegerTolerance);
265
266    double slackValue = 0.0;
267    for (j = 0; j < numberMembers_; j++) {
268        int sequence = members_[j];
269        int iColumn = integer[sequence];
270        double value = solution[iColumn];
271        value = CoinMax(value, lower[iColumn]);
272        value = CoinMin(value, upper[iColumn]);
273        double nearest = floor(value + 0.5);
274        double distance = fabs(value - nearest);
275        if (distance > integerTolerance) {
276            if (!type_[j])
277                value = 1.0 - value; // non SOS
278            // if slack then choose that
279            if (j == slack_ && value > 0.05)
280                slackValue = value;
281            value = -value; // for sort
282            upList[numberUnsatis] = j;
283            sort[numberUnsatis++] = value;
284        } else if (upper[iColumn] > lower[iColumn]) {
285            upList[--numberFree] = j;
286        }
287    }
288    assert (numberUnsatis);
289    if (!slackValue) {
290        // sort
291        CoinSort_2(sort, sort + numberUnsatis, upList);
292        // put first in up etc
293        int kWay = 1;
294        for (j = 0; j < numberUnsatis; j++) {
295            if (kWay > 0)
296                upList[nUp++] = upList[j];
297            else
298                downList[nDown++] = upList[j];
299            kWay = -kWay;
300        }
301        for (j = numberFree; j < numberMembers_; j++) {
302            if (kWay > 0)
303                upList[nUp++] = upList[j];
304            else
305                downList[nDown++] = upList[j];
306            kWay = -kWay;
307        }
308    } else {
309        // put slack to 0 in first way
310        nUp = 1;
311        upList[0] = slack_;
312        for (j = 0; j < numberUnsatis; j++) {
313            downList[nDown++] = upList[j];
314        }
315        for (j = numberFree; j < numberMembers_; j++) {
316            downList[nDown++] = upList[j];
317        }
318    }
319    // create object
320    CbcBranchingObject * branch;
321    if (numberMembers_ <= 64)
322        branch = new CbcCliqueBranchingObject(model_, this, way,
323                                              nDown, downList, nUp, upList);
324    else
325        branch = new CbcLongCliqueBranchingObject(model_, this, way,
326                nDown, downList, nUp, upList);
327    delete [] upList;
328    delete [] downList;
329    delete [] sort;
330    return branch;
331}
Note: See TracBrowser for help on using the repository browser.