source: trunk/Cbc/src/CbcSimpleIntegerPseudoCost.cpp @ 1424

Last change on this file since 1424 was 1357, checked in by coin, 10 years ago

run 'astyle -A4 -p' and dos2unix

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