source: branches/sandbox/Cbc/src/CbcHeuristicDivePseudoCost.cpp @ 1286

Last change on this file since 1286 was 1286, checked in by EdwinStraver, 10 years ago

Changed formatting using AStyle -A4 -p

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}
Note: See TracBrowser for help on using the repository browser.