source: stable/2.5/Cbc/src/CbcHeuristicDivePseudoCost.cpp @ 1510

Last change on this file since 1510 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: 7.9 KB
Line 
1/* $Id: CbcHeuristicDivePseudoCost.cpp 1240 2009-10-02 18:41:44Z forrest $ */
2// Copyright (C) 2008, International Business Machines
3// Corporation and others.  All Rights Reserved.
4#if defined(_MSC_VER)
5// Turn off compiler warning about long names
6#  pragma warning(disable:4786)
7#endif
8
9#include "CbcHeuristicDivePseudoCost.hpp"
10#include "CbcStrategy.hpp"
11#include "CbcBranchDynamic.hpp"
12
13// Default Constructor
14CbcHeuristicDivePseudoCost::CbcHeuristicDivePseudoCost()
15        : CbcHeuristicDive()
16{
17}
18
19// Constructor from model
20CbcHeuristicDivePseudoCost::CbcHeuristicDivePseudoCost(CbcModel & model)
21        : CbcHeuristicDive(model)
22{
23}
24
25// Destructor
26CbcHeuristicDivePseudoCost::~CbcHeuristicDivePseudoCost ()
27{
28}
29
30// Clone
31CbcHeuristicDivePseudoCost *
32CbcHeuristicDivePseudoCost::clone() const
33{
34    return new CbcHeuristicDivePseudoCost(*this);
35}
36
37// Create C++ lines to get to current state
38void
39CbcHeuristicDivePseudoCost::generateCpp( FILE * fp)
40{
41    CbcHeuristicDivePseudoCost other;
42    fprintf(fp, "0#include \"CbcHeuristicDivePseudoCost.hpp\"\n");
43    fprintf(fp, "3  CbcHeuristicDivePseudoCost heuristicDivePseudoCost(*cbcModel);\n");
44    CbcHeuristic::generateCpp(fp, "heuristicDivePseudoCost");
45    fprintf(fp, "3  cbcModel->addHeuristic(&heuristicDivePseudoCost);\n");
46}
47
48// Copy constructor
49CbcHeuristicDivePseudoCost::CbcHeuristicDivePseudoCost(const CbcHeuristicDivePseudoCost & rhs)
50        :
51        CbcHeuristicDive(rhs)
52{
53}
54
55// Assignment operator
56CbcHeuristicDivePseudoCost &
57CbcHeuristicDivePseudoCost::operator=( const CbcHeuristicDivePseudoCost & rhs)
58{
59    if (this != &rhs) {
60        CbcHeuristicDive::operator=(rhs);
61    }
62    return *this;
63}
64
65bool
66CbcHeuristicDivePseudoCost::selectVariableToBranch(OsiSolverInterface* solver,
67        const double* newSolution,
68        int& bestColumn,
69        int& bestRound)
70{
71    int numberIntegers = model_->numberIntegers();
72    const int * integerVariable = model_->integerVariable();
73    double integerTolerance = model_->getDblParam(CbcModel::CbcIntegerTolerance);
74
75    // get the LP relaxation solution at the root node
76    double * rootNodeLPSol = model_->continuousSolution();
77
78    // get pseudo costs
79    double * pseudoCostDown = downArray_;
80    double * pseudoCostUp = upArray_;
81
82    bestColumn = -1;
83    bestRound = -1; // -1 rounds down, +1 rounds up
84    double bestScore = -1.0;
85    bool allTriviallyRoundableSoFar = true;
86    for (int i = 0; i < numberIntegers; i++) {
87        int iColumn = integerVariable[i];
88        double rootValue = rootNodeLPSol[iColumn];
89        double value = newSolution[iColumn];
90        double fraction = value - floor(value);
91        int round = 0;
92        if (fabs(floor(value + 0.5) - value) > integerTolerance) {
93            if (allTriviallyRoundableSoFar || (downLocks_[i] > 0 && upLocks_[i] > 0)) {
94
95                if (allTriviallyRoundableSoFar && downLocks_[i] > 0 && upLocks_[i] > 0) {
96                    allTriviallyRoundableSoFar = false;
97                    bestScore = -1.0;
98                }
99
100                double pCostDown = pseudoCostDown[i];
101                double pCostUp = pseudoCostUp[i];
102                assert(pCostDown >= 0.0 && pCostUp >= 0.0);
103
104                if (allTriviallyRoundableSoFar && downLocks_[i] == 0 && upLocks_[i] > 0)
105                    round = 1;
106                else if (allTriviallyRoundableSoFar && downLocks_[i] > 0 && upLocks_[i] == 0)
107                    round = -1;
108                else if (value - rootValue < -0.4)
109                    round = -1;
110                else if (value - rootValue > 0.4)
111                    round = 1;
112                else if (fraction < 0.3)
113                    round = -1;
114                else if (fraction > 0.7)
115                    round = 1;
116                else if (pCostDown < pCostUp)
117                    round = -1;
118                else
119                    round = 1;
120
121                // calculate score
122                double score;
123                if (round == 1)
124                    score = fraction * (pCostDown + 1.0) / (pCostUp + 1.0);
125                else
126                    score = (1.0 - fraction) * (pCostUp + 1.0) / (pCostDown + 1.0);
127
128                // if variable is binary, increase its chance of being selected
129                if (solver->isBinary(iColumn))
130                    score *= 1000.0;
131
132                if (score > bestScore) {
133                    bestColumn = iColumn;
134                    bestScore = score;
135                    bestRound = round;
136                }
137            }
138        }
139    }
140
141    return allTriviallyRoundableSoFar;
142}
143void
144CbcHeuristicDivePseudoCost::initializeData()
145{
146    int numberIntegers = model_->numberIntegers();
147    if (!downArray_) {
148        downArray_ = new double [numberIntegers];
149        upArray_ = new double [numberIntegers];
150    }
151    // get pseudo costs
152    model_->fillPseudoCosts(downArray_, upArray_);
153    int diveOptions = when_ / 100;
154    if (diveOptions) {
155        // pseudo shadow prices
156        int k = diveOptions % 100;
157        if (diveOptions >= 100)
158            k += 32;
159        model_->pseudoShadow(k - 1);
160        int numberInts = CoinMin(model_->numberObjects(), numberIntegers);
161        OsiObject ** objects = model_->objects();
162        for (int i = 0; i < numberInts; i++) {
163            CbcSimpleIntegerDynamicPseudoCost * obj1 =
164                dynamic_cast <CbcSimpleIntegerDynamicPseudoCost *>(objects[i]) ;
165            if (obj1) {
166                //int iColumn = obj1->columnNumber();
167                double downPseudoCost = 1.0e-2 * obj1->downDynamicPseudoCost();
168                double downShadow = obj1->downShadowPrice();
169                double upPseudoCost = 1.0e-2 * obj1->upDynamicPseudoCost();
170                double upShadow = obj1->upShadowPrice();
171                downPseudoCost = CoinMax(downPseudoCost, downShadow);
172                downPseudoCost = CoinMax(downPseudoCost, 0.001 * upShadow);
173                downArray_[i] = downPseudoCost;
174                upPseudoCost = CoinMax(upPseudoCost, upShadow);
175                upPseudoCost = CoinMax(upPseudoCost, 0.001 * downShadow);
176                upArray_[i] = upPseudoCost;
177            }
178        }
179    }
180}
181// Fix other variables at bounds
182int
183CbcHeuristicDivePseudoCost::fixOtherVariables(OsiSolverInterface * solver,
184        const double * solution,
185        PseudoReducedCost * candidate,
186        const double * random)
187{
188    const double * lower = solver->getColLower();
189    const double * upper = solver->getColUpper();
190    double integerTolerance = model_->getDblParam(CbcModel::CbcIntegerTolerance);
191    double primalTolerance;
192    solver->getDblParam(OsiPrimalTolerance, primalTolerance);
193
194    int numberIntegers = model_->numberIntegers();
195    const int * integerVariable = model_->integerVariable();
196    const double* reducedCost = solver->getReducedCost();
197    // fix other integer variables that are at their bounds
198    int cnt = 0;
199    int numberFree = 0;
200    int numberFixedAlready = 0;
201    for (int i = 0; i < numberIntegers; i++) {
202        int iColumn = integerVariable[i];
203        if (upper[iColumn] > lower[iColumn]) {
204            numberFree++;
205            double value = solution[iColumn];
206            if (value - lower[iColumn] <= integerTolerance) {
207                candidate[cnt].var = iColumn;
208                candidate[cnt++].pseudoRedCost = CoinMax(1.0e-2 * reducedCost[iColumn],
209                                                 downArray_[i]) * random[i];
210            } else if (upper[iColumn] - value <= integerTolerance) {
211                candidate[cnt].var = iColumn;
212                candidate[cnt++].pseudoRedCost = CoinMax(-1.0e-2 * reducedCost[iColumn],
213                                                 downArray_[i]) * random[i];
214            }
215        } else {
216            numberFixedAlready++;
217        }
218    }
219#ifdef CLP_INVESTIGATE
220    printf("cutoff %g obj %g - %d free, %d fixed\n",
221           model_->getCutoff(), solver->getObjValue(), numberFree,
222           numberFixedAlready);
223#endif
224    return cnt;
225    //return CbcHeuristicDive::fixOtherVariables(solver, solution,
226    //                               candidate, random);
227}
228
Note: See TracBrowser for help on using the repository browser.