source: trunk/Cbc/src/CbcBranchDynamic.cpp

Last change on this file was 2467, checked in by unxusr, 11 months ago

spaces after angles

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 25.9 KB
Line 
1/* $Id: CbcBranchDynamic.cpp 2467 2019-01-03 21:26:29Z 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//#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// Default Constructor
137CbcBranchDynamicDecision::CbcBranchDynamicDecision()
138  : CbcBranchDecision()
139{
140  bestCriterion_ = 0.0;
141  bestChangeUp_ = 0.0;
142  bestNumberUp_ = 0;
143  bestChangeDown_ = 0.0;
144  bestNumberDown_ = 0;
145  bestObject_ = NULL;
146}
147
148// Copy constructor
149CbcBranchDynamicDecision::CbcBranchDynamicDecision(
150  const CbcBranchDynamicDecision &rhs)
151  : CbcBranchDecision()
152{
153  bestCriterion_ = rhs.bestCriterion_;
154  bestChangeUp_ = rhs.bestChangeUp_;
155  bestNumberUp_ = rhs.bestNumberUp_;
156  bestChangeDown_ = rhs.bestChangeDown_;
157  bestNumberDown_ = rhs.bestNumberDown_;
158  bestObject_ = rhs.bestObject_;
159}
160
161CbcBranchDynamicDecision::~CbcBranchDynamicDecision()
162{
163}
164
165// Clone
166CbcBranchDecision *
167CbcBranchDynamicDecision::clone() const
168{
169  return new CbcBranchDynamicDecision(*this);
170}
171
172// Initialize i.e. before start of choosing at a node
173void CbcBranchDynamicDecision::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 CbcBranchDynamicDecision::saveBranchingObject(OsiBranchingObject *object)
201{
202  OsiBranchingObject *obj = object->clone();
203#ifndef NDEBUG
204  CbcBranchingObject *obj2 = dynamic_cast< CbcBranchingObject * >(obj);
205  assert(obj2);
206#if COIN_DEVELOP > 1
207  CbcDynamicPseudoCostBranchingObject *branchingObject = dynamic_cast< CbcDynamicPseudoCostBranchingObject * >(obj);
208  if (!branchingObject)
209    printf("no dynamic branching object Dynamic Decision\n");
210#endif
211#else
212  CbcBranchingObject *obj2 = static_cast< CbcBranchingObject * >(obj);
213#endif
214  //object_=branchingObject;
215  object_ = obj2;
216}
217/* Pass in information on branch just done.
218   assumes object can get information from solver */
219/*
220  The expectation is that this method will be called after the branch has been
221  imposed on the constraint system and resolve() has executed.
222
223  Note that the CbcBranchDecision is a property of the CbcModel. Note also that
224  this method is reaching right through the CbcBranchingObject to update
225  information in the underlying CbcObject. That's why we delete the
226  branchingObject at the end of the method --- the next time we're called,
227  the CbcObject will be different.
228*/
229void CbcBranchDynamicDecision::updateInformation(OsiSolverInterface *solver,
230  const CbcNode *node)
231{
232  assert(object_);
233  const CbcModel *model = object_->model();
234  double originalValue = node->objectiveValue();
235  int originalUnsatisfied = node->numberUnsatisfied();
236  double objectiveValue = solver->getObjValue() * model->getObjSense();
237  int unsatisfied = 0;
238  int i;
239  int numberIntegers = model->numberIntegers();
240  ;
241  const double *solution = solver->getColSolution();
242  //const double * lower = solver->getColLower();
243  //const double * upper = solver->getColUpper();
244  /*
245         Gain access to the associated CbcBranchingObject and its underlying
246         CbcObject.
247
248         Seems like we'd want to distinguish between no branching object and a
249         branching object of the wrong type. Just deleting an object of the wrong
250         type hides many sins.
251
252         Hmmm ... if we're using the OSI side of the hierarchy, is this indicated by a
253         null object_? Nah, then we have an assert failure off the top.
254        */
255
256  CbcDynamicPseudoCostBranchingObject *branchingObject = dynamic_cast< CbcDynamicPseudoCostBranchingObject * >(object_);
257  if (!branchingObject) {
258    delete object_;
259    object_ = NULL;
260    return;
261  }
262  CbcSimpleIntegerDynamicPseudoCost *object = branchingObject->object();
263  /*
264        change is the change in objective due to the branch we've just imposed. It's
265        possible we may have gone infeasible.
266        */
267  double change = CoinMax(0.0, objectiveValue - originalValue);
268  // probably should also ignore if stopped
269  // FIXME. Could use enum to avoid numbers for iStatus (e.g. optimal, unknown, infeasible)
270  int iStatus;
271  if (solver->isProvenOptimal())
272    iStatus = 0; // optimal
273  else if (solver->isIterationLimitReached()
274    && !solver->isDualObjectiveLimitReached())
275    iStatus = 2; // unknown
276  else
277    iStatus = 1; // infeasible
278  /*
279          If we're feasible according to the solver, evaluate integer feasibility.
280        */
281  bool feasible = iStatus != 1;
282  if (feasible) {
283    double integerTolerance = model->getDblParam(CbcModel::CbcIntegerTolerance);
284    const int *integerVariable = model->integerVariable();
285    for (i = 0; i < numberIntegers; i++) {
286      int j = integerVariable[i];
287      double value = solution[j];
288      double nearest = floor(value + 0.5);
289      if (fabs(value - nearest) > integerTolerance)
290        unsatisfied++;
291    }
292  }
293  /*
294          Finally, update the object. Defaults (080104) are TYPE2 = 0, INFEAS = 1.
295
296          Pseudocosts are at heart the average of actual costs for a branch. We just
297          need to update the information used to calculate that average.
298        */
299  int way = object_->way();
300  double value = object_->value();
301  //#define TYPE2 1
302  //#define TYPERATIO 0.9
303  if (way < 0) {
304    // down
305    if (feasible) {
306      double movement = value - floor(value);
307      movement = CoinMax(movement, MINIMUM_MOVEMENT);
308      //printf("(down change %g value down %g ",change,movement);
309      object->incrementNumberTimesDown();
310      object->addToSumDownChange(nonZeroAmount + movement);
311      object->addToSumDownDecrease(originalUnsatisfied - unsatisfied);
312#if TYPE2 == 0
313      object->addToSumDownCost(change / (nonZeroAmount + movement));
314      object->setDownDynamicPseudoCost(object->sumDownCost() / static_cast< double >(object->numberTimesDown()));
315#elif TYPE2 == 1
316      object->addToSumDownCost(change);
317      object->setDownDynamicPseudoCost(object->sumDownCost() / object->sumDownChange());
318#elif TYPE2 == 2
319      object->addToSumDownCost(change * TYPERATIO + (1.0 - TYPERATIO) * change / (nonZeroAmount + movement));
320      object->setDownDynamicPseudoCost(object->sumDownCost() * (TYPERATIO / object->sumDownChange() + (1.0 - TYPERATIO) / (double)object->numberTimesDown()));
321#endif
322    } else {
323      //printf("(down infeasible value down %g ",change,movement);
324      object->incrementNumberTimesDown();
325      object->incrementNumberTimesDownInfeasible();
326#if INFEAS == 2
327      double distanceToCutoff = 0.0;
328      double objectiveValue = model->getCurrentMinimizationObjValue();
329      distanceToCutoff = model->getCutoff() - originalValue;
330      if (distanceToCutoff < 1.0e20)
331        change = distanceToCutoff * 2.0;
332      else
333        change = object->downDynamicPseudoCost() * movement * 10.0;
334      change = CoinMax(1.0e-12 * (1.0 + fabs(originalValue)), change);
335      object->addToSumDownChange(nonZeroAmount + movement);
336      object->addToSumDownDecrease(originalUnsatisfied - unsatisfied);
337#if TYPE2 == 0
338      object->addToSumDownCost(change / (nonZeroAmount + movement));
339      object->setDownDynamicPseudoCost(object->sumDownCost() / (double)object->numberTimesDown());
340#elif TYPE2 == 1
341      object->addToSumDownCost(change);
342      object->setDownDynamicPseudoCost(object->sumDownCost() / object->sumDownChange());
343#elif TYPE2 == 2
344      object->addToSumDownCost(change * TYPERATIO + (1.0 - TYPERATIO) * change / (nonZeroAmount + movement));
345      object->setDownDynamicPseudoCost(object->sumDownCost() * (TYPERATIO / object->sumDownChange() + (1.0 - TYPERATIO) / (double)object->numberTimesDown()));
346#endif
347#endif
348    }
349  } else {
350    // up
351    if (feasible) {
352      double movement = ceil(value) - value;
353      movement = CoinMax(movement, MINIMUM_MOVEMENT);
354      //printf("(up change %g value down %g ",change,movement);
355      object->incrementNumberTimesUp();
356      object->addToSumUpChange(nonZeroAmount + movement);
357      object->addToSumUpDecrease(unsatisfied - originalUnsatisfied);
358#if TYPE2 == 0
359      object->addToSumUpCost(change / (nonZeroAmount + movement));
360      object->setUpDynamicPseudoCost(object->sumUpCost() / static_cast< double >(object->numberTimesUp()));
361#elif TYPE2 == 1
362      object->addToSumUpCost(change);
363      object->setUpDynamicPseudoCost(object->sumUpCost() / object->sumUpChange());
364#elif TYPE2 == 2
365      object->addToSumUpCost(change * TYPERATIO + (1.0 - TYPERATIO) * change / (nonZeroAmount + movement));
366      object->setUpDynamicPseudoCost(object->sumUpCost() * (TYPERATIO / object->sumUpChange() + (1.0 - TYPERATIO) / (double)object->numberTimesUp()));
367#endif
368    } else {
369      //printf("(up infeasible value down %g ",change,movement);
370      object->incrementNumberTimesUp();
371      object->incrementNumberTimesUpInfeasible();
372#if INFEAS == 2
373      double distanceToCutoff = 0.0;
374      double objectiveValue = model->getCurrentMinimizationObjValue();
375      distanceToCutoff = model->getCutoff() - originalValue;
376      if (distanceToCutoff < 1.0e20)
377        change = distanceToCutoff * 2.0;
378      else
379        change = object->upDynamicPseudoCost() * movement * 10.0;
380      change = CoinMax(1.0e-12 * (1.0 + fabs(originalValue)), change);
381      object->addToSumUpChange(nonZeroAmount + movement);
382      object->addToSumUpDecrease(unsatisfied - originalUnsatisfied);
383#if TYPE2 == 0
384      object->addToSumUpCost(change / (nonZeroAmount + movement));
385      object->setUpDynamicPseudoCost(object->sumUpCost() / (double)object->numberTimesUp());
386#elif TYPE2 == 1
387      object->addToSumUpCost(change);
388      object->setUpDynamicPseudoCost(object->sumUpCost() / object->sumUpChange());
389#elif TYPE2 == 2
390      object->addToSumUpCost(change * TYPERATIO + (1.0 - TYPERATIO) * change / (nonZeroAmount + movement));
391      object->setUpDynamicPseudoCost(object->sumUpCost() * (TYPERATIO / object->sumUpChange() + (1.0 - TYPERATIO) / (double)object->numberTimesUp()));
392#endif
393#endif
394    }
395  }
396  //object->print(1,0.5);
397  delete object_;
398  object_ = NULL;
399}
400
401/*
402  Simple dynamic decision algorithm. Compare based on infeasibility (numInfUp,
403  numInfDown) until a solution is found by search, then switch to change in
404  objective (changeUp, changeDown). Note that bestSoFar is remembered in
405  bestObject_, so the parameter bestSoFar is unused.
406*/
407
408int CbcBranchDynamicDecision::betterBranch(CbcBranchingObject *thisOne,
409  CbcBranchingObject * /*bestSoFar*/,
410  double changeUp, int numInfUp,
411  double changeDown, int numInfDown)
412{
413  CbcModel *model = thisOne->model();
414  int stateOfSearch = model->stateOfSearch() % 10;
415  int betterWay = 0;
416  double value = 0.0;
417  if (!bestObject_) {
418    bestCriterion_ = -1.0e30;
419    bestNumberUp_ = COIN_INT_MAX;
420    bestNumberDown_ = COIN_INT_MAX;
421  }
422  // maybe branch up more if no solution or not many nodes done?
423  if (stateOfSearch <= 2) {
424    //#define TRY_STUFF 1
425#ifdef TRY_STUFF
426    // before solution - choose smallest number
427    // could add in depth as well
428    int bestNumber = CoinMin(bestNumberUp_, bestNumberDown_);
429    if (numInfUp < numInfDown) {
430      if (numInfUp < bestNumber) {
431        betterWay = 1;
432      } else if (numInfUp == bestNumber) {
433        if (changeUp < bestChangeUp_)
434          betterWay = 1;
435      }
436    } else if (numInfUp > numInfDown) {
437      if (numInfDown < bestNumber) {
438        betterWay = -1;
439      } else if (numInfDown == bestNumber) {
440        if (changeDown < bestChangeDown_)
441          betterWay = -1;
442      }
443    } else {
444      // up and down have same number
445      bool better = false;
446      if (numInfUp < bestNumber) {
447        better = true;
448      } else if (numInfUp == bestNumber) {
449        if (CoinMin(changeUp, changeDown) < CoinMin(bestChangeUp_, bestChangeDown_) - 1.0e-5)
450          better = true;
451        ;
452      }
453      if (better) {
454        // see which way
455        if (changeUp <= changeDown)
456          betterWay = 1;
457        else
458          betterWay = -1;
459      }
460    }
461    if (betterWay) {
462      value = CoinMin(numInfUp, numInfDown);
463    }
464#else
465    // use pseudo shadow prices modified by locks
466    // test testosi
467#ifndef JJF_ONE
468    double objectiveValue = model->getCurrentMinimizationObjValue();
469    double distanceToCutoff = model->getCutoff() - objectiveValue;
470    if (distanceToCutoff < 1.0e20)
471      distanceToCutoff *= 10.0;
472    else
473      distanceToCutoff = 1.0e2 + fabs(objectiveValue);
474    distanceToCutoff = CoinMax(distanceToCutoff, 1.0e-12 * (1.0 + fabs(objectiveValue)));
475    double continuousObjective = model->getContinuousObjective();
476    double distanceToCutoffC = model->getCutoff() - continuousObjective;
477    if (distanceToCutoffC > 1.0e20)
478      distanceToCutoffC = 1.0e2 + fabs(objectiveValue);
479    distanceToCutoffC = CoinMax(distanceToCutoffC, 1.0e-12 * (1.0 + fabs(objectiveValue)));
480    int numberInfC = model->getContinuousInfeasibilities();
481    double perInf = distanceToCutoffC / static_cast< double >(numberInfC);
482    assert(perInf > 0.0);
483    //int numberIntegers = model->numberIntegers();
484    changeDown += perInf * numInfDown;
485    changeUp += perInf * numInfUp;
486#ifdef JJF_ZERO
487    if (numInfDown == 1) {
488      if (numInfUp == 1) {
489        changeUp += 1.0e6;
490        changeDown += 1.0e6;
491      } else if (changeDown <= 1.5 * changeUp) {
492        changeUp += 1.0e6;
493      }
494    } else if (numInfUp == 1 && changeUp <= 1.5 * changeDown) {
495      changeDown += 1.0e6;
496    }
497#endif
498#endif
499    double minValue = CoinMin(changeDown, changeUp);
500    double maxValue = CoinMax(changeDown, changeUp);
501    value = WEIGHT_BEFORE * minValue + (1.0 - WEIGHT_BEFORE) * maxValue;
502    if (value > bestCriterion_ + 1.0e-8) {
503      if (changeUp <= 1.5 * changeDown) {
504        betterWay = 1;
505      } else {
506        betterWay = -1;
507      }
508    }
509#endif
510  } else {
511#define TRY_STUFF 2
512#if TRY_STUFF > 1
513    // Get current number of infeasibilities, cutoff and current objective
514    CbcNode *node = model->currentNode();
515    int numberUnsatisfied = node->numberUnsatisfied();
516    double cutoff = model->getCutoff();
517    double objectiveValue = node->objectiveValue();
518#endif
519    // got a solution
520    double minValue = CoinMin(changeDown, changeUp);
521    double maxValue = CoinMax(changeDown, changeUp);
522    // Reduce
523#ifdef TRY_STUFF
524    //maxValue = CoinMin(maxValue,minValue*4.0);
525#else
526    //maxValue = CoinMin(maxValue,minValue*2.0);
527#endif
528#ifndef WEIGHT_PRODUCT
529    value = WEIGHT_AFTER * minValue + (1.0 - WEIGHT_AFTER) * maxValue;
530#else
531    double minProductWeight = model->getDblParam(CbcModel::CbcSmallChange);
532    value = CoinMax(minValue, minProductWeight) * CoinMax(maxValue, minProductWeight);
533    //value += minProductWeight*minValue;
534#endif
535    double useValue = value;
536    double useBest = bestCriterion_;
537#if TRY_STUFF > 1
538    int thisNumber = CoinMin(numInfUp, numInfDown);
539    int bestNumber = CoinMin(bestNumberUp_, bestNumberDown_);
540    double distance = cutoff - objectiveValue;
541    assert(distance >= 0.0);
542    if (useValue + 0.1 * distance > useBest && useValue * 1.1 > useBest && useBest + 0.1 * distance > useValue && useBest * 1.1 > useValue) {
543      // not much in it - look at unsatisfied
544      if (thisNumber < numberUnsatisfied || bestNumber < numberUnsatisfied) {
545        double perInteger = distance / (static_cast< double >(numberUnsatisfied));
546        useValue += thisNumber * perInteger;
547        useBest += bestNumber * perInteger;
548      }
549    }
550#endif
551    if (useValue > useBest + 1.0e-8) {
552      if (changeUp <= 1.5 * changeDown) {
553        betterWay = 1;
554      } else {
555        betterWay = -1;
556      }
557    }
558  }
559#ifdef COIN_DEVELOP
560  History hist;
561  {
562    CbcDynamicPseudoCostBranchingObject *branchingObject = dynamic_cast< CbcDynamicPseudoCostBranchingObject * >(thisOne);
563    if (branchingObject) {
564      CbcSimpleIntegerDynamicPseudoCost *object = branchingObject->object();
565      assert(object);
566      hist.where_ = 'C';
567      hist.status_ = ' ';
568      hist.sequence_ = object->columnNumber();
569      hist.numberUp_ = object->numberTimesUp();
570      hist.numberUpInf_ = numInfUp;
571      hist.sumUp_ = object->sumUpCost();
572      hist.upEst_ = changeUp;
573      hist.numberDown_ = object->numberTimesDown();
574      hist.numberDownInf_ = numInfDown;
575      hist.sumDown_ = object->sumDownCost();
576      hist.downEst_ = changeDown;
577    }
578  }
579#endif
580  if (betterWay) {
581#ifdef COIN_DEVELOP
582    hist.status_ = 'B';
583#endif
584    // maybe change better way
585    CbcDynamicPseudoCostBranchingObject *branchingObject = dynamic_cast< CbcDynamicPseudoCostBranchingObject * >(thisOne);
586    if (branchingObject) {
587      CbcSimpleIntegerDynamicPseudoCost *object = branchingObject->object();
588      double separator = object->upDownSeparator();
589      if (separator > 0.0) {
590        const double *solution = thisOne->model()->testSolution();
591        double valueVariable = solution[object->columnNumber()];
592        betterWay = (valueVariable - floor(valueVariable) >= separator) ? 1 : -1;
593      }
594    }
595    bestCriterion_ = value;
596    bestChangeUp_ = changeUp;
597    bestNumberUp_ = numInfUp;
598    bestChangeDown_ = changeDown;
599    bestNumberDown_ = numInfDown;
600    bestObject_ = thisOne;
601    // See if user is overriding way
602    if (thisOne->object() && thisOne->object()->preferredWay())
603      betterWay = thisOne->object()->preferredWay();
604  }
605#ifdef COIN_DEVELOP
606  addRecord(hist);
607#endif
608  return betterWay;
609}
610/* Sets or gets best criterion so far */
611void CbcBranchDynamicDecision::setBestCriterion(double value)
612{
613  bestCriterion_ = value;
614}
615double
616CbcBranchDynamicDecision::getBestCriterion() const
617{
618  return bestCriterion_;
619}
620#ifdef COIN_DEVELOP
621void printHistory(const char *file)
622{
623  if (!numberHistory)
624    return;
625  FILE *fp = fopen(file, "w");
626  assert(fp);
627  int numberIntegers = 0;
628  int i;
629  for (i = 0; i < numberHistory; i++) {
630    if (history[i].where_ != 'C' || history[i].status_ != 'I')
631      numberIntegers = CoinMax(numberIntegers, history[i].sequence_);
632  }
633  numberIntegers++;
634  for (int iC = 0; iC < numberIntegers; iC++) {
635    int n = 0;
636    for (i = 0; i < numberHistory; i++) {
637      if (history[i].sequence_ == iC) {
638        if (!n)
639          fprintf(fp, "XXX %d\n", iC);
640        n++;
641        fprintf(fp, "%c%c up %8d %8d %12.5f %12.5f down  %8d %8d %12.5f %12.5f\n",
642          history[i].where_,
643          history[i].status_,
644          history[i].numberUp_,
645          history[i].numberUpInf_,
646          history[i].sumUp_,
647          history[i].upEst_,
648          history[i].numberDown_,
649          history[i].numberDownInf_,
650          history[i].sumDown_,
651          history[i].downEst_);
652      }
653    }
654  }
655  fclose(fp);
656}
657#endif
658
659// Default Constructor
660CbcDynamicPseudoCostBranchingObject::CbcDynamicPseudoCostBranchingObject()
661  : CbcIntegerBranchingObject()
662{
663  changeInGuessed_ = 1.0e-5;
664  object_ = NULL;
665}
666
667// Useful constructor
668CbcDynamicPseudoCostBranchingObject::CbcDynamicPseudoCostBranchingObject(CbcModel *model,
669  int variable,
670  int way, double value,
671  CbcSimpleIntegerDynamicPseudoCost *object)
672  : CbcIntegerBranchingObject(model, variable, way, value)
673{
674  changeInGuessed_ = 1.0e-5;
675  object_ = object;
676}
677// Does part of work for constructor
678void CbcDynamicPseudoCostBranchingObject::fillPart(int variable,
679  int way, double value,
680  CbcSimpleIntegerDynamicPseudoCost *object)
681{
682  CbcIntegerBranchingObject::fillPart(variable, way, value);
683  changeInGuessed_ = 1.0e-5;
684  object_ = object;
685}
686// Useful constructor for fixing
687CbcDynamicPseudoCostBranchingObject::CbcDynamicPseudoCostBranchingObject(CbcModel *model,
688  int variable, int way,
689  double lowerValue,
690  double /*upperValue*/)
691  : CbcIntegerBranchingObject(model, variable, way, lowerValue)
692{
693  changeInGuessed_ = 1.0e100;
694  object_ = NULL;
695}
696
697// Copy constructor
698CbcDynamicPseudoCostBranchingObject::CbcDynamicPseudoCostBranchingObject(
699  const CbcDynamicPseudoCostBranchingObject &rhs)
700  : CbcIntegerBranchingObject(rhs)
701{
702  changeInGuessed_ = rhs.changeInGuessed_;
703  object_ = rhs.object_;
704}
705
706// Assignment operator
707CbcDynamicPseudoCostBranchingObject &
708CbcDynamicPseudoCostBranchingObject::operator=(const CbcDynamicPseudoCostBranchingObject &rhs)
709{
710  if (this != &rhs) {
711    CbcIntegerBranchingObject::operator=(rhs);
712    changeInGuessed_ = rhs.changeInGuessed_;
713    object_ = rhs.object_;
714  }
715  return *this;
716}
717CbcBranchingObject *
718CbcDynamicPseudoCostBranchingObject::clone() const
719{
720  return (new CbcDynamicPseudoCostBranchingObject(*this));
721}
722
723// Destructor
724CbcDynamicPseudoCostBranchingObject::~CbcDynamicPseudoCostBranchingObject()
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  Returns change in guessed objective on next branch
737*/
738double
739CbcDynamicPseudoCostBranchingObject::branch()
740{
741  CbcIntegerBranchingObject::branch();
742  return changeInGuessed_;
743}
744/* Some branchingObjects may claim to be able to skip
745   strong branching.  If so they have to fill in CbcStrongInfo.
746   The object mention in incoming CbcStrongInfo must match.
747   Returns nonzero if skip is wanted */
748int CbcDynamicPseudoCostBranchingObject::fillStrongInfo(CbcStrongInfo &info)
749{
750  assert(object_);
751  assert(info.possibleBranch == this);
752  info.upMovement = object_->upDynamicPseudoCost() * (ceil(value_) - value_);
753  info.downMovement = object_->downDynamicPseudoCost() * (value_ - floor(value_));
754  info.numIntInfeasUp -= static_cast< int >(object_->sumUpDecrease() / (1.0e-12 + static_cast< double >(object_->numberTimesUp())));
755  info.numIntInfeasUp = CoinMax(info.numIntInfeasUp, 0);
756  info.numObjInfeasUp = 0;
757  info.finishedUp = false;
758  info.numItersUp = 0;
759  info.numIntInfeasDown -= static_cast< int >(object_->sumDownDecrease() / (1.0e-12 + static_cast< double >(object_->numberTimesDown())));
760  info.numIntInfeasDown = CoinMax(info.numIntInfeasDown, 0);
761  info.numObjInfeasDown = 0;
762  info.finishedDown = false;
763  info.numItersDown = 0;
764  info.fix = 0;
765  if (object_->numberTimesUp() < object_->numberBeforeTrust() + 2 * object_->numberTimesUpInfeasible() || object_->numberTimesDown() < object_->numberBeforeTrust() + 2 * object_->numberTimesDownInfeasible()) {
766    return 0;
767  } else {
768    return 1;
769  }
770}
771
772/* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2
773*/
Note: See TracBrowser for help on using the repository browser.