source: branches/sandbox/Cbc/src/CbcSimpleIntegerPseudoCost.cpp @ 1293

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