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

Last change on this file since 1432 was 1432, checked in by bjarni, 9 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.