source: trunk/Cbc/src/CbcNodeInfo.cpp @ 1569

Last change on this file since 1569 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: 13.8 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#include "CbcNodeInfo.hpp"
42
43// Default Constructor
44CbcNodeInfo::CbcNodeInfo ()
45        :
46        numberPointingToThis_(0),
47        parent_(NULL),
48        parentBranch_(NULL),
49        owner_(NULL),
50        numberCuts_(0),
51        nodeNumber_(0),
52        cuts_(NULL),
53        numberRows_(0),
54        numberBranchesLeft_(0),
55        active_(7)
56{
57#ifdef CHECK_NODE
58    printf("CbcNodeInfo %x Constructor\n", this);
59#endif
60}
61
62void
63CbcNodeInfo::setParentBasedData()
64{
65    if (parent_) {
66        numberRows_ = parent_->numberRows_ + parent_->numberCuts_;
67        //parent_->increment();
68        if (parent_->owner()) {
69            const OsiBranchingObject* br = parent_->owner()->branchingObject();
70            assert(br);
71            parentBranch_ = br->clone();
72        }
73    }
74}
75
76void
77CbcNodeInfo::unsetParentBasedData()
78{
79    if (parent_) {
80        numberRows_ = 0;
81        if (parent_->owner()) {
82            delete parentBranch_;
83            parentBranch_ = NULL;
84        }
85    }
86}
87
88#ifdef JJF_ZERO
89// Constructor given parent
90CbcNodeInfo::CbcNodeInfo (CbcNodeInfo * parent)
91        :
92        numberPointingToThis_(2),
93        parent_(parent),
94        parentBranch_(NULL),
95        owner_(NULL),
96        numberCuts_(0),
97        nodeNumber_(0),
98        cuts_(NULL),
99        numberRows_(0),
100        numberBranchesLeft_(2),
101        active_(7)
102{
103#ifdef CHECK_NODE
104    printf("CbcNodeInfo %x Constructor from parent %x\n", this, parent_);
105#endif
106    //setParentBasedData();
107}
108#endif
109
110// Copy Constructor
111CbcNodeInfo::CbcNodeInfo (const CbcNodeInfo & rhs)
112        :
113        numberPointingToThis_(rhs.numberPointingToThis_),
114        parent_(rhs.parent_),
115        parentBranch_(NULL),
116        owner_(rhs.owner_),
117        numberCuts_(rhs.numberCuts_),
118        nodeNumber_(rhs.nodeNumber_),
119        cuts_(NULL),
120        numberRows_(rhs.numberRows_),
121        numberBranchesLeft_(rhs.numberBranchesLeft_),
122        active_(rhs.active_)
123{
124#ifdef CHECK_NODE
125    printf("CbcNodeInfo %x Copy constructor\n", this);
126#endif
127    if (numberCuts_) {
128        cuts_ = new CbcCountRowCut * [numberCuts_];
129        int n = 0;
130        for (int i = 0; i < numberCuts_; i++) {
131            CbcCountRowCut * thisCut = rhs.cuts_[i];
132            if (thisCut) {
133                // I think this is correct - new one should take priority
134                thisCut->setInfo(this, n);
135                thisCut->increment(numberBranchesLeft_);
136                cuts_[n++] = thisCut;
137            }
138        }
139        numberCuts_ = n;
140    }
141    if (rhs.parentBranch_) {
142        parentBranch_ = rhs.parentBranch_->clone();
143    }
144}
145// Constructor given parent and owner
146CbcNodeInfo::CbcNodeInfo (CbcNodeInfo * parent, CbcNode * owner)
147        :
148        numberPointingToThis_(2),
149        parent_(parent),
150        parentBranch_(NULL),
151        owner_(owner),
152        numberCuts_(0),
153        nodeNumber_(0),
154        cuts_(NULL),
155        numberRows_(0),
156        numberBranchesLeft_(2),
157        active_(7)
158{
159#ifdef CHECK_NODE
160    printf("CbcNodeInfo %x Constructor from parent %x\n", this, parent_);
161#endif
162    //setParentBasedData();
163}
164
165/**
166   Take care to detach from the owning CbcNode and decrement the reference
167   count in the parent.  If this is the last nodeInfo object pointing to the
168   parent, make a recursive call to delete the parent.
169*/
170CbcNodeInfo::~CbcNodeInfo()
171{
172#ifdef CHECK_NODE
173    printf("CbcNodeInfo %x Destructor parent %x\n", this, parent_);
174#endif
175
176    assert(!numberPointingToThis_);
177    // But there may be some left (max nodes?)
178    for (int i = 0; i < numberCuts_; i++) {
179        if (cuts_[i]) {
180#ifndef GLOBAL_CUTS_JUST_POINTERS
181            delete cuts_[i];
182#else
183            if (cuts_[i]->globallyValidAsInteger() != 2)
184                delete cuts_[i];
185#endif
186        }
187    }
188    delete [] cuts_;
189    if (owner_)
190        owner_->nullNodeInfo();
191    if (parent_) {
192        int numberLinks = parent_->decrement();
193        if (!numberLinks) delete parent_;
194    }
195    delete parentBranch_;
196}
197
198
199//#define ALLCUTS
200void
201CbcNodeInfo::decrementCuts(int change)
202{
203    int i;
204    // get rid of all remaining if negative
205    int changeThis;
206    if (change < 0)
207        changeThis = numberBranchesLeft_;
208    else
209        changeThis = change;
210    // decrement cut counts
211    for (i = 0; i < numberCuts_; i++) {
212        if (cuts_[i]) {
213            int number = cuts_[i]->decrement(changeThis);
214            if (!number) {
215                //printf("info %x del cut %d %x\n",this,i,cuts_[i]);
216#ifndef GLOBAL_CUTS_JUST_POINTERS
217                delete cuts_[i];
218#else
219                if (cuts_[i]->globallyValidAsInteger() != 2)
220                    delete cuts_[i];
221#endif
222                cuts_[i] = NULL;
223            }
224        }
225    }
226}
227void
228CbcNodeInfo::incrementCuts(int change)
229{
230    int i;
231    assert (change > 0);
232    // increment cut counts
233    for (i = 0; i < numberCuts_; i++) {
234        if (cuts_[i])
235            cuts_[i]->increment(change);
236    }
237}
238void
239CbcNodeInfo::decrementParentCuts(CbcModel * model, int change)
240{
241    if (parent_) {
242        // get rid of all remaining if negative
243        int changeThis;
244        if (change < 0)
245            changeThis = numberBranchesLeft_;
246        else
247            changeThis = change;
248        int i;
249        // Get over-estimate of space needed for basis
250        CoinWarmStartBasis & dummy = model->workingBasis();
251        dummy.setSize(0, numberRows_ + numberCuts_);
252        buildRowBasis(dummy);
253        /* everything is zero (i.e. free) so we can use to see
254           if latest basis */
255        CbcNodeInfo * thisInfo = parent_;
256        while (thisInfo)
257            thisInfo = thisInfo->buildRowBasis(dummy);
258        // decrement cut counts
259        thisInfo = parent_;
260        int numberRows = numberRows_;
261        while (thisInfo) {
262            for (i = thisInfo->numberCuts_ - 1; i >= 0; i--) {
263                CoinWarmStartBasis::Status status = dummy.getArtifStatus(--numberRows);
264#ifdef ALLCUTS
265                status = CoinWarmStartBasis::isFree;
266#endif
267                if (thisInfo->cuts_[i]) {
268                    int number = 1;
269                    if (status != CoinWarmStartBasis::basic) {
270                        // tight - drop 1 or 2
271                        if (change < 0)
272                            number = thisInfo->cuts_[i]->decrement(changeThis);
273                        else
274                            number = thisInfo->cuts_[i]->decrement(change);
275                    }
276                    if (!number) {
277#ifndef GLOBAL_CUTS_JUST_POINTERS
278                        delete thisInfo->cuts_[i];
279#else
280                        if (thisInfo->cuts_[i]->globallyValidAsInteger() != 2)
281                            delete thisInfo->cuts_[i];
282#endif
283                        thisInfo->cuts_[i] = NULL;
284                    }
285                }
286            }
287            thisInfo = thisInfo->parent_;
288        }
289    }
290}
291#ifdef JJF_ZERO
292void
293CbcNodeInfo::incrementParentCuts(CbcModel * model, int change)
294{
295    if (parent_) {
296        int i;
297        // Get over-estimate of space needed for basis
298        CoinWarmStartBasis & dummy = model->workingBasis();
299        dummy.setSize(0, numberRows_ + numberCuts_);
300        /* everything is zero (i.e. free) so we can use to see
301           if latest basis */
302        buildRowBasis(dummy);
303        CbcNodeInfo * thisInfo = parent_;
304        while (thisInfo)
305            thisInfo = thisInfo->buildRowBasis(dummy);
306        // increment cut counts
307        thisInfo = parent_;
308        int numberRows = numberRows_;
309        while (thisInfo) {
310            for (i = thisInfo->numberCuts_ - 1; i >= 0; i--) {
311                CoinWarmStartBasis::Status status = dummy.getArtifStatus(--numberRows);
312#ifdef ALLCUTS
313                status = CoinWarmStartBasis::isFree;
314#endif
315                if (thisInfo->cuts_[i] && status != CoinWarmStartBasis::basic) {
316                    thisInfo->cuts_[i]->increment(change);
317                }
318            }
319            thisInfo = thisInfo->parent_;
320        }
321    }
322}
323#endif
324/*
325  Append cuts to the cuts_ array in a nodeInfo. The initial reference count
326  is set to numberToBranchOn, which will normally be the number of arms
327  defined for the CbcBranchingObject attached to the CbcNode that owns this
328  CbcNodeInfo.
329*/
330void
331CbcNodeInfo::addCuts (OsiCuts & cuts, int numberToBranchOn,
332                      /*int * whichGenerator,*/int numberPointingToThis)
333{
334    int numberCuts = cuts.sizeRowCuts();
335    if (numberCuts) {
336        int i;
337        if (!numberCuts_) {
338            cuts_ = new CbcCountRowCut * [numberCuts];
339        } else {
340            CbcCountRowCut ** temp = new CbcCountRowCut * [numberCuts+numberCuts_];
341            memcpy(temp, cuts_, numberCuts_*sizeof(CbcCountRowCut *));
342            delete [] cuts_;
343            cuts_ = temp;
344        }
345        for (i = 0; i < numberCuts; i++) {
346            CbcCountRowCut * thisCut = new CbcCountRowCut(*cuts.rowCutPtr(i),
347                    this, numberCuts_,
348                    -1, numberPointingToThis);
349            thisCut->increment(numberToBranchOn);
350            cuts_[numberCuts_++] = thisCut;
351#ifdef CBC_DEBUG
352#if CBC_DEBUG>1
353            int n = thisCut->row().getNumElements();
354            printf("Cut %d has %d entries, rhs %g %g =>", i, n, thisCut->lb(),
355                   thisCut->ub());
356            int j;
357            const int * index = thisCut->row().getIndices();
358            const double * element = thisCut->row().getElements();
359            for (j = 0; j < n; j++) {
360                printf(" (%d,%g)", index[j], element[j]);
361                assert(fabs(element[j]) > 1.00e-12);
362            }
363            printf("\n");
364#else
365            int n = thisCut->row().getNumElements();
366            int j;
367            const double * element = thisCut->row().getElements();
368            for (j = 0; j < n; j++) {
369                assert(fabs(element[j]) > 1.00e-12);
370            }
371#endif
372#endif
373        }
374    }
375}
376
377void
378CbcNodeInfo::addCuts(int numberCuts, CbcCountRowCut ** cut,
379                     int numberToBranchOn)
380{
381    if (numberCuts) {
382        int i;
383        if (!numberCuts_) {
384            cuts_ = new CbcCountRowCut * [numberCuts];
385        } else {
386            CbcCountRowCut ** temp = new CbcCountRowCut * [numberCuts+numberCuts_];
387            memcpy(temp, cuts_, numberCuts_*sizeof(CbcCountRowCut *));
388            delete [] cuts_;
389            cuts_ = temp;
390        }
391        for (i = 0; i < numberCuts; i++) {
392            CbcCountRowCut * thisCut = cut[i];
393            thisCut->setInfo(this, numberCuts_);
394            //printf("info %x cut %d %x\n",this,i,thisCut);
395            thisCut->increment(numberToBranchOn);
396            cuts_[numberCuts_++] = thisCut;
397#ifdef CBC_DEBUG
398            int n = thisCut->row().getNumElements();
399#if CBC_DEBUG>1
400            printf("Cut %d has %d entries, rhs %g %g =>", i, n, thisCut->lb(),
401                   thisCut->ub());
402#endif
403            int j;
404#if CBC_DEBUG>1
405            const int * index = thisCut->row().getIndices();
406#endif
407            const double * element = thisCut->row().getElements();
408            for (j = 0; j < n; j++) {
409#if CBC_DEBUG>1
410                printf(" (%d,%g)", index[j], element[j]);
411#endif
412                assert(fabs(element[j]) > 1.00e-12);
413            }
414            printf("\n");
415#endif
416        }
417    }
418}
419
420// delete cuts
421void
422CbcNodeInfo::deleteCuts(int numberToDelete, CbcCountRowCut ** cuts)
423{
424    int i;
425    int j;
426    int last = -1;
427    for (i = 0; i < numberToDelete; i++) {
428        CbcCountRowCut * next = cuts[i];
429        for (j = last + 1; j < numberCuts_; j++) {
430            if (next == cuts_[j])
431                break;
432        }
433        if (j == numberCuts_) {
434            // start from beginning
435            for (j = 0; j < last; j++) {
436                if (next == cuts_[j])
437                    break;
438            }
439            assert(j < last);
440        }
441        last = j;
442        int number = cuts_[j]->decrement();
443        if (!number) {
444#ifndef GLOBAL_CUTS_JUST_POINTERS
445            delete cuts_[j];
446#else
447            if (cuts_[j]->globallyValidAsInteger() != 2)
448                delete cuts_[j];
449#endif
450        }
451        cuts_[j] = NULL;
452    }
453    j = 0;
454    for (i = 0; i < numberCuts_; i++) {
455        if (cuts_[i])
456            cuts_[j++] = cuts_[i];
457    }
458    numberCuts_ = j;
459}
460
461// delete cuts
462void
463CbcNodeInfo::deleteCuts(int numberToDelete, int * which)
464{
465    int i;
466    for (i = 0; i < numberToDelete; i++) {
467        int iCut = which[i];
468        int number = cuts_[iCut]->decrement();
469        if (!number) {
470#ifndef GLOBAL_CUTS_JUST_POINTERS
471            delete cuts_[iCut];
472#else
473            if (cuts_[iCut]->globallyValidAsInteger() != 2)
474                delete cuts_[iCut];
475#endif
476        }
477        cuts_[iCut] = NULL;
478    }
479    int j = 0;
480    for (i = 0; i < numberCuts_; i++) {
481        if (cuts_[i])
482            cuts_[j++] = cuts_[i];
483    }
484    numberCuts_ = j;
485}
486
487// Really delete a cut
488void
489CbcNodeInfo::deleteCut(int whichOne)
490{
491    assert(whichOne < numberCuts_);
492    cuts_[whichOne] = NULL;
493}
494/* Deactivate node information.
495   1 - bounds
496   2 - cuts
497   4 - basis!
498*/
499void
500CbcNodeInfo::deactivate(int mode)
501{
502    active_ &= (~mode);
503}
504
Note: See TracBrowser for help on using the repository browser.