source: trunk/Alps/examples/Abc/AbcBranchActual.cpp @ 277

Last change on this file since 277 was 277, checked in by andreasw, 13 years ago

first working version with autotools

File size: 5.6 KB
Line 
1/*===========================================================================*
2 * This file is part of the Abstract Library for Parallel Search (ALPS).     *
3 *                                                                           *
4 * ALPS is distributed under the Common Public License as part of the        *
5 * COIN-OR repository (http://www.coin-or.org).                              *
6 *                                                                           *
7 * Authors: Yan Xu, SAS Institute Inc.                                       *
8 *          Ted Ralphs, Lehigh University                                    *
9 *          Laszlo Ladanyi, IBM T.J. Watson Research Center                  *
10 *          Matthew Saltzman, Clemson University                             *
11 *                                                                           *
12 *                                                                           *
13 * Copyright (C) 2001-2004, International Business Machines                  *
14 * Corporation, Lehigh University, Yan Xu, Ted Ralphs, Matthew Salzman and   *
15 * others. All Rights Reserved.                                              *
16 *===========================================================================*/
17
18//#############################################################################
19// This file is modified from SbbBranchActual.cpp
20//#############################################################################
21
22#if defined(_MSC_VER)
23// Turn off compiler warning about long names
24#  pragma warning(disable:4786)
25#endif
26#include <cassert>
27#include <cmath>
28#include <cfloat>
29
30#include "CoinSort.hpp"
31#include "OsiSolverInterface.hpp"
32
33#include "AbcModel.h"
34#include "AbcMessage.h"
35#include "AbcBranchActual.h"
36
37//#############################################################################
38//#############################################################################
39
40// Default Constructor
41AbcBranchDefaultDecision::AbcBranchDefaultDecision()
42    :
43    AbcBranchDecision()
44{
45    model_ = NULL;
46    bestCriterion_ = 0.0;
47    bestChangeUp_ = 0.0;
48    bestNumberUp_ = 0;
49    bestChangeDown_ = 0.0;
50    bestNumberDown_ = 0;
51    bestObject_ = -1;
52}
53
54// Copy constructor
55AbcBranchDefaultDecision::AbcBranchDefaultDecision (
56    const AbcBranchDefaultDecision & rhs)
57    :
58    AbcBranchDecision()
59{
60    model_ = rhs.model_;
61    bestCriterion_ = rhs.bestCriterion_;
62    bestChangeUp_ = rhs.bestChangeUp_;
63    bestNumberUp_ = rhs.bestNumberUp_;
64    bestChangeDown_ = rhs.bestChangeDown_;
65    bestNumberDown_ = rhs.bestNumberDown_;
66    bestObject_ = rhs.bestObject_;
67}
68
69AbcBranchDefaultDecision::~AbcBranchDefaultDecision()
70{
71}
72
73// Clone
74AbcBranchDecision * 
75AbcBranchDefaultDecision::clone() const
76{
77    return new AbcBranchDefaultDecision(*this);
78}
79
80// Initialize i.e. before start of choosing at a node
81void 
82AbcBranchDefaultDecision::initialize(AbcModel * model)
83{
84    model_ = model;
85    bestCriterion_ = 0.0;
86    bestChangeUp_ = 0.0;
87    bestNumberUp_ = 0;
88    bestChangeDown_ = 0.0;
89    bestNumberDown_ = 0;
90    bestObject_ = -1;
91}
92
93// Simple default decision algorithm. Compare based on infeasibility
94// (numInfUp, numInfDn) until a solution is found by search, then switch
95// to change in objective (changeUp, changeDn). Note that bestSoFar is
96// remembered in bestObject_, so the parameter bestSoFar is unused.
97int
98AbcBranchDefaultDecision::betterBranch(int thisOne, int bestSoFar,
99                                       double changeUp, int numInfUp,
100                                       double changeDn, int numInfDn)
101{
102    bool beforeSolution = model_->getSolutionCount() ==
103        model_->getNumberHeuristicSolutions();
104    int betterWay = 0;
105    if (beforeSolution) {
106        if (bestObject_ < 0) {
107            bestNumberUp_ = INT_MAX;
108            bestNumberDown_ = INT_MAX;
109        }
110       
111        // before solution - choose smallest number could add in depth as well
112        int bestNumber = min(bestNumberUp_, bestNumberDown_);
113        if (numInfUp < numInfDn) {
114            if (numInfUp < bestNumber) {
115                betterWay = 1;
116            } else if (numInfUp == bestNumber) {
117                if (changeUp < bestCriterion_)
118                    betterWay = 1;
119            }
120        } else if (numInfUp > numInfDn) {
121            if (numInfDn < bestNumber) {
122                betterWay = -1;
123            } else if (numInfDn == bestNumber) {
124                if (changeDn < bestCriterion_)
125                    betterWay = -1;
126            }
127        } else {
128            // up and down have same number
129            bool better = false;
130            if (numInfUp < bestNumber) {
131                better = true;
132            } else if (numInfUp == bestNumber) {
133                if (min(changeUp, changeDn) < bestCriterion_)
134                    better = true;
135            }
136            if (better) {
137                // see which way
138                if (changeUp <= changeDn)
139                    betterWay = 1;
140                else
141                    betterWay = -1;
142            }
143        }
144    } 
145    else {        // got a solution
146        if (bestObject_ < 0) {
147            bestCriterion_ = -1.0;
148        }
149        if (changeUp <= changeDn) {
150            if (changeUp > bestCriterion_)
151                betterWay = 1;
152        } 
153        else {
154            if (changeDn > bestCriterion_)
155                betterWay = -1;
156        }
157    }
158
159    if (betterWay) {
160        bestCriterion_ = min(changeUp, changeDn);
161        bestChangeUp_ = changeUp;
162        bestNumberUp_ = numInfUp;
163        bestChangeDown_ = changeDn;
164        bestNumberDown_ = numInfDn;
165        bestObject_ = thisOne;
166    }
167
168    return betterWay;
169}
170
171void 
172AbcPseudocost::update(const int dir,
173                      const double parentObjValue,
174                      const double objValue,
175                      const double solValue)
176{
177    double fraction = solValue - floor(solValue);
178    double objDiff = objValue - parentObjValue;
179    double cost;
180   
181    if (dir == 1) {
182        cost = objDiff / (fraction + 1.0e-9);
183        upCost_ = (upCost_ * upNum_ + cost) / (upNum_ + 1);
184        ++upNum_;
185    }
186    else if (dir == -1) {
187        cost = objDiff / (1.0 - fraction + 1.0e-9);
188        downCost_ = (downCost_ * downNum_ + cost) / (downNum_ + 1);
189        ++downNum_;
190    }
191    else {
192        abort();
193    }
194}
Note: See TracBrowser for help on using the repository browser.