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

Last change on this file since 2073 was 2073, checked in by forrest, 4 years ago

out fathomDone assert and fix debug compiler errors

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