source: trunk/Cbc/src/CbcBranchDefaultDecision.cpp @ 1899

Last change on this file since 1899 was 1899, checked in by stefan, 6 years ago

fixup svn properties

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