source: trunk/Cbc/src/CbcPartialNodeInfo.cpp @ 1432

Last change on this file since 1432 was 1432, checked in by bjarni, 9 years ago

Added extra return at end of each source file where needed, to remove possible linefeed conflicts (NightlyBuild? errors)

File size: 9.0 KB
Line 
1// Edwin 11/24/09 carved from CbcNode
2#if defined(_MSC_VER)
3// Turn off compiler warning about long names
4#  pragma warning(disable:4786)
5#endif
6
7#include "CbcConfig.h"
8
9#include <string>
10//#define CBC_DEBUG 1
11//#define CHECK_CUT_COUNTS
12//#define CHECK_NODE
13//#define CBC_CHECK_BASIS
14#include <cassert>
15#include <cfloat>
16#define CUTS
17#include "OsiSolverInterface.hpp"
18#include "OsiChooseVariable.hpp"
19#include "OsiAuxInfo.hpp"
20#include "OsiSolverBranch.hpp"
21#include "CoinWarmStartBasis.hpp"
22#include "CoinTime.hpp"
23#include "CbcModel.hpp"
24#include "CbcNode.hpp"
25#include "CbcStatistics.hpp"
26#include "CbcStrategy.hpp"
27#include "CbcBranchActual.hpp"
28#include "CbcBranchDynamic.hpp"
29#include "OsiRowCut.hpp"
30#include "OsiRowCutDebugger.hpp"
31#include "OsiCuts.hpp"
32#include "CbcCountRowCut.hpp"
33#include "CbcFeasibilityBase.hpp"
34#include "CbcMessage.hpp"
35#ifdef COIN_HAS_CLP
36#include "OsiClpSolverInterface.hpp"
37#include "ClpSimplexOther.hpp"
38#endif
39using namespace std;
40#include "CglCutGenerator.hpp"
41
42// Default constructor
43CbcPartialNodeInfo::CbcPartialNodeInfo()
44
45        : CbcNodeInfo(),
46        basisDiff_(NULL),
47        variables_(NULL),
48        newBounds_(NULL),
49        numberChangedBounds_(0)
50
51{ /* this space intentionally left blank */ }
52
53// Constructor from current state
54CbcPartialNodeInfo::CbcPartialNodeInfo (CbcNodeInfo *parent, CbcNode *owner,
55                                        int numberChangedBounds,
56                                        const int *variables,
57                                        const double *boundChanges,
58                                        const CoinWarmStartDiff *basisDiff)
59        : CbcNodeInfo(parent, owner)
60{
61    basisDiff_ = basisDiff->clone() ;
62#ifdef CBC_CHECK_BASIS
63    std::cout << "Constructor (" << this << ") " << std::endl ;
64#endif
65
66    numberChangedBounds_ = numberChangedBounds;
67    int size = numberChangedBounds_ * (sizeof(double) + sizeof(int));
68    char * temp = new char [size];
69    newBounds_ = reinterpret_cast<double *> (temp);
70    variables_ = reinterpret_cast<int *> (newBounds_ + numberChangedBounds_);
71
72    int i ;
73    for (i = 0; i < numberChangedBounds_; i++) {
74        variables_[i] = variables[i];
75        newBounds_[i] = boundChanges[i];
76    }
77}
78
79CbcPartialNodeInfo::CbcPartialNodeInfo (const CbcPartialNodeInfo & rhs)
80
81        : CbcNodeInfo(rhs)
82
83{
84    basisDiff_ = rhs.basisDiff_->clone() ;
85
86#ifdef CBC_CHECK_BASIS
87    std::cout << "Copy constructor (" << this << ") from " << this << std::endl ;
88#endif
89    numberChangedBounds_ = rhs.numberChangedBounds_;
90    int size = numberChangedBounds_ * (sizeof(double) + sizeof(int));
91    char * temp = new char [size];
92    newBounds_ = reinterpret_cast<double *> (temp);
93    variables_ = reinterpret_cast<int *> (newBounds_ + numberChangedBounds_);
94
95    int i ;
96    for (i = 0; i < numberChangedBounds_; i++) {
97        variables_[i] = rhs.variables_[i];
98        newBounds_[i] = rhs.newBounds_[i];
99    }
100}
101
102CbcNodeInfo *
103CbcPartialNodeInfo::clone() const
104{
105    return (new CbcPartialNodeInfo(*this));
106}
107
108
109CbcPartialNodeInfo::~CbcPartialNodeInfo ()
110{
111    delete basisDiff_ ;
112    delete [] newBounds_;
113}
114
115
116/**
117   The basis supplied as a parameter is incrementally modified, and lower and
118   upper bounds on variables in the model are incrementally modified. Any
119   cuts associated with this node are added to the list in addCuts.
120*/
121
122void CbcPartialNodeInfo::applyToModel (CbcModel *model,
123                                       CoinWarmStartBasis *&basis,
124                                       CbcCountRowCut **addCuts,
125                                       int &currentNumberCuts) const
126
127{
128    OsiSolverInterface *solver = model->solver();
129    if ((active_&4) != 0) {
130        basis->applyDiff(basisDiff_) ;
131#ifdef CBC_CHECK_BASIS
132        std::cout << "Basis (after applying " << this << ") " << std::endl ;
133        basis->print() ;
134#endif
135    }
136
137    // branch - do bounds
138    int i;
139    if ((active_&1) != 0) {
140        for (i = 0; i < numberChangedBounds_; i++) {
141            int variable = variables_[i];
142            int k = variable & 0x3fffffff;
143            if ((variable&0x80000000) == 0) {
144                // lower bound changing
145                //#define CBC_PRINT2
146#ifdef CBC_PRINT2
147                if (solver->getColLower()[k] != newBounds_[i])
148                    printf("lower change for column %d - from %g to %g\n", k, solver->getColLower()[k], newBounds_[i]);
149#endif
150#ifndef NDEBUG
151                if ((variable&0x40000000) == 0 && false) {
152                    double oldValue = solver->getColLower()[k];
153                    assert (newBounds_[i] > oldValue - 1.0e-8);
154                    if (newBounds_[i] < oldValue + 1.0e-8)
155                        printf("bad null lower change for column %d - bound %g\n", k, oldValue);
156                }
157#endif
158                solver->setColLower(k, newBounds_[i]);
159            } else {
160                // upper bound changing
161#ifdef CBC_PRINT2
162                if (solver->getColUpper()[k] != newBounds_[i])
163                    printf("upper change for column %d - from %g to %g\n", k, solver->getColUpper()[k], newBounds_[i]);
164#endif
165#ifndef NDEBUG
166                if ((variable&0x40000000) == 0 && false) {
167                    double oldValue = solver->getColUpper()[k];
168                    assert (newBounds_[i] < oldValue + 1.0e-8);
169                    if (newBounds_[i] > oldValue - 1.0e-8)
170                        printf("bad null upper change for column %d - bound %g\n", k, oldValue);
171                }
172#endif
173                solver->setColUpper(k, newBounds_[i]);
174            }
175        }
176    }
177    if ((active_&2) != 0) {
178        for (i = 0; i < numberCuts_; i++) {
179            addCuts[currentNumberCuts+i] = cuts_[i];
180            if (cuts_[i] && model->messageHandler()->logLevel() > 4) {
181                cuts_[i]->print();
182            }
183        }
184
185        currentNumberCuts += numberCuts_;
186    }
187    return ;
188}
189// Just apply bounds to one variable (1=>infeasible)
190int
191CbcPartialNodeInfo::applyBounds(int iColumn, double & lower, double & upper, int force)
192{
193    // branch - do bounds
194    int i;
195    int found = 0;
196    double newLower = -COIN_DBL_MAX;
197    double newUpper = COIN_DBL_MAX;
198    for (i = 0; i < numberChangedBounds_; i++) {
199        int variable = variables_[i];
200        int k = variable & 0x3fffffff;
201        if (k == iColumn) {
202            if ((variable&0x80000000) == 0) {
203                // lower bound changing
204                found |= 1;
205                newLower = CoinMax(newLower, newBounds_[i]);
206                if ((force&1) == 0) {
207                    if (lower > newBounds_[i])
208                        printf("%d odd lower going from %g to %g\n", iColumn, lower, newBounds_[i]);
209                    lower = newBounds_[i];
210                } else {
211                    newBounds_[i] = lower;
212                    variables_[i] |= 0x40000000; // say can go odd way
213                }
214            } else {
215                // upper bound changing
216                found |= 2;
217                newUpper = CoinMin(newUpper, newBounds_[i]);
218                if ((force&2) == 0) {
219                    if (upper < newBounds_[i])
220                        printf("%d odd upper going from %g to %g\n", iColumn, upper, newBounds_[i]);
221                    upper = newBounds_[i];
222                } else {
223                    newBounds_[i] = upper;
224                    variables_[i] |= 0x40000000; // say can go odd way
225                }
226            }
227        }
228    }
229    newLower = CoinMax(newLower, lower);
230    newUpper = CoinMin(newUpper, upper);
231    int nAdd = 0;
232    if ((force&2) != 0 && (found&2) == 0) {
233        // need to add new upper
234        nAdd++;
235    }
236    if ((force&1) != 0 && (found&1) == 0) {
237        // need to add new lower
238        nAdd++;
239    }
240    if (nAdd) {
241        int size = (numberChangedBounds_ + nAdd) * (sizeof(double) + sizeof(int));
242        char * temp = new char [size];
243        double * newBounds = reinterpret_cast<double *> (temp);
244        int * variables = reinterpret_cast<int *> (newBounds + numberChangedBounds_ + nAdd);
245
246        int i ;
247        for (i = 0; i < numberChangedBounds_; i++) {
248            variables[i] = variables_[i];
249            newBounds[i] = newBounds_[i];
250        }
251        delete [] newBounds_;
252        newBounds_ = newBounds;
253        variables_ = variables;
254        if ((force&2) != 0 && (found&2) == 0) {
255            // need to add new upper
256            int variable = iColumn | 0x80000000;
257            variables_[numberChangedBounds_] = variable;
258            newBounds_[numberChangedBounds_++] = newUpper;
259        }
260        if ((force&1) != 0 && (found&1) == 0) {
261            // need to add new lower
262            int variable = iColumn;
263            variables_[numberChangedBounds_] = variable;
264            newBounds_[numberChangedBounds_++] = newLower;
265        }
266    }
267
268    return (newUpper >= newLower) ? 0 : 1;
269}
270
271/* Builds up row basis backwards (until original model).
272   Returns NULL or previous one to apply .
273   Depends on Free being 0 and impossible for cuts
274*/
275
276CbcNodeInfo *
277CbcPartialNodeInfo::buildRowBasis(CoinWarmStartBasis & basis ) const
278
279{
280    basis.applyDiff(basisDiff_) ;
281
282    return parent_ ;
283}
284
Note: See TracBrowser for help on using the repository browser.