source: trunk/Cbc/src/CbcNodeInfo.cpp

Last change on this file was 2465, checked in by unxusr, 5 months ago

script to format sources

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