source: trunk/Cbc/src/CbcHeuristicDiveLineSearch.cpp @ 1573

Last change on this file since 1573 was 1573, checked in by lou, 8 years ago

Change to EPL license notice.

File size: 3.8 KB
Line 
1/* $Id: CbcHeuristicDiveLineSearch.cpp 1173 2009-06-04 09:44:10Z 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 "CbcHeuristicDiveLineSearch.hpp"
12#include "CbcStrategy.hpp"
13
14// Default Constructor
15CbcHeuristicDiveLineSearch::CbcHeuristicDiveLineSearch()
16        : CbcHeuristicDive()
17{
18}
19
20// Constructor from model
21CbcHeuristicDiveLineSearch::CbcHeuristicDiveLineSearch(CbcModel & model)
22        : CbcHeuristicDive(model)
23{
24}
25
26// Destructor
27CbcHeuristicDiveLineSearch::~CbcHeuristicDiveLineSearch ()
28{
29}
30
31// Clone
32CbcHeuristicDiveLineSearch *
33CbcHeuristicDiveLineSearch::clone() const
34{
35    return new CbcHeuristicDiveLineSearch(*this);
36}
37
38// Create C++ lines to get to current state
39void
40CbcHeuristicDiveLineSearch::generateCpp( FILE * fp)
41{
42    CbcHeuristicDiveLineSearch other;
43    fprintf(fp, "0#include \"CbcHeuristicDiveLineSearch.hpp\"\n");
44    fprintf(fp, "3  CbcHeuristicDiveLineSearch heuristicDiveLineSearch(*cbcModel);\n");
45    CbcHeuristic::generateCpp(fp, "heuristicDiveLineSearch");
46    fprintf(fp, "3  cbcModel->addHeuristic(&heuristicDiveLineSearch);\n");
47}
48
49// Copy constructor
50CbcHeuristicDiveLineSearch::CbcHeuristicDiveLineSearch(const CbcHeuristicDiveLineSearch & rhs)
51        :
52        CbcHeuristicDive(rhs)
53{
54}
55
56// Assignment operator
57CbcHeuristicDiveLineSearch &
58CbcHeuristicDiveLineSearch::operator=( const CbcHeuristicDiveLineSearch & rhs)
59{
60    if (this != &rhs) {
61        CbcHeuristicDive::operator=(rhs);
62    }
63    return *this;
64}
65
66bool
67CbcHeuristicDiveLineSearch::selectVariableToBranch(OsiSolverInterface* solver,
68        const double* newSolution,
69        int& bestColumn,
70        int& bestRound)
71{
72    int numberIntegers = model_->numberIntegers();
73    const int * integerVariable = model_->integerVariable();
74    double integerTolerance = model_->getDblParam(CbcModel::CbcIntegerTolerance);
75
76    // get the LP relaxation solution at the root node
77    double * rootNodeLPSol = model_->continuousSolution();
78
79    bestColumn = -1;
80    bestRound = -1; // -1 rounds down, +1 rounds up
81    double bestRelDistance = DBL_MAX;
82    bool allTriviallyRoundableSoFar = true;
83    for (int i = 0; i < numberIntegers; i++) {
84        int iColumn = integerVariable[i];
85        double rootValue = rootNodeLPSol[iColumn];
86        double value = newSolution[iColumn];
87        double fraction = value - floor(value);
88        int round = 0;
89        if (fabs(floor(value + 0.5) - value) > integerTolerance) {
90            if (allTriviallyRoundableSoFar || (downLocks_[i] > 0 && upLocks_[i] > 0)) {
91
92                if (allTriviallyRoundableSoFar && downLocks_[i] > 0 && upLocks_[i] > 0) {
93                    allTriviallyRoundableSoFar = false;
94                    bestRelDistance = DBL_MAX;
95                }
96
97                double relDistance;
98                if (value < rootValue) {
99                    round = -1;
100                    relDistance = fraction / (rootValue - value);
101                } else if (value > rootValue) {
102                    round = 1;
103                    relDistance = (1.0 - fraction) / (value - rootValue);
104                } else {
105                    round = -1;
106                    relDistance = DBL_MAX;
107                }
108
109                // if variable is not binary, penalize it
110                if (!solver->isBinary(iColumn))
111                    relDistance *= 1000.0;
112
113                if (relDistance < bestRelDistance) {
114                    bestColumn = iColumn;
115                    bestRelDistance = relDistance;
116                    bestRound = round;
117                }
118            }
119        }
120    }
121    return allTriviallyRoundableSoFar;
122}
123
Note: See TracBrowser for help on using the repository browser.