source: trunk/Cbc/src/CbcHeuristicDivePseudoCost.cpp @ 2280

Last change on this file since 2280 was 2280, checked in by forrest, 3 years ago

allow heuristics to see if integers are 'optional'

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