source: trunk/Cbc/src/CbcBranchLotsize.cpp @ 1869

Last change on this file since 1869 was 1573, checked in by lou, 9 years ago

Change to EPL license notice.

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 25.3 KB
Line 
1/* $Id: CbcBranchLotsize.cpp 1573 2011-01-05 01:12:36Z stefan $ */
2// Copyright (C) 2002, 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#if defined(_MSC_VER)
7// Turn off compiler warning about long names
8#  pragma warning(disable:4786)
9#endif
10#include <cassert>
11#include <cstdlib>
12#include <cmath>
13#include <cfloat>
14
15#include "OsiSolverInterface.hpp"
16#include "CbcModel.hpp"
17#include "CbcMessage.hpp"
18#include "CbcBranchLotsize.hpp"
19#include "CoinSort.hpp"
20#include "CoinError.hpp"
21
22/*
23  CBC_PRINT 1 just does sanity checks - no printing
24  Larger values of CBC_PRINT set various printing levels.  Larger
25  values print more.
26*/
27//#define CBC_PRINT 1
28// First/last variable to print info on
29#if CBC_PRINT
30// preset does all - change to x,x to just do x
31static int firstPrint = 0;
32static int lastPrint = 1000000;
33static CbcModel * saveModel = NULL;
34#endif
35// Just for debug (CBC_PRINT defined in CbcBranchLotsize.cpp)
36void
37#if CBC_PRINT
38CbcLotsize::printLotsize(double value, bool condition, int type) const
39#else
40CbcLotsize::printLotsize(double , bool , int ) const
41#endif
42{
43#if CBC_PRINT
44    if (columnNumber_ >= firstPrint && columnNumber_ <= lastPrint) {
45        int printIt = CBC_PRINT - 1;
46        // Get details
47        OsiSolverInterface * solver = saveModel->solver();
48        double currentLower = solver->getColLower()[columnNumber_];
49        double currentUpper = solver->getColUpper()[columnNumber_];
50        int i;
51        // See if in a valid range (with two tolerances)
52        bool inRange = false;
53        bool inRange2 = false;
54        double integerTolerance =
55            model_->getDblParam(CbcModel::CbcIntegerTolerance);
56        // increase if type 2
57        if (type == 2) {
58            integerTolerance *= 100.0;
59            type = 0;
60            printIt = 2; // always print
61        }
62        // bounds should match some bound
63        int rangeL = -1;
64        int rangeU = -1;
65        if (rangeType_ == 1) {
66            for (i = 0; i < numberRanges_; i++) {
67                if (fabs(currentLower - bound_[i]) < 1.0e-12)
68                    rangeL = i;
69                if (fabs(currentUpper - bound_[i]) < 1.0e-12)
70                    rangeU = i;
71                if (fabs(value - bound_[i]) < integerTolerance)
72                    inRange = true;
73                if (fabs(value - bound_[i]) < 1.0e8)
74                    inRange2 = true;
75            }
76        } else {
77            for (i = 0; i < numberRanges_; i++) {
78                if (fabs(currentLower - bound_[2*i]) < 1.0e-12)
79                    rangeL = i;
80                if (fabs(currentUpper - bound_[2*i+1]) < 1.0e-12)
81                    rangeU = i;
82                if (value > bound_[2*i] - integerTolerance &&
83                        value < bound_[2*i+1] + integerTolerance)
84                    inRange = true;
85                if (value > bound_[2*i] - integerTolerance &&
86                        value < bound_[2*i+1] + integerTolerance)
87                    inRange = true;
88            }
89        }
90        assert (rangeL >= 0 && rangeU >= 0);
91        bool abortIt = false;
92        switch (type) {
93            // returning from findRange (fall through to just check)
94        case 0:
95            if (printIt) {
96                printf("findRange returns %s for column %d and value %g",
97                       condition ? "true" : "false", columnNumber_, value);
98                if (printIt > 1)
99                    printf(" LP bounds %g, %g", currentLower, currentUpper);
100                printf("\n");
101            }
102            // Should match
103        case 1:
104            if (inRange != condition) {
105                printIt = 2;
106                abortIt = true;
107            }
108            break;
109            //
110        case 2:
111            break;
112            //
113        case 3:
114            break;
115            //
116        case 4:
117            break;
118        }
119    }
120#endif
121}
122/** Default Constructor
123
124*/
125CbcLotsize::CbcLotsize ()
126        : CbcObject(),
127        columnNumber_(-1),
128        rangeType_(0),
129        numberRanges_(0),
130        largestGap_(0),
131        bound_(NULL),
132        range_(0)
133{
134}
135
136/** Useful constructor
137
138  Loads actual upper & lower bounds for the specified variable.
139*/
140CbcLotsize::CbcLotsize (CbcModel * model,
141                        int iColumn, int numberPoints,
142                        const double * points, bool range)
143        : CbcObject(model)
144{
145#if CBC_PRINT
146    if (!saveModel)
147        saveModel = model;
148#endif
149    assert (numberPoints > 0);
150    columnNumber_ = iColumn ;
151    // and set id so can be used for branching
152    id_ = iColumn;
153    // sort ranges
154    int * sort = new int[numberPoints];
155    double * weight = new double [numberPoints];
156    int i;
157    if (range) {
158        rangeType_ = 2;
159    } else {
160        rangeType_ = 1;
161    }
162    for (i = 0; i < numberPoints; i++) {
163        sort[i] = i;
164        weight[i] = points[i*rangeType_];
165    }
166    CoinSort_2(weight, weight + numberPoints, sort);
167    numberRanges_ = 1;
168    largestGap_ = 0;
169    if (rangeType_ == 1) {
170        bound_ = new double[numberPoints+1];
171        bound_[0] = weight[0];
172        for (i = 1; i < numberPoints; i++) {
173            if (weight[i] != weight[i-1])
174                bound_[numberRanges_++] = weight[i];
175        }
176        // and for safety
177        bound_[numberRanges_] = bound_[numberRanges_-1];
178        for (i = 1; i < numberRanges_; i++) {
179            largestGap_ = CoinMax(largestGap_, bound_[i] - bound_[i-1]);
180        }
181    } else {
182        bound_ = new double[2*numberPoints+2];
183        bound_[0] = points[sort[0] * 2];
184        bound_[1] = points[sort[0] * 2 + 1];
185        double lo = bound_[0];
186        double hi = bound_[1];
187        assert (hi >= lo);
188        for (i = 1; i < numberPoints; i++) {
189            double thisLo = points[sort[i] * 2];
190            double thisHi = points[sort[i] * 2 + 1];
191            assert (thisHi >= thisLo);
192            if (thisLo > hi) {
193                bound_[2*numberRanges_] = thisLo;
194                bound_[2*numberRanges_+1] = thisHi;
195                numberRanges_++;
196                lo = thisLo;
197                hi = thisHi;
198            } else {
199                //overlap
200                hi = CoinMax(hi, thisHi);
201                bound_[2*numberRanges_-1] = hi;
202            }
203        }
204        // and for safety
205        bound_[2*numberRanges_] = bound_[2*numberRanges_-2];
206        bound_[2*numberRanges_+1] = bound_[2*numberRanges_-1];
207        for (i = 1; i < numberRanges_; i++) {
208            largestGap_ = CoinMax(largestGap_, bound_[2*i] - bound_[2*i-1]);
209        }
210    }
211    delete [] sort;
212    delete [] weight;
213    range_ = 0;
214}
215
216// Copy constructor
217CbcLotsize::CbcLotsize ( const CbcLotsize & rhs)
218        : CbcObject(rhs)
219
220{
221    columnNumber_ = rhs.columnNumber_;
222    rangeType_ = rhs.rangeType_;
223    numberRanges_ = rhs.numberRanges_;
224    range_ = rhs.range_;
225    largestGap_ = rhs.largestGap_;
226    if (numberRanges_) {
227        assert (rangeType_ > 0 && rangeType_ < 3);
228        bound_ = new double [(numberRanges_+1)*rangeType_];
229        memcpy(bound_, rhs.bound_, (numberRanges_ + 1)*rangeType_*sizeof(double));
230    } else {
231        bound_ = NULL;
232    }
233}
234
235// Clone
236CbcObject *
237CbcLotsize::clone() const
238{
239    return new CbcLotsize(*this);
240}
241
242// Assignment operator
243CbcLotsize &
244CbcLotsize::operator=( const CbcLotsize & rhs)
245{
246    if (this != &rhs) {
247        CbcObject::operator=(rhs);
248        columnNumber_ = rhs.columnNumber_;
249        rangeType_ = rhs.rangeType_;
250        numberRanges_ = rhs.numberRanges_;
251        largestGap_ = rhs.largestGap_;
252        delete [] bound_;
253        range_ = rhs.range_;
254        if (numberRanges_) {
255            assert (rangeType_ > 0 && rangeType_ < 3);
256            bound_ = new double [(numberRanges_+1)*rangeType_];
257            memcpy(bound_, rhs.bound_, (numberRanges_ + 1)*rangeType_*sizeof(double));
258        } else {
259            bound_ = NULL;
260        }
261    }
262    return *this;
263}
264
265// Destructor
266CbcLotsize::~CbcLotsize ()
267{
268    delete [] bound_;
269}
270/* Finds range of interest so value is feasible in range range_ or infeasible
271   between hi[range_] and lo[range_+1].  Returns true if feasible.
272*/
273bool
274CbcLotsize::findRange(double value) const
275{
276    assert (range_ >= 0 && range_ < numberRanges_ + 1);
277    double integerTolerance =
278        model_->getDblParam(CbcModel::CbcIntegerTolerance);
279    int iLo;
280    int iHi;
281    double infeasibility = 0.0;
282    if (rangeType_ == 1) {
283        if (value < bound_[range_] - integerTolerance) {
284            iLo = 0;
285            iHi = range_ - 1;
286        } else if (value < bound_[range_] + integerTolerance) {
287#if CBC_PRINT
288            printLotsize(value, true, 0);
289#endif
290            return true;
291        } else if (value < bound_[range_+1] - integerTolerance) {
292#ifdef CBC_PRINT
293            printLotsize(value, false, 0);
294#endif
295            return false;
296        } else {
297            iLo = range_ + 1;
298            iHi = numberRanges_ - 1;
299        }
300        // check lo and hi
301        bool found = false;
302        if (value > bound_[iLo] - integerTolerance && value < bound_[iLo+1] + integerTolerance) {
303            range_ = iLo;
304            found = true;
305        } else if (value > bound_[iHi] - integerTolerance && value < bound_[iHi+1] + integerTolerance) {
306            range_ = iHi;
307            found = true;
308        } else {
309            range_ = (iLo + iHi) >> 1;
310        }
311        //points
312        while (!found) {
313            if (value < bound_[range_]) {
314                if (value >= bound_[range_-1]) {
315                    // found
316                    range_--;
317                    break;
318                } else {
319                    iHi = range_;
320                }
321            } else {
322                if (value < bound_[range_+1]) {
323                    // found
324                    break;
325                } else {
326                    iLo = range_;
327                }
328            }
329            range_ = (iLo + iHi) >> 1;
330        }
331        if (value - bound_[range_] <= bound_[range_+1] - value) {
332            infeasibility = value - bound_[range_];
333        } else {
334            infeasibility = bound_[range_+1] - value;
335            if (infeasibility < integerTolerance)
336                range_++;
337        }
338#ifdef CBC_PRINT
339        printLotsize(value, (infeasibility < integerTolerance), 0);
340#endif
341        return (infeasibility < integerTolerance);
342    } else {
343        // ranges
344        if (value < bound_[2*range_] - integerTolerance) {
345            iLo = 0;
346            iHi = range_ - 1;
347        } else if (value < bound_[2*range_+1] + integerTolerance) {
348#ifdef CBC_PRINT
349            printLotsize(value, true, 0);
350#endif
351            return true;
352        } else if (value < bound_[2*range_+2] - integerTolerance) {
353#ifdef CBC_PRINT
354            printLotsize(value, false, 0);
355#endif
356            return false;
357        } else {
358            iLo = range_ + 1;
359            iHi = numberRanges_ - 1;
360        }
361        // check lo and hi
362        bool found = false;
363        if (value > bound_[2*iLo] - integerTolerance && value < bound_[2*iLo+2] - integerTolerance) {
364            range_ = iLo;
365            found = true;
366        } else if (value >= bound_[2*iHi] - integerTolerance) {
367            range_ = iHi;
368            found = true;
369        } else {
370            range_ = (iLo + iHi) >> 1;
371        }
372        //points
373        while (!found) {
374            if (value < bound_[2*range_]) {
375                if (value >= bound_[2*range_-2]) {
376                    // found
377                    range_--;
378                    break;
379                } else {
380                    iHi = range_;
381                }
382            } else {
383                if (value < bound_[2*range_+2]) {
384                    // found
385                    break;
386                } else {
387                    iLo = range_;
388                }
389            }
390            range_ = (iLo + iHi) >> 1;
391        }
392        if (value >= bound_[2*range_] - integerTolerance && value <= bound_[2*range_+1] + integerTolerance)
393            infeasibility = 0.0;
394        else if (value - bound_[2*range_+1] < bound_[2*range_+2] - value) {
395            infeasibility = value - bound_[2*range_+1];
396        } else {
397            infeasibility = bound_[2*range_+2] - value;
398        }
399#ifdef CBC_PRINT
400        printLotsize(value, (infeasibility < integerTolerance), 0);
401#endif
402        return (infeasibility < integerTolerance);
403    }
404}
405/* Returns floor and ceiling
406 */
407void
408CbcLotsize::floorCeiling(double & floorLotsize, double & ceilingLotsize, double value,
409                         double /*tolerance*/) const
410{
411    bool feasible = findRange(value);
412    if (rangeType_ == 1) {
413        floorLotsize = bound_[range_];
414        ceilingLotsize = bound_[range_+1];
415        // may be able to adjust
416        if (feasible && fabs(value - floorLotsize) > fabs(value - ceilingLotsize)) {
417            floorLotsize = bound_[range_+1];
418            ceilingLotsize = bound_[range_+2];
419        }
420    } else {
421        // ranges
422        assert (value >= bound_[2*range_+1]);
423        floorLotsize = bound_[2*range_+1];
424        ceilingLotsize = bound_[2*range_+2];
425    }
426}
427double
428CbcLotsize::infeasibility(const OsiBranchingInformation * /*info*/,
429                          int &preferredWay) const
430{
431    OsiSolverInterface * solver = model_->solver();
432    const double * solution = model_->testSolution();
433    const double * lower = solver->getColLower();
434    const double * upper = solver->getColUpper();
435    double value = solution[columnNumber_];
436    value = CoinMax(value, lower[columnNumber_]);
437    value = CoinMin(value, upper[columnNumber_]);
438    double integerTolerance =
439        model_->getDblParam(CbcModel::CbcIntegerTolerance);
440    /*printf("%d %g %g %g %g\n",columnNumber_,value,lower[columnNumber_],
441      solution[columnNumber_],upper[columnNumber_]);*/
442    assert (value >= bound_[0] - integerTolerance
443            && value <= bound_[rangeType_*numberRanges_-1] + integerTolerance);
444    double infeasibility = 0.0;
445    bool feasible = findRange(value);
446    if (!feasible) {
447        if (rangeType_ == 1) {
448            if (value - bound_[range_] < bound_[range_+1] - value) {
449                preferredWay = -1;
450                infeasibility = value - bound_[range_];
451            } else {
452                preferredWay = 1;
453                infeasibility = bound_[range_+1] - value;
454            }
455        } else {
456            // ranges
457            if (value - bound_[2*range_+1] < bound_[2*range_+2] - value) {
458                preferredWay = -1;
459                infeasibility = value - bound_[2*range_+1];
460            } else {
461                preferredWay = 1;
462                infeasibility = bound_[2*range_+2] - value;
463            }
464        }
465    } else {
466        // always satisfied
467        preferredWay = -1;
468    }
469    if (infeasibility < integerTolerance)
470        infeasibility = 0.0;
471    else
472        infeasibility /= largestGap_;
473#ifdef CBC_PRINT
474    printLotsize(value, infeasibility, 1);
475#endif
476    return infeasibility;
477}
478/* Column number if single column object -1 otherwise,
479   so returns >= 0
480   Used by heuristics
481*/
482int
483CbcLotsize::columnNumber() const
484{
485    return columnNumber_;
486}
487// This looks at solution and sets bounds to contain solution
488/** More precisely: it first forces the variable within the existing
489    bounds, and then tightens the bounds to make sure the variable is feasible
490*/
491void
492CbcLotsize::feasibleRegion()
493{
494    OsiSolverInterface * solver = model_->solver();
495    const double * lower = solver->getColLower();
496    const double * upper = solver->getColUpper();
497    const double * solution = model_->testSolution();
498    double value = solution[columnNumber_];
499    value = CoinMax(value, lower[columnNumber_]);
500    value = CoinMin(value, upper[columnNumber_]);
501    findRange(value);
502    double nearest;
503    if (rangeType_ == 1) {
504        nearest = bound_[range_];
505        solver->setColLower(columnNumber_, nearest);
506        solver->setColUpper(columnNumber_, nearest);
507    } else {
508        // ranges
509        solver->setColLower(columnNumber_, bound_[2*range_]);
510        solver->setColUpper(columnNumber_, bound_[2*range_+1]);
511        if (value > bound_[2*range_+1])
512            nearest = bound_[2*range_+1];
513        else if (value < bound_[2*range_])
514            nearest = bound_[2*range_];
515        else
516            nearest = value;
517    }
518#ifdef CBC_PRINT
519    // print details
520    printLotsize(value, true, 2);
521#endif
522    // Scaling may have moved it a bit
523    // Lotsizing variables could be a lot larger
524#ifndef NDEBUG
525    double integerTolerance =
526        model_->getDblParam(CbcModel::CbcIntegerTolerance);
527    assert (fabs(value - nearest) <= (100.0 + 10.0*fabs(nearest))*integerTolerance);
528#endif
529}
530CbcBranchingObject *
531CbcLotsize::createCbcBranch(OsiSolverInterface * solver, const OsiBranchingInformation * /*info*/, int way)
532{
533    //OsiSolverInterface * solver = model_->solver();
534    const double * solution = model_->testSolution();
535    const double * lower = solver->getColLower();
536    const double * upper = solver->getColUpper();
537    double value = solution[columnNumber_];
538    value = CoinMax(value, lower[columnNumber_]);
539    value = CoinMin(value, upper[columnNumber_]);
540    assert (!findRange(value));
541    return new CbcLotsizeBranchingObject(model_, columnNumber_, way,
542                                         value, this);
543}
544
545
546/* Given valid solution (i.e. satisfied) and reduced costs etc
547   returns a branching object which would give a new feasible
548   point in direction reduced cost says would be cheaper.
549   If no feasible point returns null
550*/
551CbcBranchingObject *
552CbcLotsize::preferredNewFeasible() const
553{
554    OsiSolverInterface * solver = model_->solver();
555
556    assert (findRange(model_->testSolution()[columnNumber_]));
557    double dj = solver->getObjSense() * solver->getReducedCost()[columnNumber_];
558    CbcLotsizeBranchingObject * object = NULL;
559    double lo, up;
560    if (dj >= 0.0) {
561        // can we go down
562        if (range_) {
563            // yes
564            if (rangeType_ == 1) {
565                lo = bound_[range_-1];
566                up = bound_[range_-1];
567            } else {
568                lo = bound_[2*range_-2];
569                up = bound_[2*range_-1];
570            }
571            object = new CbcLotsizeBranchingObject(model_, columnNumber_, -1,
572                                                   lo, up);
573        }
574    } else {
575        // can we go up
576        if (range_ < numberRanges_ - 1) {
577            // yes
578            if (rangeType_ == 1) {
579                lo = bound_[range_+1];
580                up = bound_[range_+1];
581            } else {
582                lo = bound_[2*range_+2];
583                up = bound_[2*range_+3];
584            }
585            object = new CbcLotsizeBranchingObject(model_, columnNumber_, -1,
586                                                   lo, up);
587        }
588    }
589    return object;
590}
591
592/* Given valid solution (i.e. satisfied) and reduced costs etc
593   returns a branching object which would give a new feasible
594   point in direction opposite to one reduced cost says would be cheaper.
595   If no feasible point returns null
596*/
597CbcBranchingObject *
598CbcLotsize::notPreferredNewFeasible() const
599{
600    OsiSolverInterface * solver = model_->solver();
601
602#ifndef NDEBUG
603    double value = model_->testSolution()[columnNumber_];
604    double nearest = floor(value + 0.5);
605    double integerTolerance =
606        model_->getDblParam(CbcModel::CbcIntegerTolerance);
607    // Scaling may have moved it a bit
608    // Lotsizing variables could be a lot larger
609    assert (fabs(value - nearest) <= (10.0 + 10.0*fabs(nearest))*integerTolerance);
610#endif
611    double dj = solver->getObjSense() * solver->getReducedCost()[columnNumber_];
612    CbcLotsizeBranchingObject * object = NULL;
613    double lo, up;
614    if (dj <= 0.0) {
615        // can we go down
616        if (range_) {
617            // yes
618            if (rangeType_ == 1) {
619                lo = bound_[range_-1];
620                up = bound_[range_-1];
621            } else {
622                lo = bound_[2*range_-2];
623                up = bound_[2*range_-1];
624            }
625            object = new CbcLotsizeBranchingObject(model_, columnNumber_, -1,
626                                                   lo, up);
627        }
628    } else {
629        // can we go up
630        if (range_ < numberRanges_ - 1) {
631            // yes
632            if (rangeType_ == 1) {
633                lo = bound_[range_+1];
634                up = bound_[range_+1];
635            } else {
636                lo = bound_[2*range_+2];
637                up = bound_[2*range_+3];
638            }
639            object = new CbcLotsizeBranchingObject(model_, columnNumber_, -1,
640                                                   lo, up);
641        }
642    }
643    return object;
644}
645
646/*
647  Bounds may be tightened, so it may be good to be able to refresh the local
648  copy of the original bounds.
649 */
650void
651CbcLotsize::resetBounds(const OsiSolverInterface * /*solver*/)
652{
653}
654
655// Default Constructor
656CbcLotsizeBranchingObject::CbcLotsizeBranchingObject()
657        : CbcBranchingObject()
658{
659    down_[0] = 0.0;
660    down_[1] = 0.0;
661    up_[0] = 0.0;
662    up_[1] = 0.0;
663}
664
665// Useful constructor
666CbcLotsizeBranchingObject::CbcLotsizeBranchingObject (CbcModel * model,
667        int variable, int way , double value,
668        const CbcLotsize * lotsize)
669        : CbcBranchingObject(model, variable, way, value)
670{
671    int iColumn = lotsize->modelSequence();
672    assert (variable == iColumn);
673    down_[0] = model_->solver()->getColLower()[iColumn];
674    double integerTolerance =
675        model_->getDblParam(CbcModel::CbcIntegerTolerance);
676    lotsize->floorCeiling(down_[1], up_[0], value, integerTolerance);
677    up_[1] = model->getColUpper()[iColumn];
678}
679// Useful constructor for fixing
680CbcLotsizeBranchingObject::CbcLotsizeBranchingObject (CbcModel * model,
681        int variable, int way,
682        double lowerValue,
683        double upperValue)
684        : CbcBranchingObject(model, variable, way, lowerValue)
685{
686    setNumberBranchesLeft(1);
687    down_[0] = lowerValue;
688    down_[1] = upperValue;
689    up_[0] = lowerValue;
690    up_[1] = upperValue;
691}
692
693
694// Copy constructor
695CbcLotsizeBranchingObject::CbcLotsizeBranchingObject ( const CbcLotsizeBranchingObject & rhs) : CbcBranchingObject(rhs)
696{
697    down_[0] = rhs.down_[0];
698    down_[1] = rhs.down_[1];
699    up_[0] = rhs.up_[0];
700    up_[1] = rhs.up_[1];
701}
702
703// Assignment operator
704CbcLotsizeBranchingObject &
705CbcLotsizeBranchingObject::operator=( const CbcLotsizeBranchingObject & rhs)
706{
707    if (this != &rhs) {
708        CbcBranchingObject::operator=(rhs);
709        down_[0] = rhs.down_[0];
710        down_[1] = rhs.down_[1];
711        up_[0] = rhs.up_[0];
712        up_[1] = rhs.up_[1];
713    }
714    return *this;
715}
716CbcBranchingObject *
717CbcLotsizeBranchingObject::clone() const
718{
719    return (new CbcLotsizeBranchingObject(*this));
720}
721
722
723// Destructor
724CbcLotsizeBranchingObject::~CbcLotsizeBranchingObject ()
725{
726}
727
728/*
729  Perform a branch by adjusting the bounds of the specified variable. Note
730  that each arm of the branch advances the object to the next arm by
731  advancing the value of way_.
732
733  Providing new values for the variable's lower and upper bounds for each
734  branching direction gives a little bit of additional flexibility and will
735  be easily extensible to multi-way branching.
736*/
737double
738CbcLotsizeBranchingObject::branch()
739{
740    decrementNumberBranchesLeft();
741    int iColumn = variable_;
742    if (way_ < 0) {
743#ifdef CBC_DEBUG
744        { double olb, oub ;
745            olb = model_->solver()->getColLower()[iColumn] ;
746            oub = model_->solver()->getColUpper()[iColumn] ;
747            printf("branching down on var %d: [%g,%g] => [%g,%g]\n",
748                   iColumn, olb, oub, down_[0], down_[1]) ;
749        }
750#endif
751        model_->solver()->setColLower(iColumn, down_[0]);
752        model_->solver()->setColUpper(iColumn, down_[1]);
753        way_ = 1;
754    } else {
755#ifdef CBC_DEBUG
756        { double olb, oub ;
757            olb = model_->solver()->getColLower()[iColumn] ;
758            oub = model_->solver()->getColUpper()[iColumn] ;
759            printf("branching up on var %d: [%g,%g] => [%g,%g]\n",
760                   iColumn, olb, oub, up_[0], up_[1]) ;
761        }
762#endif
763        model_->solver()->setColLower(iColumn, up_[0]);
764        model_->solver()->setColUpper(iColumn, up_[1]);
765        way_ = -1;        // Swap direction
766    }
767    return 0.0;
768}
769// Print
770void
771CbcLotsizeBranchingObject::print()
772{
773    int iColumn = variable_;
774    if (way_ < 0) {
775        {
776            double olb, oub ;
777            olb = model_->solver()->getColLower()[iColumn] ;
778            oub = model_->solver()->getColUpper()[iColumn] ;
779            printf("branching down on var %d: [%g,%g] => [%g,%g]\n",
780                   iColumn, olb, oub, down_[0], down_[1]) ;
781        }
782    } else {
783        {
784            double olb, oub ;
785            olb = model_->solver()->getColLower()[iColumn] ;
786            oub = model_->solver()->getColUpper()[iColumn] ;
787            printf("branching up on var %d: [%g,%g] => [%g,%g]\n",
788                   iColumn, olb, oub, up_[0], up_[1]) ;
789        }
790    }
791}
792
793/** Compare the \c this with \c brObj. \c this and \c brObj must be os the
794    same type and must have the same original object, but they may have
795    different feasible regions.
796    Return the appropriate CbcRangeCompare value (first argument being the
797    sub/superset if that's the case). In case of overlap (and if \c
798    replaceIfOverlap is true) replace the current branching object with one
799    whose feasible region is the overlap.
800*/
801CbcRangeCompare
802CbcLotsizeBranchingObject::compareBranchingObject
803(const CbcBranchingObject* brObj, const bool replaceIfOverlap)
804{
805    const CbcLotsizeBranchingObject* br =
806        dynamic_cast<const CbcLotsizeBranchingObject*>(brObj);
807    assert(br);
808    double* thisBd = way_ == -1 ? down_ : up_;
809    const double* otherBd = br->way_ == -1 ? br->down_ : br->up_;
810    return CbcCompareRanges(thisBd, otherBd, replaceIfOverlap);
811}
812
Note: See TracBrowser for help on using the repository browser.