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

Last change on this file since 1852 was 1573, checked in by lou, 9 years ago

Change to EPL license notice.

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