source: stable/2.9/Cbc/src/CbcBranchLotsize.cpp @ 2238

Last change on this file since 2238 was 2043, checked in by forrest, 5 years ago

minor changes for SOS etc
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 25.4 KB
Line 
1/* $Id: CbcBranchLotsize.cpp 2043 2014-07-01 13:03:51Z unxusr $ */
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 hi = bound_[1];
186        assert (hi >= bound_[0]);
187        for (i = 1; i < numberPoints; i++) {
188            double thisLo = points[sort[i] * 2];
189            double thisHi = points[sort[i] * 2 + 1];
190            assert (thisHi >= thisLo);
191            if (thisLo > hi) {
192                bound_[2*numberRanges_] = thisLo;
193                bound_[2*numberRanges_+1] = thisHi;
194                numberRanges_++;
195                hi = thisHi;
196            } else {
197                //overlap
198                hi = CoinMax(hi, thisHi);
199                bound_[2*numberRanges_-1] = hi;
200            }
201        }
202        // and for safety
203        bound_[2*numberRanges_] = bound_[2*numberRanges_-2];
204        bound_[2*numberRanges_+1] = bound_[2*numberRanges_-1];
205        for (i = 1; i < numberRanges_; i++) {
206            largestGap_ = CoinMax(largestGap_, bound_[2*i] - bound_[2*i-1]);
207        }
208    }
209    delete [] sort;
210    delete [] weight;
211    range_ = 0;
212}
213
214// Copy constructor
215CbcLotsize::CbcLotsize ( const CbcLotsize & rhs)
216        : CbcObject(rhs)
217
218{
219    columnNumber_ = rhs.columnNumber_;
220    rangeType_ = rhs.rangeType_;
221    numberRanges_ = rhs.numberRanges_;
222    range_ = rhs.range_;
223    largestGap_ = rhs.largestGap_;
224    if (numberRanges_) {
225        assert (rangeType_ > 0 && rangeType_ < 3);
226        bound_ = new double [(numberRanges_+1)*rangeType_];
227        memcpy(bound_, rhs.bound_, (numberRanges_ + 1)*rangeType_*sizeof(double));
228    } else {
229        bound_ = NULL;
230    }
231}
232
233// Clone
234CbcObject *
235CbcLotsize::clone() const
236{
237    return new CbcLotsize(*this);
238}
239
240// Assignment operator
241CbcLotsize &
242CbcLotsize::operator=( const CbcLotsize & rhs)
243{
244    if (this != &rhs) {
245        CbcObject::operator=(rhs);
246        columnNumber_ = rhs.columnNumber_;
247        rangeType_ = rhs.rangeType_;
248        numberRanges_ = rhs.numberRanges_;
249        largestGap_ = rhs.largestGap_;
250        delete [] bound_;
251        range_ = rhs.range_;
252        if (numberRanges_) {
253            assert (rangeType_ > 0 && rangeType_ < 3);
254            bound_ = new double [(numberRanges_+1)*rangeType_];
255            memcpy(bound_, rhs.bound_, (numberRanges_ + 1)*rangeType_*sizeof(double));
256        } else {
257            bound_ = NULL;
258        }
259    }
260    return *this;
261}
262
263// Destructor
264CbcLotsize::~CbcLotsize ()
265{
266    delete [] bound_;
267}
268/* Finds range of interest so value is feasible in range range_ or infeasible
269   between hi[range_] and lo[range_+1].  Returns true if feasible.
270*/
271bool
272CbcLotsize::findRange(double value) const
273{
274    assert (range_ >= 0 && range_ < numberRanges_ + 1);
275    double integerTolerance =
276        model_->getDblParam(CbcModel::CbcIntegerTolerance);
277    int iLo;
278    int iHi;
279    double infeasibility = 0.0;
280    if (rangeType_ == 1) {
281        if (value < bound_[range_] - integerTolerance) {
282            iLo = 0;
283            iHi = range_ - 1;
284        } else if (value < bound_[range_] + integerTolerance) {
285#if CBC_PRINT
286            printLotsize(value, true, 0);
287#endif
288            return true;
289        } else if (value < bound_[range_+1] - integerTolerance) {
290#ifdef CBC_PRINT
291            printLotsize(value, false, 0);
292#endif
293            return false;
294        } else {
295            iLo = range_ + 1;
296            iHi = numberRanges_ - 1;
297        }
298        // check lo and hi
299        bool found = false;
300        if (value > bound_[iLo] - integerTolerance && value < bound_[iLo+1] + integerTolerance) {
301            range_ = iLo;
302            found = true;
303        } else if (value > bound_[iHi] - integerTolerance && value < bound_[iHi+1] + integerTolerance) {
304            range_ = iHi;
305            found = true;
306        } else {
307            range_ = (iLo + iHi) >> 1;
308        }
309        //points
310        while (!found) {
311            if (value < bound_[range_]) {
312                if (value >= bound_[range_-1]) {
313                    // found
314                    range_--;
315                    break;
316                } else {
317                    iHi = range_;
318                }
319            } else {
320                if (value < bound_[range_+1]) {
321                    // found
322                    break;
323                } else {
324                    iLo = range_;
325                }
326            }
327            range_ = (iLo + iHi) >> 1;
328        }
329        if (value - bound_[range_] <= bound_[range_+1] - value) {
330            infeasibility = value - bound_[range_];
331        } else {
332            infeasibility = bound_[range_+1] - value;
333            if (infeasibility < integerTolerance)
334                range_++;
335        }
336#ifdef CBC_PRINT
337        printLotsize(value, (infeasibility < integerTolerance), 0);
338#endif
339        return (infeasibility < integerTolerance);
340    } else {
341        // ranges
342        if (value < bound_[2*range_] - integerTolerance) {
343            iLo = 0;
344            iHi = range_ - 1;
345        } else if (value < bound_[2*range_+1] + integerTolerance) {
346#ifdef CBC_PRINT
347            printLotsize(value, true, 0);
348#endif
349            return true;
350        } else if (value < bound_[2*range_+2] - integerTolerance) {
351#ifdef CBC_PRINT
352            printLotsize(value, false, 0);
353#endif
354            return false;
355        } else {
356            iLo = range_ + 1;
357            iHi = numberRanges_ - 1;
358        }
359        // check lo and hi
360        bool found = false;
361        if (value > bound_[2*iLo] - integerTolerance && value < bound_[2*iLo+2] - integerTolerance) {
362            range_ = iLo;
363            found = true;
364        } else if (value >= bound_[2*iHi] - integerTolerance) {
365            range_ = iHi;
366            found = true;
367        } else {
368            range_ = (iLo + iHi) >> 1;
369        }
370        //points
371        while (!found) {
372            if (value < bound_[2*range_]) {
373                if (value >= bound_[2*range_-2]) {
374                    // found
375                    range_--;
376                    break;
377                } else {
378                    iHi = range_;
379                }
380            } else {
381                if (value < bound_[2*range_+2]) {
382                    // found
383                    break;
384                } else {
385                    iLo = range_;
386                }
387            }
388            range_ = (iLo + iHi) >> 1;
389        }
390        if (value >= bound_[2*range_] - integerTolerance && value <= bound_[2*range_+1] + integerTolerance)
391            infeasibility = 0.0;
392        else if (value - bound_[2*range_+1] < bound_[2*range_+2] - value) {
393            infeasibility = value - bound_[2*range_+1];
394        } else {
395            infeasibility = bound_[2*range_+2] - value;
396        }
397#ifdef CBC_PRINT
398        printLotsize(value, (infeasibility < integerTolerance), 0);
399#endif
400        return (infeasibility < integerTolerance);
401    }
402}
403/* Returns floor and ceiling
404 */
405void
406CbcLotsize::floorCeiling(double & floorLotsize, double & ceilingLotsize, double value,
407                         double /*tolerance*/) const
408{
409    bool feasible = findRange(value);
410    if (rangeType_ == 1) {
411        floorLotsize = bound_[range_];
412        ceilingLotsize = bound_[range_+1];
413        // may be able to adjust
414        if (feasible && fabs(value - floorLotsize) > fabs(value - ceilingLotsize)) {
415            floorLotsize = bound_[range_+1];
416            ceilingLotsize = bound_[range_+2];
417        }
418    } else {
419        // ranges
420        assert (value >= bound_[2*range_+1]);
421        floorLotsize = bound_[2*range_+1];
422        ceilingLotsize = bound_[2*range_+2];
423    }
424}
425double
426CbcLotsize::infeasibility(const OsiBranchingInformation * /*info*/,
427                          int &preferredWay) const
428{
429    OsiSolverInterface * solver = model_->solver();
430    const double * solution = model_->testSolution();
431    const double * lower = solver->getColLower();
432    const double * upper = solver->getColUpper();
433    double value = solution[columnNumber_];
434    value = CoinMax(value, lower[columnNumber_]);
435    value = CoinMin(value, upper[columnNumber_]);
436    double integerTolerance =
437        model_->getDblParam(CbcModel::CbcIntegerTolerance);
438    /*printf("%d %g %g %g %g\n",columnNumber_,value,lower[columnNumber_],
439      solution[columnNumber_],upper[columnNumber_]);*/
440    assert (value >= bound_[0] - integerTolerance
441            && value <= bound_[rangeType_*numberRanges_-1] + integerTolerance);
442    double infeasibility = 0.0;
443    bool feasible = findRange(value);
444    if (!feasible) {
445        if (rangeType_ == 1) {
446            if (value - bound_[range_] < bound_[range_+1] - value) {
447                preferredWay = -1;
448                infeasibility = value - bound_[range_];
449            } else {
450                preferredWay = 1;
451                infeasibility = bound_[range_+1] - value;
452            }
453        } else {
454            // ranges
455            if (value - bound_[2*range_+1] < bound_[2*range_+2] - value) {
456                preferredWay = -1;
457                infeasibility = value - bound_[2*range_+1];
458            } else {
459                preferredWay = 1;
460                infeasibility = bound_[2*range_+2] - value;
461            }
462        }
463    } else {
464        // always satisfied
465        preferredWay = -1;
466    }
467    if (infeasibility < integerTolerance)
468        infeasibility = 0.0;
469    else
470        infeasibility /= largestGap_;
471#ifdef CBC_PRINT
472    printLotsize(value, infeasibility, 1);
473#endif
474    return infeasibility;
475}
476/* Column number if single column object -1 otherwise,
477   so returns >= 0
478   Used by heuristics
479*/
480int
481CbcLotsize::columnNumber() const
482{
483    return columnNumber_;
484}
485// This looks at solution and sets bounds to contain solution
486/** More precisely: it first forces the variable within the existing
487    bounds, and then tightens the bounds to make sure the variable is feasible
488*/
489void
490CbcLotsize::feasibleRegion()
491{
492    OsiSolverInterface * solver = model_->solver();
493    const double * lower = solver->getColLower();
494    const double * upper = solver->getColUpper();
495    const double * solution = model_->testSolution();
496    double value = solution[columnNumber_];
497    value = CoinMax(value, lower[columnNumber_]);
498    value = CoinMin(value, upper[columnNumber_]);
499    findRange(value);
500    double nearest;
501    if (rangeType_ == 1) {
502        nearest = bound_[range_];
503        solver->setColLower(columnNumber_, nearest);
504        solver->setColUpper(columnNumber_, nearest);
505    } else {
506        // ranges
507        solver->setColLower(columnNumber_, CoinMax(bound_[2*range_],
508                                                   lower[columnNumber_]));
509        solver->setColUpper(columnNumber_, CoinMin(bound_[2*range_+1],
510                                                   upper[columnNumber_]));
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#ifndef NDEBUG
744        { double olb, oub ;
745            olb = model_->solver()->getColLower()[iColumn] ;
746            oub = model_->solver()->getColUpper()[iColumn] ;
747#ifdef CBC_DEBUG
748            printf("branching down on var %d: [%g,%g] => [%g,%g]\n",
749                   iColumn, olb, oub, down_[0], down_[1]) ;
750#endif
751            assert (olb<down_[0]+1.0e-7&&oub>down_[1]-1.0e-7);
752        }
753#endif
754        model_->solver()->setColLower(iColumn, down_[0]);
755        model_->solver()->setColUpper(iColumn, down_[1]);
756        way_ = 1;
757    } else {
758#ifndef NDEBUG
759        { double olb, oub ;
760            olb = model_->solver()->getColLower()[iColumn] ;
761            oub = model_->solver()->getColUpper()[iColumn] ;
762#ifdef CBC_DEBUG
763            printf("branching up on var %d: [%g,%g] => [%g,%g]\n",
764                   iColumn, olb, oub, up_[0], up_[1]) ;
765#endif
766            assert (olb<up_[0]+1.0e-7&&oub>up_[1]-1.0e-7);
767        }
768#endif
769        model_->solver()->setColLower(iColumn, up_[0]);
770        model_->solver()->setColUpper(iColumn, up_[1]);
771        way_ = -1;        // Swap direction
772    }
773    return 0.0;
774}
775// Print
776void
777CbcLotsizeBranchingObject::print()
778{
779    int iColumn = variable_;
780    if (way_ < 0) {
781        {
782            double olb, oub ;
783            olb = model_->solver()->getColLower()[iColumn] ;
784            oub = model_->solver()->getColUpper()[iColumn] ;
785            printf("branching down on var %d: [%g,%g] => [%g,%g]\n",
786                   iColumn, olb, oub, down_[0], down_[1]) ;
787        }
788    } else {
789        {
790            double olb, oub ;
791            olb = model_->solver()->getColLower()[iColumn] ;
792            oub = model_->solver()->getColUpper()[iColumn] ;
793            printf("branching up on var %d: [%g,%g] => [%g,%g]\n",
794                   iColumn, olb, oub, up_[0], up_[1]) ;
795        }
796    }
797}
798
799/** Compare the \c this with \c brObj. \c this and \c brObj must be os the
800    same type and must have the same original object, but they may have
801    different feasible regions.
802    Return the appropriate CbcRangeCompare value (first argument being the
803    sub/superset if that's the case). In case of overlap (and if \c
804    replaceIfOverlap is true) replace the current branching object with one
805    whose feasible region is the overlap.
806*/
807CbcRangeCompare
808CbcLotsizeBranchingObject::compareBranchingObject
809(const CbcBranchingObject* brObj, const bool replaceIfOverlap)
810{
811    const CbcLotsizeBranchingObject* br =
812        dynamic_cast<const CbcLotsizeBranchingObject*>(brObj);
813    assert(br);
814    double* thisBd = way_ == -1 ? down_ : up_;
815    const double* otherBd = br->way_ == -1 ? br->down_ : br->up_;
816    return CbcCompareRanges(thisBd, otherBd, replaceIfOverlap);
817}
818
Note: See TracBrowser for help on using the repository browser.