source: trunk/Cbc/src/CbcCountRowCut.cpp @ 2094

Last change on this file since 2094 was 2094, checked in by forrest, 4 years ago

for memory leaks and heuristics and some experimental stuff

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 17.7 KB
Line 
1/* $Id: CbcCountRowCut.cpp 2094 2014-11-18 11:15:36Z 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#if defined(_MSC_VER)
7// Turn off compiler warning about long names
8#  pragma warning(disable:4786)
9#endif
10#include <cassert>
11
12#include "OsiRowCut.hpp"
13#include "CbcModel.hpp"
14#include "CbcCountRowCut.hpp"
15#include "CbcNode.hpp"
16//#define CHECK_CUT_COUNTS
17// Default Constructor
18CbcCountRowCut::CbcCountRowCut ()
19        :
20        OsiRowCut(),
21        owner_(NULL),
22        ownerCut_(-1),
23        numberPointingToThis_(0),
24        whichCutGenerator_(-1)
25{
26#ifdef CHECK_CUT_COUNTS
27    printf("CbcCountRowCut default constructor %x\n", this);
28#endif
29}
30
31// Copy Constructor
32CbcCountRowCut::CbcCountRowCut (const OsiRowCut & rhs)
33        : OsiRowCut(rhs),
34        owner_(NULL),
35        ownerCut_(-1),
36        numberPointingToThis_(0),
37        whichCutGenerator_(-1)
38{
39#ifdef CHECK_CUT_COUNTS
40    printf("CbcCountRowCut constructor %x from RowCut\n", this);
41#endif
42}
43// Copy Constructor
44CbcCountRowCut::CbcCountRowCut (const OsiRowCut & rhs,
45                                CbcNodeInfo * info, int whichOne,
46                                int whichGenerator,
47                                int numberPointingToThis)
48        : OsiRowCut(rhs),
49        owner_(info),
50        ownerCut_(whichOne),
51        numberPointingToThis_(numberPointingToThis),
52        whichCutGenerator_(whichGenerator)
53{
54#ifdef CHECK_CUT_COUNTS
55    printf("CbcCountRowCut constructor %x from RowCut and info %d\n",
56           this, numberPointingToThis_);
57#endif
58    //assert (!numberPointingToThis||numberPointingToThis==1000000000);
59}
60CbcCountRowCut::~CbcCountRowCut()
61{
62#ifdef CHECK_CUT_COUNTS
63    printf("CbcCountRowCut destructor %x - references %d\n", this,
64           numberPointingToThis_);
65#endif
66    // Look at owner and delete
67    if (owner_)
68        owner_->deleteCut(ownerCut_);
69    ownerCut_ = -1234567;
70}
71// Increment number of references
72void
73CbcCountRowCut::increment(int change)
74{
75    assert(ownerCut_ != -1234567);
76    numberPointingToThis_ += change;
77}
78
79// Decrement number of references and return number left
80int
81CbcCountRowCut::decrement(int change)
82{
83    assert(ownerCut_ != -1234567);
84    // See if plausible number
85    if (change < 900000000) {
86        //assert(numberPointingToThis_>=change);
87        assert(numberPointingToThis_ >= 0);
88        if (numberPointingToThis_ < change) {
89            assert(numberPointingToThis_ > 0);
90            COIN_DETAIL_PRINT(printf("negative cut count %d - %d\n", numberPointingToThis_, change));
91            change = numberPointingToThis_;
92        }
93        numberPointingToThis_ -= change;
94    }
95    return numberPointingToThis_;
96}
97
98// Set information
99void
100CbcCountRowCut::setInfo(CbcNodeInfo * info, int whichOne)
101{
102    owner_ = info;
103    ownerCut_ = whichOne;
104}
105// Returns true if can drop cut if slack basic
106bool
107CbcCountRowCut::canDropCut(const OsiSolverInterface * solver, int iRow) const
108{
109    // keep if COIN_DBL_MAX otherwise keep if slack zero
110    if (effectiveness() < 1.0e20) {
111        return true;
112    } else if (effectiveness() != COIN_DBL_MAX) {
113        if (iRow >= solver->getNumRows())
114            return true;
115        const double * rowActivity = solver->getRowActivity();
116        const double * rowLower = solver->getRowLower();
117        const double * rowUpper = solver->getRowUpper();
118        double tolerance;
119        solver->getDblParam(OsiPrimalTolerance, tolerance) ;
120        double value = rowActivity[iRow];
121        if (value < rowLower[iRow] + tolerance ||
122                value > rowUpper[iRow] - tolerance)
123            return false;
124        else
125            return true;
126    } else {
127        return false;
128    }
129}
130static double multiplier[] = {1.23456789e2,-9.87654321};
131static int hashCut (const OsiRowCut2 & x, int size) 
132{
133  int xN =x.row().getNumElements();
134  double xLb = x.lb();
135  double xUb = x.ub();
136  const int * xIndices = x.row().getIndices();
137  const double * xElements = x.row().getElements();
138  unsigned int hashValue;
139  double value=1.0;
140  if (xLb>-1.0e10)
141    value += xLb*multiplier[0];
142  if (xUb<1.0e10)
143    value += xUb*multiplier[1];
144  for( int j=0;j<xN;j++) {
145    int xColumn = xIndices[j];
146    double xValue = xElements[j];
147    int k=(j&1);
148    value += (j+1)*multiplier[k]*(xColumn+1)*xValue;
149  }
150  // should be compile time but too lazy for now
151  if (sizeof(value)>sizeof(hashValue)) {
152    assert (sizeof(value)==2*sizeof(hashValue));
153    union { double d; int i[2]; } xx;
154    xx.d = value;
155    hashValue = (xx.i[0] + xx.i[1]);
156  } else {
157    assert (sizeof(value)==sizeof(hashValue));
158    union { double d; unsigned int i[2]; } xx;
159    xx.d = value;
160    hashValue = xx.i[0];
161  }
162  return hashValue%(size);
163}
164static int hashCut2 (const OsiRowCut2 & x, int size) 
165{
166  int xN =x.row().getNumElements();
167  double xLb = x.lb();
168  double xUb = x.ub();
169  const int * xIndices = x.row().getIndices();
170  const double * xElements = x.row().getElements();
171  unsigned int hashValue;
172  double value=1.0;
173  if (xLb>-1.0e10)
174    value += xLb*multiplier[0];
175  if (xUb<1.0e10)
176    value += xUb*multiplier[1];
177  for( int j=0;j<xN;j++) {
178    int xColumn = xIndices[j];
179    double xValue = xElements[j];
180    int k=(j&1);
181    value += (j+1)*multiplier[k]*(xColumn+1)*xValue;
182  }
183  // should be compile time but too lazy for now
184  if (sizeof(value)>sizeof(hashValue)) {
185    assert (sizeof(value)==2*sizeof(hashValue));
186    union { double d; int i[2]; } xx;
187    xx.d = value;
188    hashValue = (xx.i[0] + xx.i[1]);
189  } else {
190    assert (sizeof(value)==sizeof(hashValue));
191    union { double d; unsigned int i[2]; } xx;
192    xx.d = value;
193    hashValue = xx.i[0];
194  }
195  return hashValue%(size);
196}
197static bool same (const OsiRowCut2 & x, const OsiRowCut2 & y) 
198{
199  int xN =x.row().getNumElements();
200  int yN =y.row().getNumElements();
201  bool identical=false;
202  if (xN==yN) {
203    double xLb = x.lb();
204    double xUb = x.ub();
205    double yLb = y.lb();
206    double yUb = y.ub();
207    if (fabs(xLb-yLb)<1.0e-8&&fabs(xUb-yUb)<1.0e-8) {
208      const int * xIndices = x.row().getIndices();
209      const double * xElements = x.row().getElements();
210      const int * yIndices = y.row().getIndices();
211      const double * yElements = y.row().getElements();
212      int j;
213      for( j=0;j<xN;j++) {
214        if (xIndices[j]!=yIndices[j])
215          break;
216        if (fabs(xElements[j]-yElements[j])>1.0e-12)
217          break;
218      }
219      identical =  (j==xN);
220    }
221  }
222  return identical;
223}
224static bool same2 (const OsiRowCut2 & x, const OsiRowCut2 & y) 
225{
226  int xN =x.row().getNumElements();
227  int yN =y.row().getNumElements();
228  bool identical=false;
229  if (xN==yN) {
230    double xLb = x.lb();
231    double xUb = x.ub();
232    double yLb = y.lb();
233    double yUb = y.ub();
234    if (fabs(xLb-yLb)<1.0e-8&&fabs(xUb-yUb)<1.0e-8) {
235      const int * xIndices = x.row().getIndices();
236      const double * xElements = x.row().getElements();
237      const int * yIndices = y.row().getIndices();
238      const double * yElements = y.row().getElements();
239      int j;
240      for( j=0;j<xN;j++) {
241        if (xIndices[j]!=yIndices[j])
242          break;
243        if (fabs(xElements[j]-yElements[j])>1.0e-12)
244          break;
245      }
246      identical =  (j==xN);
247    }
248  }
249  return identical;
250}
251CbcRowCuts::CbcRowCuts(int initialMaxSize, int hashMultiplier)
252{
253  numberCuts_=0;
254  size_ = initialMaxSize;
255  hashMultiplier_ = hashMultiplier;
256  int hashSize=hashMultiplier_*size_;
257  if (size_) {
258    rowCut_ = new  OsiRowCut2 * [size_];
259    hash_ = new CoinHashLink[hashSize];
260  } else {
261    rowCut_ = NULL;
262    hash_ = NULL;
263  }
264  for (int i=0;i<hashSize;i++) {
265    hash_[i].index=-1;
266    hash_[i].next=-1;
267  }
268  lastHash_=-1;
269}
270CbcRowCuts::~CbcRowCuts()
271{
272  for (int i=0;i<numberCuts_;i++)
273    delete rowCut_[i];
274  delete [] rowCut_;
275  delete [] hash_;
276}
277CbcRowCuts::CbcRowCuts(const CbcRowCuts& rhs)
278{
279  numberCuts_=rhs.numberCuts_;
280  hashMultiplier_ = rhs.hashMultiplier_;
281  size_ = rhs.size_;
282  int hashSize= size_*hashMultiplier_;
283  lastHash_=rhs.lastHash_;
284  if (size_) {
285    rowCut_ = new  OsiRowCut2 * [size_];
286    hash_ = new CoinHashLink[hashSize];
287    for (int i=0;i<hashSize;i++) {
288      hash_[i] = rhs.hash_[i];
289    }
290    for (int i=0;i<numberCuts_;i++) {
291      if (rhs.rowCut_[i])
292        rowCut_[i]=new OsiRowCut2(*rhs.rowCut_[i]);
293      else
294        rowCut_[i]=NULL;
295    }
296  } else {
297    rowCut_ = NULL;
298    hash_ = NULL;
299  }
300}
301CbcRowCuts& 
302CbcRowCuts::operator=(const CbcRowCuts& rhs)
303{
304  if (this != &rhs) {
305    for (int i=0;i<numberCuts_;i++)
306      delete rowCut_[i];
307    delete [] rowCut_;
308    delete [] hash_;
309    numberCuts_=rhs.numberCuts_;
310    hashMultiplier_ = rhs.hashMultiplier_;
311    size_ = rhs.size_;
312    lastHash_=rhs.lastHash_;
313    if (size_) {
314      rowCut_ = new  OsiRowCut2 * [size_];
315      int hashSize= size_*hashMultiplier_;
316      hash_ = new CoinHashLink[hashSize];
317      for (int i=0;i<hashSize;i++) {
318        hash_[i] = rhs.hash_[i];
319      }
320      for (int i=0;i<numberCuts_;i++) {
321        if (rhs.rowCut_[i])
322          rowCut_[i]=new OsiRowCut2(*rhs.rowCut_[i]);
323        else
324          rowCut_[i]=NULL;
325      }
326    } else {
327      rowCut_ = NULL;
328      hash_ = NULL;
329    }
330  }
331  return *this;
332}
333void 
334CbcRowCuts::eraseRowCut(int sequence)
335{
336  // find
337  assert (sequence>=0&&sequence<numberCuts_);
338  OsiRowCut2 * cut = rowCut_[sequence];
339  int hashSize= size_*hashMultiplier_;
340  int ipos = hashCut(*cut,hashSize);
341  int found = -1;
342  while ( true ) {
343    int j1 = hash_[ipos].index;
344    if ( j1 >= 0 ) {
345      if (j1!=sequence) {
346        int k = hash_[ipos].next;
347        if ( k != -1 )
348          ipos = k;
349        else
350          break;
351      } else {
352        found = j1;
353        break;
354      }
355    } else {
356      break;
357    }
358  }
359  assert (found>=0);
360  assert (hash_[ipos].index==sequence);
361  // shuffle up
362  while (hash_[ipos].next>=0) {
363    int k = hash_[ipos].next;
364    hash_[ipos]=hash_[k];
365    ipos=k;
366  }
367  hash_[ipos].index=-1;
368  // move last to found
369  numberCuts_--;
370  assert (found==numberCuts_); // debug when fails
371  if (numberCuts_&&found<numberCuts_) {
372    ipos = hashCut(*rowCut_[numberCuts_],hashSize);
373    while ( true ) {
374      int j1 = hash_[ipos].index;
375      if (j1!=numberCuts_) {
376        int k = hash_[ipos].next;
377        ipos = k;
378        assert (ipos>=0);
379      } else {
380        // change
381        hash_[ipos].index=found;
382        rowCut_[found]=rowCut_[numberCuts_];
383        rowCut_[numberCuts_]=NULL;
384        break;
385      }
386    }
387  }
388  delete cut;
389  rowCut_[numberCuts_]=NULL;
390  //assert (!rowCut_[numberCuts_-1]);
391}
392// Truncate
393void 
394CbcRowCuts::truncate(int numberAfter)
395{
396  if (numberAfter<0||numberAfter>=numberCuts_)
397    return;
398  for (int i=numberAfter;i<numberCuts_;i++) {
399    delete rowCut_[i];
400    rowCut_[i]=NULL;
401  }
402  numberCuts_=numberAfter;
403  int hashSize= size_*hashMultiplier_;
404  for (int i=0;i<hashSize;i++) {
405    hash_[i].index=-1;
406    hash_[i].next=-1;
407  }
408  OsiRowCut2 ** temp = new  OsiRowCut2 * [size_];
409  lastHash_=-1;
410  for (int i=0;i<numberCuts_;i++) {
411    temp[i]=rowCut_[i];
412    int ipos = hashCut(*temp[i],hashSize);
413    int found = -1;
414    int jpos=ipos;
415    while ( true ) {
416      int j1 = hash_[ipos].index;
417      if ( j1 >= 0 ) {
418        if ( !same(*temp[i],*temp[j1]) ) {
419          int k = hash_[ipos].next;
420          if ( k != -1 )
421            ipos = k;
422          else
423            break;
424        } else {
425          found = j1;
426          break;
427        }
428      } else {
429        break;
430      }
431    }
432    if (found<0) {
433      assert (hash_[ipos].next==-1);
434      if (ipos==jpos) {
435        // first
436        hash_[ipos].index=i;
437      } else {
438        // find next space
439        while ( true ) {
440          ++lastHash_;
441          assert (lastHash_<hashSize);
442          if ( hash_[lastHash_].index == -1 ) 
443            break;
444        }
445        hash_[ipos].next = lastHash_;
446        hash_[lastHash_].index = i;
447      }
448    }
449  }
450  delete [] rowCut_;
451  rowCut_ = temp;
452}
453// Return 0 if added, 1 if not, -1 if not added because of space
454int 
455CbcRowCuts::addCutIfNotDuplicate(const OsiRowCut & cut,int whichType)
456{
457  int hashSize= size_*hashMultiplier_;
458  bool globallyValid=cut.globallyValid();
459  if (numberCuts_==size_) {
460    size_ = 2*size_+100;
461    hashSize=hashMultiplier_*size_;
462    OsiRowCut2 ** temp = new  OsiRowCut2 * [size_];
463    delete [] hash_;
464    hash_ = new CoinHashLink[hashSize];
465    for (int i=0;i<hashSize;i++) {
466      hash_[i].index=-1;
467      hash_[i].next=-1;
468    }
469    lastHash_=-1;
470    for (int i=0;i<numberCuts_;i++) {
471      temp[i]=rowCut_[i];
472      int ipos = hashCut(*temp[i],hashSize);
473      int found = -1;
474      int jpos=ipos;
475      while ( true ) {
476        int j1 = hash_[ipos].index;
477       
478        if ( j1 >= 0 ) {
479          if ( !same(*temp[i],*temp[j1]) ) {
480            int k = hash_[ipos].next;
481            if ( k != -1 )
482              ipos = k;
483            else
484              break;
485          } else {
486            found = j1;
487            break;
488          }
489        } else {
490          break;
491        }
492      }
493      if (found<0) {
494        assert (hash_[ipos].next==-1);
495        if (ipos==jpos) {
496          // first
497          hash_[ipos].index=i;
498        } else {
499          // find next space
500          while ( true ) {
501            ++lastHash_;
502            assert (lastHash_<hashSize);
503            if ( hash_[lastHash_].index == -1 ) 
504              break;
505          }
506          hash_[ipos].next = lastHash_;
507          hash_[lastHash_].index = i;
508        }
509      }
510    }
511    delete [] rowCut_;
512    rowCut_ = temp;
513  }
514  if (numberCuts_<size_) {
515    double newLb = cut.lb();
516    double newUb = cut.ub();
517    CoinPackedVector vector = cut.row();
518    int numberElements =vector.getNumElements();
519    int * newIndices = vector.getIndices();
520    double * newElements = vector.getElements();
521    CoinSort_2(newIndices,newIndices+numberElements,newElements);
522    int i;
523    bool bad=false;
524    for (i=0;i<numberElements;i++) {
525      double value = fabs(newElements[i]);
526      if (value<1.0e-12||value>1.0e12) 
527        bad=true;
528    }
529    if (bad)
530      return 1;
531    OsiRowCut2 newCut(whichType);
532    newCut.setLb(newLb);
533    newCut.setUb(newUb);
534    newCut.setRow(vector);
535    int ipos = hashCut(newCut,hashSize);
536    int found = -1;
537    int jpos=ipos;
538    while ( true ) {
539      int j1 = hash_[ipos].index;
540     
541      if ( j1 >= 0 ) {
542        if ( !same(newCut,*rowCut_[j1]) ) {
543          int k = hash_[ipos].next;
544          if ( k != -1 )
545            ipos = k;
546          else
547            break;
548        } else {
549          found = j1;
550          break;
551        }
552      } else {
553        break;
554      }
555    }
556    if (found<0) {
557      assert (hash_[ipos].next==-1);
558      if (ipos==jpos) {
559        // first
560        hash_[ipos].index=numberCuts_;
561      } else {
562        // find next space
563        while ( true ) {
564          ++lastHash_;
565          assert (lastHash_<hashSize);
566          if ( hash_[lastHash_].index == -1 ) 
567            break;
568        }
569        hash_[ipos].next = lastHash_;
570        hash_[lastHash_].index = numberCuts_;
571      }
572      OsiRowCut2 * newCutPtr = new OsiRowCut2(whichType);
573      newCutPtr->setLb(newLb);
574      newCutPtr->setUb(newUb);
575      newCutPtr->setRow(vector);
576      newCutPtr->setGloballyValid(globallyValid);
577      rowCut_[numberCuts_++]=newCutPtr;
578      //printf("addedGlobalCut of size %d to %x - cuts size %d\n",
579      //     cut.row().getNumElements(),this,numberCuts_);
580      return 0;
581    } else {
582      return 1;
583    }
584  } else {
585    return -1;
586  }
587}
588// Return 0 if added, 1 if not, -1 if not added because of space
589int 
590CbcRowCuts::addCutIfNotDuplicateWhenGreedy(const OsiRowCut & cut,int whichType)
591{
592  int hashSize= size_*hashMultiplier_;
593  if (numberCuts_==size_) {
594    size_ = 2*size_+100;
595    hashSize=hashMultiplier_*size_;
596    OsiRowCut2 ** temp = new  OsiRowCut2 * [size_];
597    delete [] hash_;
598    hash_ = new CoinHashLink[hashSize];
599    for (int i=0;i<hashSize;i++) {
600      hash_[i].index=-1;
601      hash_[i].next=-1;
602    }
603    lastHash_=-1;
604    for (int i=0;i<numberCuts_;i++) {
605      temp[i]=rowCut_[i];
606      int ipos = hashCut2(*temp[i],hashSize);
607      int found = -1;
608      int jpos=ipos;
609      while ( true ) {
610        int j1 = hash_[ipos].index;
611       
612        if ( j1 >= 0 ) {
613          if ( !same2(*temp[i],*temp[j1]) ) {
614            int k = hash_[ipos].next;
615            if ( k != -1 )
616              ipos = k;
617            else
618              break;
619          } else {
620            found = j1;
621            break;
622          }
623        } else {
624          break;
625        }
626      }
627      if (found<0) {
628        assert (hash_[ipos].next==-1);
629        if (ipos==jpos) {
630          // first
631          hash_[ipos].index=i;
632        } else {
633          // find next space
634          while ( true ) {
635            ++lastHash_;
636            assert (lastHash_<hashSize);
637            if ( hash_[lastHash_].index == -1 ) 
638              break;
639          }
640          hash_[ipos].next = lastHash_;
641          hash_[lastHash_].index = i;
642        }
643      }
644    }
645    delete [] rowCut_;
646    rowCut_ = temp;
647  }
648  if (numberCuts_<size_) {
649    double newLb = cut.lb();
650    double newUb = cut.ub();
651    CoinPackedVector vector = cut.row();
652    int numberElements =vector.getNumElements();
653    int * newIndices = vector.getIndices();
654    double * newElements = vector.getElements();
655    CoinSort_2(newIndices,newIndices+numberElements,newElements);
656    int i;
657    bool bad=false;
658    for (i=0;i<numberElements;i++) {
659      double value = fabs(newElements[i]);
660      if (value<1.0e-12||value>1.0e12) 
661        bad=true;
662    }
663    if (bad)
664      return 1;
665    OsiRowCut2 newCut(whichType);
666    newCut.setLb(newLb);
667    newCut.setUb(newUb);
668    newCut.setRow(vector);
669    int ipos = hashCut2(newCut,hashSize);
670    int found = -1;
671    int jpos=ipos;
672    while ( true ) {
673      int j1 = hash_[ipos].index;
674     
675      if ( j1 >= 0 ) {
676        if ( !same2(newCut,*rowCut_[j1]) ) {
677          int k = hash_[ipos].next;
678          if ( k != -1 )
679            ipos = k;
680          else
681            break;
682        } else {
683          found = j1;
684          break;
685        }
686      } else {
687        break;
688      }
689    }
690    if (found<0) {
691      assert (hash_[ipos].next==-1);
692      if (ipos==jpos) {
693        // first
694        hash_[ipos].index=numberCuts_;
695      } else {
696        // find next space
697        while ( true ) {
698          ++lastHash_;
699          assert (lastHash_<hashSize);
700          if ( hash_[lastHash_].index == -1 ) 
701            break;
702        }
703        hash_[ipos].next = lastHash_;
704        hash_[lastHash_].index = numberCuts_;
705      }
706      OsiRowCut2 * newCutPtr = new OsiRowCut2(whichType);
707      newCutPtr->setLb(newLb);
708      newCutPtr->setUb(newUb);
709      newCutPtr->setRow(vector);
710      rowCut_[numberCuts_++]=newCutPtr;
711      printf("addedGreedyGlobalCut of size %d to %x - cuts size %d\n",
712             cut.row().getNumElements(),this,numberCuts_);
713      return 0;
714    } else {
715      return 1;
716    }
717  } else {
718    return -1;
719  }
720}
721// Add in cuts as normal cuts and delete
722void 
723CbcRowCuts::addCuts(OsiCuts & cs)
724{
725  for (int i=0;i<numberCuts_;i++) {
726    cs.insert(*rowCut_[i]);
727    delete rowCut_[i] ;
728    rowCut_[i] = NULL ;
729  }
730  numberCuts_=0;
731}
Note: See TracBrowser for help on using the repository browser.