source: stable/2.6/Cbc/src/CbcSimpleIntegerPseudoCost.cpp @ 2122

Last change on this file since 2122 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: 8.4 KB
Line 
1// Edwin 11/10/2009-- carved out of CbcBranchActual
2#if defined(_MSC_VER)
3// Turn off compiler warning about long names
4#  pragma warning(disable:4786)
5#endif
6#include <cassert>
7#include <cstdlib>
8#include <cmath>
9#include <cfloat>
10//#define CBC_DEBUG
11
12#include "CoinTypes.hpp"
13#include "OsiSolverInterface.hpp"
14#include "OsiSolverBranch.hpp"
15#include "CbcModel.hpp"
16#include "CbcMessage.hpp"
17#include "CbcSimpleIntegerPseudoCost.hpp"
18#include "CbcSimpleIntegerDynamicPseudoCost.hpp"
19#include "CbcBranchActual.hpp"
20#include "CoinSort.hpp"
21#include "CoinError.hpp"
22
23//##############################################################################
24
25/** Default Constructor
26
27  Equivalent to an unspecified binary variable.
28*/
29CbcSimpleIntegerPseudoCost::CbcSimpleIntegerPseudoCost ()
30        : CbcSimpleInteger(),
31        downPseudoCost_(1.0e-5),
32        upPseudoCost_(1.0e-5),
33        upDownSeparator_(-1.0),
34        method_(0)
35{
36}
37
38/** Useful constructor
39
40  Loads actual upper & lower bounds for the specified variable.
41*/
42CbcSimpleIntegerPseudoCost::CbcSimpleIntegerPseudoCost (CbcModel * model,
43        int iColumn, double breakEven)
44        : CbcSimpleInteger(model, iColumn, breakEven)
45{
46    const double * cost = model->getObjCoefficients();
47    double costValue = CoinMax(1.0e-5, fabs(cost[iColumn]));
48    // treat as if will cost what it says up
49    upPseudoCost_ = costValue;
50    // and balance at breakeven
51    downPseudoCost_ = ((1.0 - breakEven_) * upPseudoCost_) / breakEven_;
52    upDownSeparator_ = -1.0;
53    method_ = 0;
54}
55
56/** Useful constructor
57
58  Loads actual upper & lower bounds for the specified variable.
59*/
60CbcSimpleIntegerPseudoCost::CbcSimpleIntegerPseudoCost (CbcModel * model,
61        int iColumn, double downPseudoCost,
62        double upPseudoCost)
63        : CbcSimpleInteger(model, iColumn)
64{
65    downPseudoCost_ = CoinMax(1.0e-10, downPseudoCost);
66    upPseudoCost_ = CoinMax(1.0e-10, upPseudoCost);
67    breakEven_ = upPseudoCost_ / (upPseudoCost_ + downPseudoCost_);
68    upDownSeparator_ = -1.0;
69    method_ = 0;
70}
71// Useful constructor - passed and model index and pseudo costs
72CbcSimpleIntegerPseudoCost::CbcSimpleIntegerPseudoCost (CbcModel * model,
73        int /*dummy*/,
74        int iColumn,
75        double downPseudoCost, double upPseudoCost)
76{
77    *this = CbcSimpleIntegerPseudoCost(model, iColumn, downPseudoCost, upPseudoCost);
78    columnNumber_ = iColumn;
79}
80
81// Copy constructor
82CbcSimpleIntegerPseudoCost::CbcSimpleIntegerPseudoCost ( const CbcSimpleIntegerPseudoCost & rhs)
83        : CbcSimpleInteger(rhs),
84        downPseudoCost_(rhs.downPseudoCost_),
85        upPseudoCost_(rhs.upPseudoCost_),
86        upDownSeparator_(rhs.upDownSeparator_),
87        method_(rhs.method_)
88
89{
90}
91
92// Clone
93CbcObject *
94CbcSimpleIntegerPseudoCost::clone() const
95{
96    return new CbcSimpleIntegerPseudoCost(*this);
97}
98
99// Assignment operator
100CbcSimpleIntegerPseudoCost &
101CbcSimpleIntegerPseudoCost::operator=( const CbcSimpleIntegerPseudoCost & rhs)
102{
103    if (this != &rhs) {
104        CbcSimpleInteger::operator=(rhs);
105        downPseudoCost_ = rhs.downPseudoCost_;
106        upPseudoCost_ = rhs.upPseudoCost_;
107        upDownSeparator_ = rhs.upDownSeparator_;
108        method_ = rhs.method_;
109    }
110    return *this;
111}
112
113// Destructor
114CbcSimpleIntegerPseudoCost::~CbcSimpleIntegerPseudoCost ()
115{
116}
117CbcBranchingObject *
118CbcSimpleIntegerPseudoCost::createCbcBranch(OsiSolverInterface * solver, const OsiBranchingInformation * /*info*/, int way)
119{
120    //OsiSolverInterface * solver = model_->solver();
121    const double * solution = model_->testSolution();
122    const double * lower = solver->getColLower();
123    const double * upper = solver->getColUpper();
124    double value = solution[columnNumber_];
125    value = CoinMax(value, lower[columnNumber_]);
126    value = CoinMin(value, upper[columnNumber_]);
127#ifndef NDEBUG
128    double nearest = floor(value + 0.5);
129    double integerTolerance =
130        model_->getDblParam(CbcModel::CbcIntegerTolerance);
131    assert (upper[columnNumber_] > lower[columnNumber_]);
132#endif
133    if (!model_->hotstartSolution()) {
134        assert (fabs(value - nearest) > integerTolerance);
135    } else {
136        const double * hotstartSolution = model_->hotstartSolution();
137        double targetValue = hotstartSolution[columnNumber_];
138        if (way > 0)
139            value = targetValue - 0.1;
140        else
141            value = targetValue + 0.1;
142    }
143    CbcIntegerPseudoCostBranchingObject * newObject =
144        new CbcIntegerPseudoCostBranchingObject(model_, columnNumber_, way,
145                                                value);
146    double up =  upPseudoCost_ * (ceil(value) - value);
147    double down =  downPseudoCost_ * (value - floor(value));
148    double changeInGuessed = up - down;
149    if (way > 0)
150        changeInGuessed = - changeInGuessed;
151    changeInGuessed = CoinMax(0.0, changeInGuessed);
152    //if (way>0)
153    //changeInGuessed += 1.0e8; // bias to stay up
154    newObject->setChangeInGuessed(changeInGuessed);
155    newObject->setOriginalObject(this);
156    return newObject;
157}
158double
159CbcSimpleIntegerPseudoCost::infeasibility(const OsiBranchingInformation * /*info*/,
160        int &preferredWay) const
161{
162    OsiSolverInterface * solver = model_->solver();
163    const double * solution = model_->testSolution();
164    const double * lower = solver->getColLower();
165    const double * upper = solver->getColUpper();
166    if (upper[columnNumber_] == lower[columnNumber_]) {
167        // fixed
168        preferredWay = 1;
169        return 0.0;
170    }
171    double value = solution[columnNumber_];
172    value = CoinMax(value, lower[columnNumber_]);
173    value = CoinMin(value, upper[columnNumber_]);
174    /*printf("%d %g %g %g %g\n",columnNumber_,value,lower[columnNumber_],
175      solution[columnNumber_],upper[columnNumber_]);*/
176    double nearest = floor(value + 0.5);
177    double integerTolerance =
178        model_->getDblParam(CbcModel::CbcIntegerTolerance);
179    double below = floor(value + integerTolerance);
180    double above = below + 1.0;
181    if (above > upper[columnNumber_]) {
182        above = below;
183        below = above - 1;
184    }
185    double downCost = CoinMax((value - below) * downPseudoCost_, 0.0);
186    double upCost = CoinMax((above - value) * upPseudoCost_, 0.0);
187    if (downCost >= upCost)
188        preferredWay = 1;
189    else
190        preferredWay = -1;
191    // See if up down choice set
192    if (upDownSeparator_ > 0.0) {
193        preferredWay = (value - below >= upDownSeparator_) ? 1 : -1;
194    }
195    if (preferredWay_)
196        preferredWay = preferredWay_;
197    if (fabs(value - nearest) <= integerTolerance) {
198        return 0.0;
199    } else {
200        // can't get at model so 1,2 don't make sense
201        assert(method_ < 1 || method_ > 2);
202        if (!method_)
203            return CoinMin(downCost, upCost);
204        else
205            return CoinMax(downCost, upCost);
206    }
207}
208
209// Return "up" estimate
210double
211CbcSimpleIntegerPseudoCost::upEstimate() const
212{
213    OsiSolverInterface * solver = model_->solver();
214    const double * solution = model_->testSolution();
215    const double * lower = solver->getColLower();
216    const double * upper = solver->getColUpper();
217    double value = solution[columnNumber_];
218    value = CoinMax(value, lower[columnNumber_]);
219    value = CoinMin(value, upper[columnNumber_]);
220    if (upper[columnNumber_] == lower[columnNumber_]) {
221        // fixed
222        return 0.0;
223    }
224    double integerTolerance =
225        model_->getDblParam(CbcModel::CbcIntegerTolerance);
226    double below = floor(value + integerTolerance);
227    double above = below + 1.0;
228    if (above > upper[columnNumber_]) {
229        above = below;
230        below = above - 1;
231    }
232    double upCost = CoinMax((above - value) * upPseudoCost_, 0.0);
233    return upCost;
234}
235// Return "down" estimate
236double
237CbcSimpleIntegerPseudoCost::downEstimate() const
238{
239    OsiSolverInterface * solver = model_->solver();
240    const double * solution = model_->testSolution();
241    const double * lower = solver->getColLower();
242    const double * upper = solver->getColUpper();
243    double value = solution[columnNumber_];
244    value = CoinMax(value, lower[columnNumber_]);
245    value = CoinMin(value, upper[columnNumber_]);
246    if (upper[columnNumber_] == lower[columnNumber_]) {
247        // fixed
248        return 0.0;
249    }
250    double integerTolerance =
251        model_->getDblParam(CbcModel::CbcIntegerTolerance);
252    double below = floor(value + integerTolerance);
253    double above = below + 1.0;
254    if (above > upper[columnNumber_]) {
255        above = below;
256        below = above - 1;
257    }
258    double downCost = CoinMax((value - below) * downPseudoCost_, 0.0);
259    return downCost;
260}
261
Note: See TracBrowser for help on using the repository browser.