source: trunk/Cbc/src/CbcHeuristicDiveVectorLength.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: 4.5 KB
Line 
1/* $Id: CbcHeuristicDiveVectorLength.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 "CbcHeuristicDiveVectorLength.hpp"
12#include "CbcStrategy.hpp"
13
14// Default Constructor
15CbcHeuristicDiveVectorLength::CbcHeuristicDiveVectorLength()
16        : CbcHeuristicDive()
17{
18}
19
20// Constructor from model
21CbcHeuristicDiveVectorLength::CbcHeuristicDiveVectorLength(CbcModel & model)
22        : CbcHeuristicDive(model)
23{
24}
25
26// Destructor
27CbcHeuristicDiveVectorLength::~CbcHeuristicDiveVectorLength ()
28{
29}
30
31// Clone
32CbcHeuristicDiveVectorLength *
33CbcHeuristicDiveVectorLength::clone() const
34{
35    return new CbcHeuristicDiveVectorLength(*this);
36}
37
38// Create C++ lines to get to current state
39void
40CbcHeuristicDiveVectorLength::generateCpp( FILE * fp)
41{
42    CbcHeuristicDiveVectorLength other;
43    fprintf(fp, "0#include \"CbcHeuristicDiveVectorLength.hpp\"\n");
44    fprintf(fp, "3  CbcHeuristicDiveVectorLength heuristicDiveVectorLength(*cbcModel);\n");
45    CbcHeuristic::generateCpp(fp, "heuristicDiveVectorLength");
46    fprintf(fp, "3  cbcModel->addHeuristic(&heuristicDiveVectorLength);\n");
47}
48
49// Copy constructor
50CbcHeuristicDiveVectorLength::CbcHeuristicDiveVectorLength(const CbcHeuristicDiveVectorLength & rhs)
51        :
52        CbcHeuristicDive(rhs)
53{
54}
55
56// Assignment operator
57CbcHeuristicDiveVectorLength &
58CbcHeuristicDiveVectorLength::operator=( const CbcHeuristicDiveVectorLength & rhs)
59{
60    if (this != &rhs) {
61        CbcHeuristicDive::operator=(rhs);
62    }
63    return *this;
64}
65
66bool
67CbcHeuristicDiveVectorLength::selectVariableToBranch(OsiSolverInterface* solver,
68        const double* newSolution,
69        int& bestColumn,
70        int& bestRound)
71{
72    const double * objective = solver->getObjCoefficients();
73    double direction = solver->getObjSense(); // 1 for min, -1 for max
74
75    const int * columnLength = matrix_.getVectorLengths();
76    int numberIntegers = model_->numberIntegers();
77    const int * integerVariable = model_->integerVariable();
78    double integerTolerance = model_->getDblParam(CbcModel::CbcIntegerTolerance);
79
80    bestColumn = -1;
81    bestRound = -1; // -1 rounds down, +1 rounds up
82    double bestScore = COIN_DBL_MAX;
83    bool allTriviallyRoundableSoFar = true;
84    int bestPriority = COIN_INT_MAX;
85    for (int i = 0; i < numberIntegers; i++) {
86        int iColumn = integerVariable[i];
87        if (!isHeuristicInteger(solver,iColumn))
88          continue;
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 = COIN_DBL_MAX;
98                }
99
100                // the variable cannot be rounded
101                double obj = direction * objective[iColumn];
102                if (obj > smallObjective_) {
103                    round = 1; // round up
104                } else if (obj < -smallObjective_) {
105                    round = -1; // round down
106                } else {
107                  if (fraction<0.4)
108                    round = -1;
109                  else
110                    round = 1;
111                }
112                double objDelta;
113                if (round == 1)
114                    objDelta = (1.0 - fraction) * CoinMax(obj,smallObjective_);
115                else
116                    objDelta = - fraction * CoinMin(obj,-smallObjective_);
117
118                // we want the smaller score
119                double score = objDelta / (static_cast<double> (columnLength[iColumn]) + 1.0);
120
121                // if variable is not binary, penalize it
122                if (!solver->isBinary(iColumn))
123                    score *= 1000.0;
124
125                // if priorities then use
126                if (priority_) {
127                  int thisRound=static_cast<int>(priority_[i].direction);
128                  if ((thisRound&1)!=0) 
129                    round = ((thisRound&2)==0) ? -1 : +1;
130                  if (priority_[i].priority>bestPriority) {
131                    score=COIN_DBL_MAX;
132                  } else if (priority_[i].priority<bestPriority) {
133                    bestPriority=static_cast<int>(priority_[i].priority);
134                    bestScore=COIN_DBL_MAX;
135                  }
136                }
137                if (score < bestScore) {
138                    bestColumn = iColumn;
139                    bestScore = score;
140                    bestRound = round;
141                }
142            }
143        }
144    }
145    return allTriviallyRoundableSoFar;
146}
147
Note: See TracBrowser for help on using the repository browser.