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

Last change on this file since 1433 was 1432, checked in by bjarni, 10 years ago

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