source: trunk/Cbc/src/CbcBranchDefaultDecision.cpp

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

spaces after angles

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 13.7 KB
Line 
1// $Id: CbcBranchDefaultDecision.cpp 2467 2019-01-03 21:26:29Z glebb $
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// Edwin 11/10/2009-- carved out of CbcBranchActual
7
8#if defined(_MSC_VER)
9// Turn off compiler warning about long names
10#pragma warning(disable : 4786)
11#endif
12#include <cassert>
13#include <cstdlib>
14#include <cmath>
15#include <cfloat>
16//#define CBC_DEBUG
17
18#include "CoinTypes.hpp"
19#include "OsiSolverInterface.hpp"
20#include "OsiSolverBranch.hpp"
21#include "CbcModel.hpp"
22#include "CbcMessage.hpp"
23#include "CbcBranchDefaultDecision.hpp"
24#include "CbcBranchActual.hpp"
25#include "CoinSort.hpp"
26#include "CoinError.hpp"
27
28//##############################################################################
29
30// Default Constructor
31CbcBranchDefaultDecision::CbcBranchDefaultDecision()
32  : CbcBranchDecision()
33{
34  bestCriterion_ = 0.0;
35  bestChangeUp_ = 0.0;
36  bestNumberUp_ = 0;
37  bestChangeDown_ = 0.0;
38  bestObject_ = NULL;
39  bestNumberDown_ = 0;
40}
41
42// Copy constructor
43CbcBranchDefaultDecision::CbcBranchDefaultDecision(
44  const CbcBranchDefaultDecision &rhs)
45  : CbcBranchDecision(rhs)
46{
47  bestCriterion_ = rhs.bestCriterion_;
48  bestChangeUp_ = rhs.bestChangeUp_;
49  bestNumberUp_ = rhs.bestNumberUp_;
50  bestChangeDown_ = rhs.bestChangeDown_;
51  bestNumberDown_ = rhs.bestNumberDown_;
52  bestObject_ = rhs.bestObject_;
53  model_ = rhs.model_;
54}
55
56CbcBranchDefaultDecision::~CbcBranchDefaultDecision()
57{
58}
59
60// Clone
61CbcBranchDecision *
62CbcBranchDefaultDecision::clone() const
63{
64  return new CbcBranchDefaultDecision(*this);
65}
66
67// Initialize i.e. before start of choosing at a node
68void CbcBranchDefaultDecision::initialize(CbcModel *model)
69{
70  bestCriterion_ = 0.0;
71  bestChangeUp_ = 0.0;
72  bestNumberUp_ = 0;
73  bestChangeDown_ = 0.0;
74  bestNumberDown_ = 0;
75  bestObject_ = NULL;
76  model_ = model;
77}
78
79/*
80  Simple default decision algorithm. Compare based on infeasibility (numInfUp,
81  numInfDn) until a solution is found by search, then switch to change in
82  objective (changeUp, changeDn). Note that bestSoFar is remembered in
83  bestObject_, so the parameter bestSoFar is unused.
84*/
85
86int CbcBranchDefaultDecision::betterBranch(CbcBranchingObject *thisOne,
87  CbcBranchingObject * /*bestSoFar*/,
88  double changeUp, int numInfUp,
89  double changeDn, int numInfDn)
90{
91  bool beforeSolution = cbcModel()->getSolutionCount() == cbcModel()->getNumberHeuristicSolutions();
92  ;
93  int betterWay = 0;
94  if (beforeSolution) {
95    if (!bestObject_) {
96      bestNumberUp_ = COIN_INT_MAX;
97      bestNumberDown_ = COIN_INT_MAX;
98    }
99    // before solution - choose smallest number
100    // could add in depth as well
101    int bestNumber = CoinMin(bestNumberUp_, bestNumberDown_);
102    if (numInfUp < numInfDn) {
103      if (numInfUp < bestNumber) {
104        betterWay = 1;
105      } else if (numInfUp == bestNumber) {
106        if (changeUp < bestCriterion_)
107          betterWay = 1;
108      }
109    } else if (numInfUp > numInfDn) {
110      if (numInfDn < bestNumber) {
111        betterWay = -1;
112      } else if (numInfDn == bestNumber) {
113        if (changeDn < bestCriterion_)
114          betterWay = -1;
115      }
116    } else {
117      // up and down have same number
118      bool better = false;
119      if (numInfUp < bestNumber) {
120        better = true;
121      } else if (numInfUp == bestNumber) {
122        if (CoinMin(changeUp, changeDn) < bestCriterion_)
123          better = true;
124        ;
125      }
126      if (better) {
127        // see which way
128        if (changeUp <= changeDn)
129          betterWay = 1;
130        else
131          betterWay = -1;
132      }
133    }
134  } else {
135    if (!bestObject_) {
136      bestCriterion_ = -1.0;
137    }
138    // got a solution
139    if (changeUp <= changeDn) {
140      if (changeUp > bestCriterion_)
141        betterWay = 1;
142    } else {
143      if (changeDn > bestCriterion_)
144        betterWay = -1;
145    }
146  }
147  if (betterWay) {
148    bestCriterion_ = CoinMin(changeUp, changeDn);
149    bestChangeUp_ = changeUp;
150    bestNumberUp_ = numInfUp;
151    bestChangeDown_ = changeDn;
152    bestNumberDown_ = numInfDn;
153    bestObject_ = thisOne;
154    // See if user is overriding way
155    if (thisOne->object() && thisOne->object()->preferredWay())
156      betterWay = thisOne->object()->preferredWay();
157  }
158  return betterWay;
159}
160/* Sets or gets best criterion so far */
161void CbcBranchDefaultDecision::setBestCriterion(double value)
162{
163  bestCriterion_ = value;
164}
165double
166CbcBranchDefaultDecision::getBestCriterion() const
167{
168  return bestCriterion_;
169}
170
171/* Compare N branching objects. Return index of best
172   and sets way of branching in chosen object.
173
174   This routine is used only after strong branching.
175*/
176
177int CbcBranchDefaultDecision::bestBranch(CbcBranchingObject **objects, int numberObjects,
178  int numberUnsatisfied,
179  double *changeUp, int *numberInfeasibilitiesUp,
180  double *changeDown, int *numberInfeasibilitiesDown,
181  double objectiveValue)
182{
183
184  int bestWay = 0;
185  int whichObject = -1;
186  if (numberObjects) {
187    CbcModel *model = cbcModel();
188    // at continuous
189    //double continuousObjective = model->getContinuousObjective();
190    //int continuousInfeasibilities = model->getContinuousInfeasibilities();
191
192    // average cost to get rid of infeasibility
193    //double averageCostPerInfeasibility =
194    //(objectiveValue-continuousObjective)/
195    //(double) (abs(continuousInfeasibilities-numberUnsatisfied)+1);
196    /* beforeSolution is :
197           0 - before any solution
198           n - n heuristic solutions but no branched one
199           -1 - branched solution found
200        */
201    int numberSolutions = model->getSolutionCount();
202    double cutoff = model->getCutoff();
203    int method = 0;
204    int i;
205    if (numberSolutions) {
206      int numberHeuristic = model->getNumberHeuristicSolutions();
207      if (numberHeuristic < numberSolutions) {
208        method = 1;
209      } else {
210        method = 2;
211        // look further
212        for (i = 0; i < numberObjects; i++) {
213          int numberNext = numberInfeasibilitiesUp[i];
214
215          if (numberNext < numberUnsatisfied) {
216            int numberUp = numberUnsatisfied - numberInfeasibilitiesUp[i];
217            double perUnsatisfied = changeUp[i] / static_cast< double >(numberUp);
218            double estimatedObjective = objectiveValue + numberUnsatisfied * perUnsatisfied;
219            if (estimatedObjective < cutoff)
220              method = 3;
221          }
222          numberNext = numberInfeasibilitiesDown[i];
223          if (numberNext < numberUnsatisfied) {
224            int numberDown = numberUnsatisfied - numberInfeasibilitiesDown[i];
225            double perUnsatisfied = changeDown[i] / static_cast< double >(numberDown);
226            double estimatedObjective = objectiveValue + numberUnsatisfied * perUnsatisfied;
227            if (estimatedObjective < cutoff)
228              method = 3;
229          }
230        }
231      }
232      method = 2;
233    } else {
234      method = 0;
235    }
236    // Uncomment next to force method 4
237    //method=4;
238
239    // FIXME This should be an enum.  It will be easier to
240    // understand in the code than numbers.
241    /* Methods :
242           0 - fewest infeasibilities
243           1 - largest min change in objective
244           2 - as 1 but use sum of changes if min close
245           3 - predicted best solution
246           4 - take cheapest up branch if infeasibilities same
247        */
248    int bestNumber = COIN_INT_MAX;
249    double bestCriterion = -1.0e50;
250    double alternativeCriterion = -1.0;
251    double bestEstimate = 1.0e100;
252    switch (method) {
253    case 0:
254      // could add in depth as well
255      for (i = 0; i < numberObjects; i++) {
256        int thisNumber = CoinMin(numberInfeasibilitiesUp[i], numberInfeasibilitiesDown[i]);
257        if (thisNumber <= bestNumber) {
258          int betterWay = 0;
259          if (numberInfeasibilitiesUp[i] < numberInfeasibilitiesDown[i]) {
260            if (numberInfeasibilitiesUp[i] < bestNumber) {
261              betterWay = 1;
262            } else {
263              if (changeUp[i] < bestCriterion)
264                betterWay = 1;
265            }
266          } else if (numberInfeasibilitiesUp[i] > numberInfeasibilitiesDown[i]) {
267            if (numberInfeasibilitiesDown[i] < bestNumber) {
268              betterWay = -1;
269            } else {
270              if (changeDown[i] < bestCriterion)
271                betterWay = -1;
272            }
273          } else {
274            // up and down have same number
275            bool better = false;
276            if (numberInfeasibilitiesUp[i] < bestNumber) {
277              better = true;
278            } else if (numberInfeasibilitiesUp[i] == bestNumber) {
279              if (CoinMin(changeUp[i], changeDown[i]) < bestCriterion)
280                better = true;
281              ;
282            }
283            if (better) {
284              // see which way
285              if (changeUp[i] <= changeDown[i])
286                betterWay = 1;
287              else
288                betterWay = -1;
289            }
290          }
291          if (betterWay) {
292            bestCriterion = CoinMin(changeUp[i], changeDown[i]);
293            bestNumber = thisNumber;
294            whichObject = i;
295            bestWay = betterWay;
296          }
297        }
298      }
299      break;
300    case 1:
301      for (i = 0; i < numberObjects; i++) {
302        int betterWay = 0;
303        if (changeUp[i] <= changeDown[i]) {
304          if (changeUp[i] > bestCriterion)
305            betterWay = 1;
306        } else {
307          if (changeDown[i] > bestCriterion)
308            betterWay = -1;
309        }
310        if (betterWay) {
311          bestCriterion = CoinMin(changeUp[i], changeDown[i]);
312          whichObject = i;
313          bestWay = betterWay;
314        }
315      }
316      break;
317    case 2:
318      for (i = 0; i < numberObjects; i++) {
319        double change = CoinMin(changeUp[i], changeDown[i]);
320        double sum = changeUp[i] + changeDown[i];
321        bool take = false;
322        if (change > 1.1 * bestCriterion)
323          take = true;
324        else if (change > 0.9 * bestCriterion && sum + change > bestCriterion + alternativeCriterion)
325          take = true;
326        if (take) {
327          if (changeUp[i] <= changeDown[i]) {
328            if (changeUp[i] > bestCriterion)
329              bestWay = 1;
330          } else {
331            if (changeDown[i] > bestCriterion)
332              bestWay = -1;
333          }
334          bestCriterion = change;
335          alternativeCriterion = sum;
336          whichObject = i;
337        }
338      }
339      break;
340    case 3:
341      for (i = 0; i < numberObjects; i++) {
342        int numberNext = numberInfeasibilitiesUp[i];
343
344        if (numberNext < numberUnsatisfied) {
345          int numberUp = numberUnsatisfied - numberInfeasibilitiesUp[i];
346          double perUnsatisfied = changeUp[i] / static_cast< double >(numberUp);
347          double estimatedObjective = objectiveValue + numberUnsatisfied * perUnsatisfied;
348          if (estimatedObjective < bestEstimate) {
349            bestEstimate = estimatedObjective;
350            bestWay = 1;
351            whichObject = i;
352          }
353        }
354        numberNext = numberInfeasibilitiesDown[i];
355        if (numberNext < numberUnsatisfied) {
356          int numberDown = numberUnsatisfied - numberInfeasibilitiesDown[i];
357          double perUnsatisfied = changeDown[i] / static_cast< double >(numberDown);
358          double estimatedObjective = objectiveValue + numberUnsatisfied * perUnsatisfied;
359          if (estimatedObjective < bestEstimate) {
360            bestEstimate = estimatedObjective;
361            bestWay = -1;
362            whichObject = i;
363          }
364        }
365      }
366      break;
367    case 4:
368      // if number infeas same then cheapest up
369      // first get best number or when going down
370      // now choose smallest change up amongst equal number infeas
371      for (i = 0; i < numberObjects; i++) {
372        int thisNumber = CoinMin(numberInfeasibilitiesUp[i], numberInfeasibilitiesDown[i]);
373        if (thisNumber <= bestNumber) {
374          int betterWay = 0;
375          if (numberInfeasibilitiesUp[i] < numberInfeasibilitiesDown[i]) {
376            if (numberInfeasibilitiesUp[i] < bestNumber) {
377              betterWay = 1;
378            } else {
379              if (changeUp[i] < bestCriterion)
380                betterWay = 1;
381            }
382          } else if (numberInfeasibilitiesUp[i] > numberInfeasibilitiesDown[i]) {
383            if (numberInfeasibilitiesDown[i] < bestNumber) {
384              betterWay = -1;
385            } else {
386              if (changeDown[i] < bestCriterion)
387                betterWay = -1;
388            }
389          } else {
390            // up and down have same number
391            bool better = false;
392            if (numberInfeasibilitiesUp[i] < bestNumber) {
393              better = true;
394            } else if (numberInfeasibilitiesUp[i] == bestNumber) {
395              if (CoinMin(changeUp[i], changeDown[i]) < bestCriterion)
396                better = true;
397              ;
398            }
399            if (better) {
400              // see which way
401              if (changeUp[i] <= changeDown[i])
402                betterWay = 1;
403              else
404                betterWay = -1;
405            }
406          }
407          if (betterWay) {
408            bestCriterion = CoinMin(changeUp[i], changeDown[i]);
409            bestNumber = thisNumber;
410            whichObject = i;
411            bestWay = betterWay;
412          }
413        }
414      }
415      bestCriterion = 1.0e50;
416      for (i = 0; i < numberObjects; i++) {
417        int thisNumber = numberInfeasibilitiesUp[i];
418        if (thisNumber == bestNumber && changeUp) {
419          if (changeUp[i] < bestCriterion) {
420            bestCriterion = changeUp[i];
421            whichObject = i;
422            bestWay = 1;
423          }
424        }
425      }
426      break;
427    }
428    // set way in best
429    if (whichObject >= 0) {
430      CbcBranchingObject *bestObject = objects[whichObject];
431      if (bestObject->object() && bestObject->object()->preferredWay())
432        bestWay = bestObject->object()->preferredWay();
433      bestObject->way(bestWay);
434    } else {
435      COIN_DETAIL_PRINT(printf("debug\n"));
436    }
437  }
438  return whichObject;
439}
440
441/* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2
442*/
Note: See TracBrowser for help on using the repository browser.