source: trunk/Cbc/src/CbcBranchDynamic.cpp @ 1424

Last change on this file since 1424 was 1393, checked in by lou, 10 years ago

Mark #if 0 with JJF_ZERO and #if 1 with JJF_ONE as a historical reference
point.

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 28.3 KB
Line 
1/* $Id: CbcBranchDynamic.cpp 1393 2009-12-11 00:29:38Z forrest $ */
2// Copyright (C) 2002, International Business Machines
3// Corporation and others.  All Rights Reserved.
4#if defined(_MSC_VER)
5// Turn off compiler warning about long names
6#  pragma warning(disable:4786)
7#endif
8#include <cassert>
9#include <cstdlib>
10#include <cmath>
11#include <cfloat>
12//#define CBC_DEBUG
13//#define TRACE_ONE 19
14#include "OsiSolverInterface.hpp"
15#include "OsiSolverBranch.hpp"
16#include "CbcModel.hpp"
17#include "CbcMessage.hpp"
18#include "CbcBranchDynamic.hpp"
19#include "CoinSort.hpp"
20#include "CoinError.hpp"
21
22// Removing magic constants.
23
24// This is a very small number, added to something to make sure it's non-zero.
25// Useful, for example in denominators of ratios to avoid any possible division by zero
26# define nonZeroAmount 1.0e-30
27
28// Increasing the size of an array when it grows to the end of its alloted space.
29// In this file, only used for the history of the outcome of a branch.
30// New size is   size_scale_numerator* <old value> / size_scale_denominator + additive_size_increase.
31
32#define size_scale_numerator 3
33#define size_scale_denominator 2
34#define additive_size_increase 100
35
36// Explanation of options used in this file
37
38// TYPE2 defines a strategy for computing pseudocosts
39// 0 means to just use the absolute change in objective
40// 1 means use the relative change in objective
41// 2 means use a convex combination of absolute and relative objective changes
42
43// For option 2 (TYPE2 == 2), the specific combination is controlled by TYPERATIO
44// Includes a TYPERATIO fraction of the absolute change and (1 - TYPERATIO) fraction of
45// the relative change.  So should in general have 0 <= TYPERATIO <= 1.  But for the
46// equality cases, you're better off using the other strategy (TYPE2) options.
47
48#ifdef COIN_DEVELOP
49typedef struct {
50    double sumUp_;
51    double upEst_; // or change in obj in update
52    double sumDown_;
53    double downEst_; // or movement in value in update
54    int sequence_;
55    int numberUp_;
56    int numberUpInf_;
57    int numberDown_;
58    int numberDownInf_;
59    char where_;
60    char status_;
61} History;
62History * history = NULL;
63int numberHistory = 0;
64int maxHistory = 0;
65bool getHistoryStatistics_ = true;
66static void increaseHistory()
67{
68    if (numberHistory == maxHistory) {
69      // This was originally 3 * maxHistory/2 + 100
70        maxHistory = additive_size_increase + (size_scale_numerator * maxHistory) / size_scale_denominator;
71        History * temp = new History [maxHistory];
72        memcpy(temp, history, numberHistory*sizeof(History));
73        delete [] history;
74        history = temp;
75    }
76}
77static bool addRecord(History newOne)
78{
79    //if (!getHistoryStatistics_)
80    return false;
81    bool fromCompare = false;
82    int i;
83    for ( i = numberHistory - 1; i >= 0; i--) {
84        if (newOne.sequence_ != history[i].sequence_)
85            continue;
86        if (newOne.where_ != history[i].where_)
87            continue;
88        if (newOne.numberUp_ != history[i].numberUp_)
89            continue;
90        if (newOne.sumUp_ != history[i].sumUp_)
91            continue;
92        if (newOne.numberUpInf_ != history[i].numberUpInf_)
93            continue;
94        if (newOne.upEst_ != history[i].upEst_)
95            continue;
96        if (newOne.numberDown_ != history[i].numberDown_)
97            continue;
98        if (newOne.sumDown_ != history[i].sumDown_)
99            continue;
100        if (newOne.numberDownInf_ != history[i].numberDownInf_)
101            continue;
102        if (newOne.downEst_ != history[i].downEst_)
103            continue;
104        // If B knock out previous B
105        if (newOne.where_ == 'C') {
106            fromCompare = true;
107            if (newOne.status_ == 'B') {
108                int j;
109                for (j = i - 1; j >= 0; j--) {
110                    if (history[j].where_ == 'C') {
111                        if (history[j].status_ == 'I') {
112                            break;
113                        } else if (history[j].status_ == 'B') {
114                            history[j].status_ = ' ';
115                            break;
116                        }
117                    }
118                }
119            }
120            break;
121        }
122    }
123    if (i == -1 || fromCompare) {
124        //add
125        increaseHistory();
126        history[numberHistory++] = newOne;
127        return true;
128    } else {
129        return false;
130    }
131}
132#endif
133
134
135// Default Constructor
136CbcBranchDynamicDecision::CbcBranchDynamicDecision()
137        : CbcBranchDecision()
138{
139    bestCriterion_ = 0.0;
140    bestChangeUp_ = 0.0;
141    bestNumberUp_ = 0;
142    bestChangeDown_ = 0.0;
143    bestNumberDown_ = 0;
144    bestObject_ = NULL;
145}
146
147// Copy constructor
148CbcBranchDynamicDecision::CbcBranchDynamicDecision (
149    const CbcBranchDynamicDecision & rhs)
150        : CbcBranchDecision()
151{
152    bestCriterion_ = rhs.bestCriterion_;
153    bestChangeUp_ = rhs.bestChangeUp_;
154    bestNumberUp_ = rhs.bestNumberUp_;
155    bestChangeDown_ = rhs.bestChangeDown_;
156    bestNumberDown_ = rhs.bestNumberDown_;
157    bestObject_ = rhs.bestObject_;
158}
159
160CbcBranchDynamicDecision::~CbcBranchDynamicDecision()
161{
162}
163
164// Clone
165CbcBranchDecision *
166CbcBranchDynamicDecision::clone() const
167{
168    return new CbcBranchDynamicDecision(*this);
169}
170
171// Initialize i.e. before start of choosing at a node
172void
173CbcBranchDynamicDecision::initialize(CbcModel * /*model*/)
174{
175    bestCriterion_ = 0.0;
176    bestChangeUp_ = 0.0;
177    bestNumberUp_ = 0;
178    bestChangeDown_ = 0.0;
179    bestNumberDown_ = 0;
180    bestObject_ = NULL;
181#ifdef COIN_DEVELOP
182    History hist;
183    hist.where_ = 'C';
184    hist.status_ = 'I';
185    hist.sequence_ = 55555;
186    hist.numberUp_ = 0;
187    hist.numberUpInf_ = 0;
188    hist.sumUp_ = 0.0;
189    hist.upEst_ = 0.0;
190    hist.numberDown_ = 0;
191    hist.numberDownInf_ = 0;
192    hist.sumDown_ = 0.0;
193    hist.downEst_ = 0.0;
194    addRecord(hist);
195#endif
196}
197
198/* Saves a clone of current branching object.  Can be used to update
199      information on object causing branch - after branch */
200void
201CbcBranchDynamicDecision::saveBranchingObject(OsiBranchingObject * object)
202{
203    OsiBranchingObject * obj = object->clone();
204#ifndef NDEBUG
205    CbcBranchingObject * obj2 =
206        dynamic_cast<CbcBranchingObject *>(obj);
207    assert (obj2);
208#if COIN_DEVELOP>1
209    CbcDynamicPseudoCostBranchingObject * branchingObject =
210        dynamic_cast<CbcDynamicPseudoCostBranchingObject *>(obj);
211    if (!branchingObject)
212        printf("no dynamic branching object Dynamic Decision\n");
213#endif
214#else
215    CbcBranchingObject * obj2 =
216        static_cast<CbcBranchingObject *>(obj);
217#endif
218    //object_=branchingObject;
219    object_ = obj2;
220}
221/* Pass in information on branch just done.
222   assumes object can get information from solver */
223/*
224  The expectation is that this method will be called after the branch has been
225  imposed on the constraint system and resolve() has executed.
226
227  Note that the CbcBranchDecision is a property of the CbcModel. Note also that
228  this method is reaching right through the CbcBranchingObject to update
229  information in the underlying CbcObject. That's why we delete the
230  branchingObject at the end of the method --- the next time we're called,
231  the CbcObject will be different.
232*/
233void
234CbcBranchDynamicDecision::updateInformation(OsiSolverInterface * solver,
235        const CbcNode * node)
236{
237    assert (object_);
238    const CbcModel * model = object_->model();
239    double originalValue = node->objectiveValue();
240    int originalUnsatisfied = node->numberUnsatisfied();
241    double objectiveValue = solver->getObjValue() * model->getObjSense();
242    int unsatisfied = 0;
243    int i;
244    int numberIntegers = model->numberIntegers();;
245    const double * solution = solver->getColSolution();
246    //const double * lower = solver->getColLower();
247    //const double * upper = solver->getColUpper();
248        /*
249         Gain access to the associated CbcBranchingObject and its underlying
250         CbcObject.
251
252         Seems like we'd want to distinguish between no branching object and a
253         branching object of the wrong type. Just deleting an object of the wrong
254         type hides many sins.
255
256         Hmmm ... if we're using the OSI side of the hierarchy, is this indicated by a
257         null object_? Nah, then we have an assert failure off the top.
258        */
259
260    CbcDynamicPseudoCostBranchingObject * branchingObject =
261        dynamic_cast<CbcDynamicPseudoCostBranchingObject *>(object_);
262    if (!branchingObject) {
263        delete object_;
264        object_ = NULL;
265        return;
266    }
267    CbcSimpleIntegerDynamicPseudoCost *  object = branchingObject->object();
268    /*
269        change is the change in objective due to the branch we've just imposed. It's
270        possible we may have gone infeasible.
271        */
272        double change = CoinMax(0.0, objectiveValue - originalValue);
273    // probably should also ignore if stopped
274        // FIXME. Could use enum to avoid numbers for iStatus (e.g. optimal, unknown, infeasible)
275    int iStatus;
276    if (solver->isProvenOptimal())
277        iStatus = 0; // optimal
278    else if (solver->isIterationLimitReached()
279             && !solver->isDualObjectiveLimitReached())
280        iStatus = 2; // unknown
281    else
282        iStatus = 1; // infeasible
283        /*
284          If we're feasible according to the solver, evaluate integer feasibility.
285        */
286    bool feasible = iStatus != 1;
287    if (feasible) {
288        double integerTolerance =
289            model->getDblParam(CbcModel::CbcIntegerTolerance);
290        const int * integerVariable = model->integerVariable();
291        for (i = 0; i < numberIntegers; i++) {
292            int j = integerVariable[i];
293            double value = solution[j];
294            double nearest = floor(value + 0.5);
295            if (fabs(value - nearest) > integerTolerance)
296                unsatisfied++;
297        }
298    }
299        /*
300          Finally, update the object. Defaults (080104) are TYPE2 = 0, INFEAS = 1.
301
302          Pseudocosts are at heart the average of actual costs for a branch. We just
303          need to update the information used to calculate that average.
304        */
305    int way = object_->way();
306    double value = object_->value();
307    //#define TYPE2 1
308    //#define TYPERATIO 0.9
309    if (way < 0) {
310        // down
311        if (feasible) {
312            double movement = value - floor(value);
313            movement = CoinMax(movement, MINIMUM_MOVEMENT);
314            //printf("(down change %g value down %g ",change,movement);
315            object->incrementNumberTimesDown();
316            object->addToSumDownChange(nonZeroAmount + movement);
317            object->addToSumDownDecrease(originalUnsatisfied - unsatisfied);
318#if TYPE2==0
319            object->addToSumDownCost(change / (nonZeroAmount + movement));
320            object->setDownDynamicPseudoCost(object->sumDownCost() /
321                                             static_cast<double> (object->numberTimesDown()));
322#elif TYPE2==1
323            object->addToSumDownCost(change);
324            object->setDownDynamicPseudoCost(object->sumDownCost() / object->sumDownChange());
325#elif TYPE2==2
326            object->addToSumDownCost(change*TYPERATIO + (1.0 - TYPERATIO)*change / (nonZeroAmount + movement));
327            object->setDownDynamicPseudoCost(object->sumDownCost()*(TYPERATIO / object->sumDownChange() + (1.0 - TYPERATIO) / (double) object->numberTimesDown()));
328#endif
329        } else {
330            //printf("(down infeasible value down %g ",change,movement);
331            object->incrementNumberTimesDown();
332            object->incrementNumberTimesDownInfeasible();
333#if INFEAS==2
334            double distanceToCutoff = 0.0;
335            double objectiveValue = model->getCurrentMinimizationObjValue();
336            distanceToCutoff =  model->getCutoff()  - originalValue;
337            if (distanceToCutoff < 1.0e20)
338                change = distanceToCutoff * 2.0;
339            else
340                change = object->downDynamicPseudoCost() * movement * 10.0;
341            change = CoinMax(1.0e-12 * (1.0 + fabs(originalValue)), change);
342            object->addToSumDownChange(nonZeroAmount + movement);
343            object->addToSumDownDecrease(originalUnsatisfied - unsatisfied);
344#if TYPE2==0
345            object->addToSumDownCost(change / (nonZeroAmount + movement));
346            object->setDownDynamicPseudoCost(object->sumDownCost() / (double) object->numberTimesDown());
347#elif TYPE2==1
348            object->addToSumDownCost(change);
349            object->setDownDynamicPseudoCost(object->sumDownCost() / object->sumDownChange());
350#elif TYPE2==2
351            object->addToSumDownCost(change*TYPERATIO + (1.0 - TYPERATIO)*change / (nonZeroAmount + movement));
352            object->setDownDynamicPseudoCost(object->sumDownCost()*(TYPERATIO / object->sumDownChange() + (1.0 - TYPERATIO) / (double) object->numberTimesDown()));
353#endif
354#endif
355        }
356    } else {
357        // up
358        if (feasible) {
359            double movement = ceil(value) - value;
360            movement = CoinMax(movement, MINIMUM_MOVEMENT);
361            //printf("(up change %g value down %g ",change,movement);
362            object->incrementNumberTimesUp();
363            object->addToSumUpChange(nonZeroAmount + movement);
364            object->addToSumUpDecrease(unsatisfied - originalUnsatisfied);
365#if TYPE2==0
366            object->addToSumUpCost(change / (nonZeroAmount + movement));
367            object->setUpDynamicPseudoCost(object->sumUpCost() /
368                                           static_cast<double> (object->numberTimesUp()));
369#elif TYPE2==1
370            object->addToSumUpCost(change);
371            object->setUpDynamicPseudoCost(object->sumUpCost() / object->sumUpChange());
372#elif TYPE2==2
373            object->addToSumUpCost(change*TYPERATIO + (1.0 - TYPERATIO)*change / (nonZeroAmount + movement));
374            object->setUpDynamicPseudoCost(object->sumUpCost()*(TYPERATIO / object->sumUpChange() + (1.0 - TYPERATIO) / (double) object->numberTimesUp()));
375#endif
376        } else {
377            //printf("(up infeasible value down %g ",change,movement);
378            object->incrementNumberTimesUp();
379            object->incrementNumberTimesUpInfeasible();
380#if INFEAS==2
381            double distanceToCutoff = 0.0;
382            double objectiveValue = model->getCurrentMinimizationObjValue();
383            distanceToCutoff =  model->getCutoff()  - originalValue;
384            if (distanceToCutoff < 1.0e20)
385                change = distanceToCutoff * 2.0;
386            else
387                change = object->upDynamicPseudoCost() * movement * 10.0;
388            change = CoinMax(1.0e-12 * (1.0 + fabs(originalValue)), change);
389            object->addToSumUpChange(nonZeroAmount + movement);
390            object->addToSumUpDecrease(unsatisfied - originalUnsatisfied);
391#if TYPE2==0
392            object->addToSumUpCost(change / (nonZeroAmount + movement));
393            object->setUpDynamicPseudoCost(object->sumUpCost() / (double) object->numberTimesUp());
394#elif TYPE2==1
395            object->addToSumUpCost(change);
396            object->setUpDynamicPseudoCost(object->sumUpCost() / object->sumUpChange());
397#elif TYPE2==2
398            object->addToSumUpCost(change*TYPERATIO + (1.0 - TYPERATIO)*change / (nonZeroAmount + movement));
399            object->setUpDynamicPseudoCost(object->sumUpCost()*(TYPERATIO / object->sumUpChange() + (1.0 - TYPERATIO) / (double) object->numberTimesUp()));
400#endif
401#endif
402        }
403    }
404    //object->print(1,0.5);
405    delete object_;
406    object_ = NULL;
407}
408
409/*
410  Simple dynamic decision algorithm. Compare based on infeasibility (numInfUp,
411  numInfDown) until a solution is found by search, then switch to change in
412  objective (changeUp, changeDown). Note that bestSoFar is remembered in
413  bestObject_, so the parameter bestSoFar is unused.
414*/
415
416int
417CbcBranchDynamicDecision::betterBranch(CbcBranchingObject * thisOne,
418                                       CbcBranchingObject * /*bestSoFar*/,
419                                       double changeUp, int numInfUp,
420                                       double changeDown, int numInfDown)
421{
422    CbcModel * model = thisOne->model();
423    int stateOfSearch = model->stateOfSearch() % 10;
424    int betterWay = 0;
425    double value = 0.0;
426    if (!bestObject_) {
427        bestCriterion_ = -1.0e30;
428        bestNumberUp_ = COIN_INT_MAX;
429        bestNumberDown_ = COIN_INT_MAX;
430    }
431    // maybe branch up more if no solution or not many nodes done?
432    if (stateOfSearch <= 2) {
433        //#define TRY_STUFF 1
434#ifdef TRY_STUFF
435        // before solution - choose smallest number
436        // could add in depth as well
437        int bestNumber = CoinMin(bestNumberUp_, bestNumberDown_);
438        if (numInfUp < numInfDown) {
439            if (numInfUp < bestNumber) {
440                betterWay = 1;
441            } else if (numInfUp == bestNumber) {
442                if (changeUp < bestChangeUp_)
443                    betterWay = 1;
444            }
445        } else if (numInfUp > numInfDown) {
446            if (numInfDown < bestNumber) {
447                betterWay = -1;
448            } else if (numInfDown == bestNumber) {
449                if (changeDown < bestChangeDown_)
450                    betterWay = -1;
451            }
452        } else {
453            // up and down have same number
454            bool better = false;
455            if (numInfUp < bestNumber) {
456                better = true;
457            } else if (numInfUp == bestNumber) {
458                if (CoinMin(changeUp, changeDown) < CoinMin(bestChangeUp_, bestChangeDown_) - 1.0e-5)
459                    better = true;;
460            }
461            if (better) {
462                // see which way
463                if (changeUp <= changeDown)
464                    betterWay = 1;
465                else
466                    betterWay = -1;
467            }
468        }
469        if (betterWay) {
470            value = CoinMin(numInfUp, numInfDown);
471        }
472#else
473        // use pseudo shadow prices modified by locks
474        // test testosi
475#ifndef JJF_ONE
476        double objectiveValue = model->getCurrentMinimizationObjValue();
477        double distanceToCutoff =  model->getCutoff()  - objectiveValue;
478        if (distanceToCutoff < 1.0e20)
479            distanceToCutoff *= 10.0;
480        else
481            distanceToCutoff = 1.0e2 + fabs(objectiveValue);
482        distanceToCutoff = CoinMax(distanceToCutoff, 1.0e-12 * (1.0 + fabs(objectiveValue)));
483        double continuousObjective = model->getContinuousObjective();
484        double distanceToCutoffC =  model->getCutoff()  - continuousObjective;
485        if (distanceToCutoffC > 1.0e20)
486            distanceToCutoffC = 1.0e2 + fabs(objectiveValue);
487        distanceToCutoffC = CoinMax(distanceToCutoffC, 1.0e-12 * (1.0 + fabs(objectiveValue)));
488        int numberInfC = model->getContinuousInfeasibilities();
489        double perInf = distanceToCutoffC / static_cast<double> (numberInfC);
490        assert (perInf > 0.0);
491        //int numberIntegers = model->numberIntegers();
492        changeDown += perInf * numInfDown;
493        changeUp += perInf * numInfUp;
494#ifdef JJF_ZERO
495        if (numInfDown == 1) {
496            if (numInfUp == 1) {
497                changeUp += 1.0e6;
498                changeDown += 1.0e6;
499            } else if (changeDown <= 1.5*changeUp) {
500                changeUp += 1.0e6;
501            }
502        } else if (numInfUp == 1 && changeUp <= 1.5*changeDown) {
503            changeDown += 1.0e6;
504        }
505#endif
506#endif
507        double minValue = CoinMin(changeDown, changeUp);
508        double maxValue = CoinMax(changeDown, changeUp);
509        value = WEIGHT_BEFORE * minValue + (1.0 - WEIGHT_BEFORE) * maxValue;
510        if (value > bestCriterion_ + 1.0e-8) {
511            if (changeUp <= 1.5*changeDown) {
512                betterWay = 1;
513            } else {
514                betterWay = -1;
515            }
516        }
517#endif
518    } else {
519#define TRY_STUFF 2
520#if TRY_STUFF > 1
521        // Get current number of infeasibilities, cutoff and current objective
522        CbcNode * node = model->currentNode();
523        int numberUnsatisfied = node->numberUnsatisfied();
524        double cutoff = model->getCutoff();
525        double objectiveValue = node->objectiveValue();
526#endif
527        // got a solution
528        double minValue = CoinMin(changeDown, changeUp);
529        double maxValue = CoinMax(changeDown, changeUp);
530        // Reduce
531#ifdef TRY_STUFF
532        //maxValue = CoinMin(maxValue,minValue*4.0);
533#else
534        //maxValue = CoinMin(maxValue,minValue*2.0);
535#endif
536#ifndef WEIGHT_PRODUCT
537        value = WEIGHT_AFTER * minValue + (1.0 - WEIGHT_AFTER) * maxValue;
538#else
539        double minProductWeight = model->getDblParam(CbcModel::CbcSmallChange);
540        value = CoinMax(minValue, minProductWeight) * CoinMax(maxValue, minProductWeight);
541        //value += minProductWeight*minValue;
542#endif
543        double useValue = value;
544        double useBest = bestCriterion_;
545#if TRY_STUFF>1
546        int thisNumber = CoinMin(numInfUp, numInfDown);
547        int bestNumber = CoinMin(bestNumberUp_, bestNumberDown_);
548        double distance = cutoff - objectiveValue;
549        assert (distance >= 0.0);
550        if (useValue + 0.1*distance > useBest && useValue*1.1 > useBest &&
551                useBest + 0.1*distance > useValue && useBest*1.1 > useValue) {
552            // not much in it - look at unsatisfied
553            if (thisNumber < numberUnsatisfied || bestNumber < numberUnsatisfied) {
554                double perInteger = distance / (static_cast<double> (numberUnsatisfied));
555                useValue += thisNumber * perInteger;
556                useBest += bestNumber * perInteger;
557            }
558        }
559#endif
560        if (useValue > useBest + 1.0e-8) {
561            if (changeUp <= 1.5*changeDown) {
562                betterWay = 1;
563            } else {
564                betterWay = -1;
565            }
566        }
567    }
568#ifdef COIN_DEVELOP
569    History hist;
570    {
571        CbcDynamicPseudoCostBranchingObject * branchingObject =
572            dynamic_cast<CbcDynamicPseudoCostBranchingObject *>(thisOne);
573        if (branchingObject) {
574            CbcSimpleIntegerDynamicPseudoCost *  object = branchingObject->object();
575            assert (object);
576            hist.where_ = 'C';
577            hist.status_ = ' ';
578            hist.sequence_ = object->columnNumber();
579            hist.numberUp_ = object->numberTimesUp();
580            hist.numberUpInf_ = numInfUp;
581            hist.sumUp_ = object->sumUpCost();
582            hist.upEst_ = changeUp;
583            hist.numberDown_ = object->numberTimesDown();
584            hist.numberDownInf_ = numInfDown;
585            hist.sumDown_ = object->sumDownCost();
586            hist.downEst_ = changeDown;
587        }
588    }
589#endif
590    if (betterWay) {
591#ifdef COIN_DEVELOP
592        hist.status_ = 'B';
593#endif
594        // maybe change better way
595        CbcDynamicPseudoCostBranchingObject * branchingObject =
596            dynamic_cast<CbcDynamicPseudoCostBranchingObject *>(thisOne);
597        if (branchingObject) {
598            CbcSimpleIntegerDynamicPseudoCost *  object = branchingObject->object();
599            double separator = object->upDownSeparator();
600            if (separator > 0.0) {
601                const double * solution = thisOne->model()->testSolution();
602                double valueVariable = solution[object->columnNumber()];
603                betterWay = (valueVariable - floor(valueVariable) >= separator) ? 1 : -1;
604            }
605        }
606        bestCriterion_ = value;
607        bestChangeUp_ = changeUp;
608        bestNumberUp_ = numInfUp;
609        bestChangeDown_ = changeDown;
610        bestNumberDown_ = numInfDown;
611        bestObject_ = thisOne;
612        // See if user is overriding way
613        if (thisOne->object() && thisOne->object()->preferredWay())
614            betterWay = thisOne->object()->preferredWay();
615    }
616#ifdef COIN_DEVELOP
617    addRecord(hist);
618#endif
619    return betterWay;
620}
621/* Sets or gets best criterion so far */
622void
623CbcBranchDynamicDecision::setBestCriterion(double value)
624{
625    bestCriterion_ = value;
626}
627double
628CbcBranchDynamicDecision::getBestCriterion() const
629{
630    return bestCriterion_;
631}
632#ifdef COIN_DEVELOP
633void printHistory(const char * file)
634{
635    if (!numberHistory)
636        return;
637    FILE * fp = fopen(file, "w");
638    assert(fp);
639    int numberIntegers = 0;
640    int i;
641    for (i = 0; i < numberHistory; i++) {
642        if (history[i].where_ != 'C' || history[i].status_ != 'I')
643            numberIntegers = CoinMax(numberIntegers, history[i].sequence_);
644    }
645    numberIntegers++;
646    for (int iC = 0; iC < numberIntegers; iC++) {
647        int n = 0;
648        for (i = 0; i < numberHistory; i++) {
649            if (history[i].sequence_ == iC) {
650                if (!n)
651                    fprintf(fp, "XXX %d\n", iC);
652                n++;
653                fprintf(fp, "%c%c up %8d %8d %12.5f %12.5f down  %8d %8d %12.5f %12.5f\n",
654                        history[i].where_,
655                        history[i].status_,
656                        history[i].numberUp_,
657                        history[i].numberUpInf_,
658                        history[i].sumUp_,
659                        history[i].upEst_,
660                        history[i].numberDown_,
661                        history[i].numberDownInf_,
662                        history[i].sumDown_,
663                        history[i].downEst_);
664            }
665        }
666    }
667    fclose(fp);
668}
669#endif
670
671// Default Constructor
672CbcDynamicPseudoCostBranchingObject::CbcDynamicPseudoCostBranchingObject()
673        : CbcIntegerBranchingObject()
674{
675    changeInGuessed_ = 1.0e-5;
676    object_ = NULL;
677}
678
679// Useful constructor
680CbcDynamicPseudoCostBranchingObject::CbcDynamicPseudoCostBranchingObject (CbcModel * model,
681        int variable,
682        int way , double value,
683        CbcSimpleIntegerDynamicPseudoCost * object)
684        : CbcIntegerBranchingObject(model, variable, way, value)
685{
686    changeInGuessed_ = 1.0e-5;
687    object_ = object;
688}
689// Does part of work for constructor
690void
691CbcDynamicPseudoCostBranchingObject::fillPart (int variable,
692        int way , double value,
693        CbcSimpleIntegerDynamicPseudoCost * object)
694{
695    CbcIntegerBranchingObject::fillPart(variable, way, value);
696    changeInGuessed_ = 1.0e-5;
697    object_ = object;
698}
699// Useful constructor for fixing
700CbcDynamicPseudoCostBranchingObject::CbcDynamicPseudoCostBranchingObject (CbcModel * model,
701        int variable, int way,
702        double lowerValue,
703        double /*upperValue*/)
704        : CbcIntegerBranchingObject(model, variable, way, lowerValue)
705{
706    changeInGuessed_ = 1.0e100;
707    object_ = NULL;
708}
709
710
711// Copy constructor
712CbcDynamicPseudoCostBranchingObject::CbcDynamicPseudoCostBranchingObject (
713    const CbcDynamicPseudoCostBranchingObject & rhs)
714        : CbcIntegerBranchingObject(rhs)
715{
716    changeInGuessed_ = rhs.changeInGuessed_;
717    object_ = rhs.object_;
718}
719
720// Assignment operator
721CbcDynamicPseudoCostBranchingObject &
722CbcDynamicPseudoCostBranchingObject::operator=( const CbcDynamicPseudoCostBranchingObject & rhs)
723{
724    if (this != &rhs) {
725        CbcIntegerBranchingObject::operator=(rhs);
726        changeInGuessed_ = rhs.changeInGuessed_;
727        object_ = rhs.object_;
728    }
729    return *this;
730}
731CbcBranchingObject *
732CbcDynamicPseudoCostBranchingObject::clone() const
733{
734    return (new CbcDynamicPseudoCostBranchingObject(*this));
735}
736
737// Destructor
738CbcDynamicPseudoCostBranchingObject::~CbcDynamicPseudoCostBranchingObject ()
739{
740}
741
742/*
743  Perform a branch by adjusting the bounds of the specified variable. Note
744  that each arm of the branch advances the object to the next arm by
745  advancing the value of way_.
746
747  Providing new values for the variable's lower and upper bounds for each
748  branching direction gives a little bit of additional flexibility and will
749  be easily extensible to multi-way branching.
750  Returns change in guessed objective on next branch
751*/
752double
753CbcDynamicPseudoCostBranchingObject::branch()
754{
755    CbcIntegerBranchingObject::branch();
756    return changeInGuessed_;
757}
758/* Some branchingObjects may claim to be able to skip
759   strong branching.  If so they have to fill in CbcStrongInfo.
760   The object mention in incoming CbcStrongInfo must match.
761   Returns nonzero if skip is wanted */
762int
763CbcDynamicPseudoCostBranchingObject::fillStrongInfo( CbcStrongInfo & info)
764{
765    assert (object_);
766    assert (info.possibleBranch == this);
767    info.upMovement = object_->upDynamicPseudoCost() * (ceil(value_) - value_);
768    info.downMovement = object_->downDynamicPseudoCost() * (value_ - floor(value_));
769    info.numIntInfeasUp  -= static_cast<int> (object_->sumUpDecrease() /
770                            (1.0e-12 + static_cast<double> (object_->numberTimesUp())));
771    info.numIntInfeasUp = CoinMax(info.numIntInfeasUp, 0);
772    info.numObjInfeasUp = 0;
773    info.finishedUp = false;
774    info.numItersUp = 0;
775    info.numIntInfeasDown  -= static_cast<int> (object_->sumDownDecrease() /
776                              (1.0e-12 + static_cast<double> (object_->numberTimesDown())));
777    info.numIntInfeasDown = CoinMax(info.numIntInfeasDown, 0);
778    info.numObjInfeasDown = 0;
779    info.finishedDown = false;
780    info.numItersDown = 0;
781    info.fix = 0;
782    if (object_->numberTimesUp() < object_->numberBeforeTrust() +
783            2*object_->numberTimesUpInfeasible() ||
784            object_->numberTimesDown() < object_->numberBeforeTrust() +
785            2*object_->numberTimesDownInfeasible()) {
786        return 0;
787    } else {
788        return 1;
789    }
790}
Note: See TracBrowser for help on using the repository browser.