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

Last change on this file since 1899 was 1899, checked in by stefan, 5 years ago

fixup svn properties

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