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

Last change on this file since 1293 was 1293, checked in by EdwinStraver, 10 years ago
File size: 15.6 KB
Line 
1// Edwin 11/10/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 "CbcIntegerBranchingObject.hpp"
18#include "CbcBranchActual.hpp"
19#include "CoinSort.hpp"
20#include "CoinError.hpp"
21
22//##############################################################################
23
24// Default Constructor
25CbcIntegerBranchingObject::CbcIntegerBranchingObject()
26        : CbcBranchingObject()
27{
28    down_[0] = 0.0;
29    down_[1] = 0.0;
30    up_[0] = 0.0;
31    up_[1] = 0.0;
32#ifdef FUNNY_BRANCHING
33    variables_ = NULL;
34    newBounds_ = NULL;
35    numberExtraChangedBounds_ = 0;
36#endif
37}
38// Useful constructor
39CbcIntegerBranchingObject::CbcIntegerBranchingObject (CbcModel * model,
40        int variable, int way , double value)
41        : CbcBranchingObject(model, variable, way, value)
42{
43    int iColumn = variable;
44    assert (model_->solver()->getNumCols() > 0);
45    down_[0] = model_->solver()->getColLower()[iColumn];
46    down_[1] = floor(value_);
47    up_[0] = ceil(value_);
48    up_[1] = model->getColUpper()[iColumn];
49#ifdef FUNNY_BRANCHING
50    variables_ = NULL;
51    newBounds_ = NULL;
52    numberExtraChangedBounds_ = 0;
53#endif
54}
55// Does part of constructor
56void
57CbcIntegerBranchingObject::fillPart (int variable,
58                                     int way , double value)
59{
60    //originalObject_=NULL;
61    branchIndex_ = 0;
62    value_ = value;
63    numberBranches_ = 2;
64    //model_= model;
65    //originalCbcObject_=NULL;
66    variable_ = variable;
67    way_ = way;
68    int iColumn = variable;
69    down_[0] = model_->solver()->getColLower()[iColumn];
70    down_[1] = floor(value_);
71    up_[0] = ceil(value_);
72    up_[1] = model_->getColUpper()[iColumn];
73}
74// Useful constructor for fixing
75CbcIntegerBranchingObject::CbcIntegerBranchingObject (CbcModel * model,
76        int variable, int way,
77        double lowerValue,
78        double upperValue)
79        : CbcBranchingObject(model, variable, way, lowerValue)
80{
81    setNumberBranchesLeft(1);
82    down_[0] = lowerValue;
83    down_[1] = upperValue;
84    up_[0] = lowerValue;
85    up_[1] = upperValue;
86#ifdef FUNNY_BRANCHING
87    variables_ = NULL;
88    newBounds_ = NULL;
89    numberExtraChangedBounds_ = 0;
90#endif
91}
92
93
94// Copy constructor
95CbcIntegerBranchingObject::CbcIntegerBranchingObject ( const CbcIntegerBranchingObject & rhs) : CbcBranchingObject(rhs)
96{
97    down_[0] = rhs.down_[0];
98    down_[1] = rhs.down_[1];
99    up_[0] = rhs.up_[0];
100    up_[1] = rhs.up_[1];
101#ifdef FUNNY_BRANCHING
102    numberExtraChangedBounds_ = rhs.numberExtraChangedBounds_;
103    int size = numberExtraChangedBounds_ * (sizeof(double) + sizeof(int));
104    char * temp = new char [size];
105    newBounds_ = (double *) temp;
106    variables_ = (int *) (newBounds_ + numberExtraChangedBounds_);
107
108    int i ;
109    for (i = 0; i < numberExtraChangedBounds_; i++) {
110        variables_[i] = rhs.variables_[i];
111        newBounds_[i] = rhs.newBounds_[i];
112    }
113#endif
114}
115
116// Assignment operator
117CbcIntegerBranchingObject &
118CbcIntegerBranchingObject::operator=( const CbcIntegerBranchingObject & rhs)
119{
120    if (this != &rhs) {
121        CbcBranchingObject::operator=(rhs);
122        down_[0] = rhs.down_[0];
123        down_[1] = rhs.down_[1];
124        up_[0] = rhs.up_[0];
125        up_[1] = rhs.up_[1];
126#ifdef FUNNY_BRANCHING
127        delete [] newBounds_;
128        numberExtraChangedBounds_ = rhs.numberExtraChangedBounds_;
129        int size = numberExtraChangedBounds_ * (sizeof(double) + sizeof(int));
130        char * temp = new char [size];
131        newBounds_ = (double *) temp;
132        variables_ = (int *) (newBounds_ + numberExtraChangedBounds_);
133
134        int i ;
135        for (i = 0; i < numberExtraChangedBounds_; i++) {
136            variables_[i] = rhs.variables_[i];
137            newBounds_[i] = rhs.newBounds_[i];
138        }
139#endif
140    }
141    return *this;
142}
143CbcBranchingObject *
144CbcIntegerBranchingObject::clone() const
145{
146    return (new CbcIntegerBranchingObject(*this));
147}
148
149
150// Destructor
151CbcIntegerBranchingObject::~CbcIntegerBranchingObject ()
152{
153    // for debugging threads
154    way_ = -23456789;
155#ifdef FUNNY_BRANCHING
156    delete [] newBounds_;
157#endif
158}
159
160/*
161  Perform a branch by adjusting the bounds of the specified variable. Note
162  that each arm of the branch advances the object to the next arm by
163  advancing the value of way_.
164
165  Providing new values for the variable's lower and upper bounds for each
166  branching direction gives a little bit of additional flexibility and will
167  be easily extensible to multi-way branching.
168  Returns change in guessed objective on next branch
169*/
170double
171CbcIntegerBranchingObject::branch()
172{
173    // for debugging threads
174    if (way_ < -1 || way_ > 100000) {
175        printf("way %d, left %d, iCol %d, variable %d\n",
176               way_, numberBranchesLeft(),
177               originalCbcObject_->columnNumber(), variable_);
178        assert (way_ != -23456789);
179    }
180    decrementNumberBranchesLeft();
181    if (down_[1] == -COIN_DBL_MAX)
182        return 0.0;
183    int iColumn = originalCbcObject_->columnNumber();
184    assert (variable_ == iColumn);
185    double olb, oub ;
186    olb = model_->solver()->getColLower()[iColumn] ;
187    oub = model_->solver()->getColUpper()[iColumn] ;
188    //#define TIGHTEN_BOUNDS
189#ifndef TIGHTEN_BOUNDS
190#ifdef COIN_DEVELOP
191    if (olb != down_[0] || oub != up_[1]) {
192        if (way_ > 0)
193            printf("branching up on var %d: [%g,%g] => [%g,%g] - other [%g,%g]\n",
194                   iColumn, olb, oub, up_[0], up_[1], down_[0], down_[1]) ;
195        else
196            printf("branching down on var %d: [%g,%g] => [%g,%g] - other [%g,%g]\n",
197                   iColumn, olb, oub, down_[0], down_[1], up_[0], up_[1]) ;
198    }
199#endif
200#endif
201    if (way_ < 0) {
202#ifdef CBC_DEBUG
203        { double olb, oub ;
204            olb = model_->solver()->getColLower()[iColumn] ;
205            oub = model_->solver()->getColUpper()[iColumn] ;
206            printf("branching down on var %d: [%g,%g] => [%g,%g]\n",
207                   iColumn, olb, oub, down_[0], down_[1]) ;
208        }
209#endif
210#ifndef TIGHTEN_BOUNDS
211        model_->solver()->setColLower(iColumn, down_[0]);
212#else
213        model_->solver()->setColLower(iColumn, CoinMax(down_[0], olb));
214#endif
215        model_->solver()->setColUpper(iColumn, down_[1]);
216        //#define CBC_PRINT2
217#ifdef CBC_PRINT2
218        printf("%d branching down has bounds %g %g", iColumn, down_[0], down_[1]);
219#endif
220#ifdef FUNNY_BRANCHING
221        // branch - do extra bounds
222        for (int i = 0; i < numberExtraChangedBounds_; i++) {
223            int variable = variables_[i];
224            if ((variable&0x40000000) != 0) {
225                // for going down
226                int k = variable & 0x3fffffff;
227                assert (k != iColumn);
228                if ((variable&0x80000000) == 0) {
229                    // lower bound changing
230#ifdef CBC_PRINT2
231                    printf(" extra for %d changes lower from %g to %g",
232                           k, model_->solver()->getColLower()[k], newBounds_[i]);
233#endif
234                    model_->solver()->setColLower(k, newBounds_[i]);
235                } else {
236                    // upper bound changing
237#ifdef CBC_PRINT2
238                    printf(" extra for %d changes upper from %g to %g",
239                           k, model_->solver()->getColUpper()[k], newBounds_[i]);
240#endif
241                    model_->solver()->setColUpper(k, newBounds_[i]);
242                }
243            }
244        }
245#endif
246#ifdef CBC_PRINT2
247        printf("\n");
248#endif
249        way_ = 1;
250    } else {
251#ifdef CBC_DEBUG
252        { double olb, oub ;
253            olb = model_->solver()->getColLower()[iColumn] ;
254            oub = model_->solver()->getColUpper()[iColumn] ;
255            printf("branching up on var %d: [%g,%g] => [%g,%g]\n",
256                   iColumn, olb, oub, up_[0], up_[1]) ;
257        }
258#endif
259        model_->solver()->setColLower(iColumn, up_[0]);
260#ifndef TIGHTEN_BOUNDS
261        model_->solver()->setColUpper(iColumn, up_[1]);
262#else
263        model_->solver()->setColUpper(iColumn, CoinMin(up_[1], oub));
264#endif
265#ifdef CBC_PRINT2
266        printf("%d branching up has bounds %g %g", iColumn, up_[0], up_[1]);
267#endif
268#ifdef FUNNY_BRANCHING
269        // branch - do extra bounds
270        for (int i = 0; i < numberExtraChangedBounds_; i++) {
271            int variable = variables_[i];
272            if ((variable&0x40000000) == 0) {
273                // for going up
274                int k = variable & 0x3fffffff;
275                assert (k != iColumn);
276                if ((variable&0x80000000) == 0) {
277                    // lower bound changing
278#ifdef CBC_PRINT2
279                    printf(" extra for %d changes lower from %g to %g",
280                           k, model_->solver()->getColLower()[k], newBounds_[i]);
281#endif
282                    model_->solver()->setColLower(k, newBounds_[i]);
283                } else {
284                    // upper bound changing
285#ifdef CBC_PRINT2
286                    printf(" extra for %d changes upper from %g to %g",
287                           k, model_->solver()->getColUpper()[k], newBounds_[i]);
288#endif
289                    model_->solver()->setColUpper(k, newBounds_[i]);
290                }
291            }
292        }
293#endif
294#ifdef CBC_PRINT2
295        printf("\n");
296#endif
297        way_ = -1;        // Swap direction
298    }
299    double nlb = model_->solver()->getColLower()[iColumn];
300    double nub = model_->solver()->getColUpper()[iColumn];
301    if (nlb < olb) {
302#ifndef NDEBUG
303        printf("bad lb change for column %d from %g to %g\n", iColumn, olb, nlb);
304#endif
305        model_->solver()->setColLower(iColumn, CoinMin(olb, nub));
306        nlb = olb;
307    }
308    if (nub > oub) {
309#ifndef NDEBUG
310        printf("bad ub change for column %d from %g to %g\n", iColumn, oub, nub);
311#endif
312        model_->solver()->setColUpper(iColumn, CoinMax(oub, nlb));
313    }
314#ifndef NDEBUG
315    if (nlb < olb + 1.0e-8 && nub > oub - 1.0e-8 && false)
316        printf("bad null change for column %d - bounds %g,%g\n", iColumn, olb, oub);
317#endif
318    return 0.0;
319}
320/* Update bounds in solver as in 'branch' and update given bounds.
321   branchState is -1 for 'down' +1 for 'up' */
322void
323CbcIntegerBranchingObject::fix(OsiSolverInterface * /*solver*/,
324                               double * lower, double * upper,
325                               int branchState) const
326{
327    int iColumn = originalCbcObject_->columnNumber();
328    assert (variable_ == iColumn);
329    if (branchState < 0) {
330        model_->solver()->setColLower(iColumn, down_[0]);
331        lower[iColumn] = down_[0];
332        model_->solver()->setColUpper(iColumn, down_[1]);
333        upper[iColumn] = down_[1];
334    } else {
335        model_->solver()->setColLower(iColumn, up_[0]);
336        lower[iColumn] = up_[0];
337        model_->solver()->setColUpper(iColumn, up_[1]);
338        upper[iColumn] = up_[1];
339    }
340}
341#ifdef FUNNY_BRANCHING
342// Deactivate bounds for branching
343void
344CbcIntegerBranchingObject::deactivate()
345{
346    down_[1] = -COIN_DBL_MAX;
347}
348int
349CbcIntegerBranchingObject::applyExtraBounds(int iColumn, double lower, double upper, int way)
350{
351    // branch - do bounds
352
353    int i;
354    int found = 0;
355    if (variable_ == iColumn) {
356        printf("odd applyExtra %d\n", iColumn);
357        if (way < 0) {
358            down_[0] = CoinMax(lower, down_[0]);
359            down_[1] = CoinMin(upper, down_[1]);
360            assert (down_[0] <= down_[1]);
361        } else {
362            up_[0] = CoinMax(lower, up_[0]);
363            up_[1] = CoinMin(upper, up_[1]);
364            assert (up_[0] <= up_[1]);
365        }
366        return 0;
367    }
368    int check = (way < 0) ? 0x40000000 : 0;
369    double newLower = lower;
370    double newUpper = upper;
371    for (i = 0; i < numberExtraChangedBounds_; i++) {
372        int variable = variables_[i];
373        if ((variable&0x40000000) == check) {
374            int k = variable & 0x3fffffff;
375            if (k == iColumn) {
376                if ((variable&0x80000000) == 0) {
377                    // lower bound changing
378                    found |= 1;
379                    newBounds_[i] = CoinMax(lower, newBounds_[i]);
380                    newLower = newBounds_[i];
381                } else {
382                    // upper bound changing
383                    found |= 2;
384                    newBounds_[i] = CoinMin(upper, newBounds_[i]);
385                    newUpper = newBounds_[i];
386                }
387            }
388        }
389    }
390    int nAdd = 0;
391    if ((found&2) == 0) {
392        // need to add new upper
393        nAdd++;
394    }
395    if ((found&1) == 0) {
396        // need to add new lower
397        nAdd++;
398    }
399    if (nAdd) {
400        int size = (numberExtraChangedBounds_ + nAdd) * (sizeof(double) + sizeof(int));
401        char * temp = new char [size];
402        double * newBounds = (double *) temp;
403        int * variables = (int *) (newBounds + numberExtraChangedBounds_ + nAdd);
404
405        int i ;
406        for (i = 0; i < numberExtraChangedBounds_; i++) {
407            variables[i] = variables_[i];
408            newBounds[i] = newBounds_[i];
409        }
410        delete [] newBounds_;
411        newBounds_ = newBounds;
412        variables_ = variables;
413        if ((found&2) == 0) {
414            // need to add new upper
415            int variable = iColumn | 0x80000000;
416            variables_[numberExtraChangedBounds_] = variable;
417            newBounds_[numberExtraChangedBounds_++] = newUpper;
418        }
419        if ((found&1) == 0) {
420            // need to add new lower
421            int variable = iColumn;
422            variables_[numberExtraChangedBounds_] = variable;
423            newBounds_[numberExtraChangedBounds_++] = newLower;
424        }
425    }
426
427    return (newUpper >= newLower) ? 0 : 1;
428}
429#endif
430// Print what would happen
431void
432CbcIntegerBranchingObject::print()
433{
434    int iColumn = originalCbcObject_->columnNumber();
435    assert (variable_ == iColumn);
436    if (way_ < 0) {
437        {
438            double olb, oub ;
439            olb = model_->solver()->getColLower()[iColumn] ;
440            oub = model_->solver()->getColUpper()[iColumn] ;
441            printf("CbcInteger would branch down on var %d (int var %d): [%g,%g] => [%g,%g]\n",
442                   iColumn, variable_, olb, oub, down_[0], down_[1]) ;
443        }
444    } else {
445        {
446            double olb, oub ;
447            olb = model_->solver()->getColLower()[iColumn] ;
448            oub = model_->solver()->getColUpper()[iColumn] ;
449            printf("CbcInteger would branch up on var %d (int var %d): [%g,%g] => [%g,%g]\n",
450                   iColumn, variable_, olb, oub, up_[0], up_[1]) ;
451        }
452    }
453}
454
455/** Compare the \c this with \c brObj. \c this and \c brObj must be os the
456    same type and must have the same original object, but they may have
457    different feasible regions.
458    Return the appropriate CbcRangeCompare value (first argument being the
459    sub/superset if that's the case). In case of overlap (and if \c
460    replaceIfOverlap is true) replace the current branching object with one
461    whose feasible region is the overlap.
462   */
463CbcRangeCompare
464CbcIntegerBranchingObject::compareBranchingObject
465(const CbcBranchingObject* brObj, const bool replaceIfOverlap)
466{
467    const CbcIntegerBranchingObject* br =
468        dynamic_cast<const CbcIntegerBranchingObject*>(brObj);
469    assert(br);
470    double* thisBd = way_ < 0 ? down_ : up_;
471    const double* otherBd = br->way_ < 0 ? br->down_ : br->up_;
472    return CbcCompareRanges(thisBd, otherBd, replaceIfOverlap);
473}
Note: See TracBrowser for help on using the repository browser.