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

Last change on this file since 2342 was 2342, checked in by forrest, 19 months ago

to unsigned

  • 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 2342 2017-08-09 09:28:53Z 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  union { double d; unsigned int i[2]; } xx;
152  if (sizeof(value)>sizeof(hashValue)) {
153    assert (sizeof(value)==2*sizeof(hashValue));
154    xx.d = value;
155    hashValue = (xx.i[0] + xx.i[1]);
156  } else {
157    assert (sizeof(value)==sizeof(hashValue));
158    xx.d = value;
159    hashValue = xx.i[0];
160  }
161  return hashValue%(size);
162}
163static int hashCut2 (const OsiRowCut2 & x, int size) 
164{
165  int xN =x.row().getNumElements();
166  double xLb = x.lb();
167  double xUb = x.ub();
168  const int * xIndices = x.row().getIndices();
169  const double * xElements = x.row().getElements();
170  unsigned int hashValue;
171  double value=1.0;
172  if (xLb>-1.0e10)
173    value += xLb*multiplier[0];
174  if (xUb<1.0e10)
175    value += xUb*multiplier[1];
176  for( int j=0;j<xN;j++) {
177    int xColumn = xIndices[j];
178    double xValue = xElements[j];
179    int k=(j&1);
180    value += (j+1)*multiplier[k]*(xColumn+1)*xValue;
181  }
182  // should be compile time but too lazy for now
183  if (sizeof(value)>sizeof(hashValue)) {
184    assert (sizeof(value)==2*sizeof(hashValue));
185    union { double d; unsigned int i[2]; } xx;
186    xx.d = value;
187    hashValue = (xx.i[0] + xx.i[1]);
188  } else {
189    assert (sizeof(value)==sizeof(hashValue));
190    union { double d; unsigned int i[2]; } xx;
191    xx.d = value;
192    hashValue = xx.i[0];
193  }
194  return hashValue%(size);
195}
196static bool same (const OsiRowCut2 & x, const OsiRowCut2 & y) 
197{
198  int xN =x.row().getNumElements();
199  int yN =y.row().getNumElements();
200  bool identical=false;
201  if (xN==yN) {
202    double xLb = x.lb();
203    double xUb = x.ub();
204    double yLb = y.lb();
205    double yUb = y.ub();
206    if (fabs(xLb-yLb)<1.0e-8&&fabs(xUb-yUb)<1.0e-8) {
207      const int * xIndices = x.row().getIndices();
208      const double * xElements = x.row().getElements();
209      const int * yIndices = y.row().getIndices();
210      const double * yElements = y.row().getElements();
211      int j;
212      for( j=0;j<xN;j++) {
213        if (xIndices[j]!=yIndices[j])
214          break;
215        if (fabs(xElements[j]-yElements[j])>1.0e-12)
216          break;
217      }
218      identical =  (j==xN);
219    }
220  }
221  return identical;
222}
223static bool same2 (const OsiRowCut2 & x, const OsiRowCut2 & y) 
224{
225  int xN =x.row().getNumElements();
226  int yN =y.row().getNumElements();
227  bool identical=false;
228  if (xN==yN) {
229    double xLb = x.lb();
230    double xUb = x.ub();
231    double yLb = y.lb();
232    double yUb = y.ub();
233    if (fabs(xLb-yLb)<1.0e-8&&fabs(xUb-yUb)<1.0e-8) {
234      const int * xIndices = x.row().getIndices();
235      const double * xElements = x.row().getElements();
236      const int * yIndices = y.row().getIndices();
237      const double * yElements = y.row().getElements();
238      int j;
239      for( j=0;j<xN;j++) {
240        if (xIndices[j]!=yIndices[j])
241          break;
242        if (fabs(xElements[j]-yElements[j])>1.0e-12)
243          break;
244      }
245      identical =  (j==xN);
246    }
247  }
248  return identical;
249}
250CbcRowCuts::CbcRowCuts(int initialMaxSize, int hashMultiplier)
251{
252  numberCuts_=0;
253  size_ = initialMaxSize;
254  hashMultiplier_ = hashMultiplier;
255  int hashSize=hashMultiplier_*size_;
256  if (size_) {
257    rowCut_ = new  OsiRowCut2 * [size_];
258    hash_ = new CoinHashLink[hashSize];
259  } else {
260    rowCut_ = NULL;
261    hash_ = NULL;
262  }
263  for (int i=0;i<hashSize;i++) {
264    hash_[i].index=-1;
265    hash_[i].next=-1;
266  }
267  lastHash_=-1;
268}
269CbcRowCuts::~CbcRowCuts()
270{
271  for (int i=0;i<numberCuts_;i++)
272    delete rowCut_[i];
273  delete [] rowCut_;
274  delete [] hash_;
275}
276CbcRowCuts::CbcRowCuts(const CbcRowCuts& rhs)
277{
278  numberCuts_=rhs.numberCuts_;
279  hashMultiplier_ = rhs.hashMultiplier_;
280  size_ = rhs.size_;
281  int hashSize= size_*hashMultiplier_;
282  lastHash_=rhs.lastHash_;
283  if (size_) {
284    rowCut_ = new  OsiRowCut2 * [size_];
285    hash_ = new CoinHashLink[hashSize];
286    for (int i=0;i<hashSize;i++) {
287      hash_[i] = rhs.hash_[i];
288    }
289    for (int i=0;i<numberCuts_;i++) {
290      if (rhs.rowCut_[i])
291        rowCut_[i]=new OsiRowCut2(*rhs.rowCut_[i]);
292      else
293        rowCut_[i]=NULL;
294    }
295  } else {
296    rowCut_ = NULL;
297    hash_ = NULL;
298  }
299}
300CbcRowCuts& 
301CbcRowCuts::operator=(const CbcRowCuts& rhs)
302{
303  if (this != &rhs) {
304    for (int i=0;i<numberCuts_;i++)
305      delete rowCut_[i];
306    delete [] rowCut_;
307    delete [] hash_;
308    numberCuts_=rhs.numberCuts_;
309    hashMultiplier_ = rhs.hashMultiplier_;
310    size_ = rhs.size_;
311    lastHash_=rhs.lastHash_;
312    if (size_) {
313      rowCut_ = new  OsiRowCut2 * [size_];
314      int hashSize= size_*hashMultiplier_;
315      hash_ = new CoinHashLink[hashSize];
316      for (int i=0;i<hashSize;i++) {
317        hash_[i] = rhs.hash_[i];
318      }
319      for (int i=0;i<numberCuts_;i++) {
320        if (rhs.rowCut_[i])
321          rowCut_[i]=new OsiRowCut2(*rhs.rowCut_[i]);
322        else
323          rowCut_[i]=NULL;
324      }
325    } else {
326      rowCut_ = NULL;
327      hash_ = NULL;
328    }
329  }
330  return *this;
331}
332void 
333CbcRowCuts::eraseRowCut(int sequence)
334{
335  // find
336  assert (sequence>=0&&sequence<numberCuts_);
337  OsiRowCut2 * cut = rowCut_[sequence];
338  int hashSize= size_*hashMultiplier_;
339  int ipos = hashCut(*cut,hashSize);
340  int found = -1;
341  while ( true ) {
342    int j1 = hash_[ipos].index;
343    if ( j1 >= 0 ) {
344      if (j1!=sequence) {
345        int k = hash_[ipos].next;
346        if ( k != -1 )
347          ipos = k;
348        else
349          break;
350      } else {
351        found = j1;
352        break;
353      }
354    } else {
355      break;
356    }
357  }
358  assert (found>=0);
359  assert (hash_[ipos].index==sequence);
360  // shuffle up
361  while (hash_[ipos].next>=0) {
362    int k = hash_[ipos].next;
363    hash_[ipos]=hash_[k];
364    ipos=k;
365  }
366  hash_[ipos].index=-1;
367  // move last to found
368  numberCuts_--;
369  assert (found==numberCuts_); // debug when fails
370  if (numberCuts_&&found<numberCuts_) {
371    ipos = hashCut(*rowCut_[numberCuts_],hashSize);
372    while ( true ) {
373      int j1 = hash_[ipos].index;
374      if (j1!=numberCuts_) {
375        int k = hash_[ipos].next;
376        ipos = k;
377        assert (ipos>=0);
378      } else {
379        // change
380        hash_[ipos].index=found;
381        rowCut_[found]=rowCut_[numberCuts_];
382        rowCut_[numberCuts_]=NULL;
383        break;
384      }
385    }
386  }
387  delete cut;
388  rowCut_[numberCuts_]=NULL;
389  //assert (!rowCut_[numberCuts_-1]);
390}
391// Truncate
392void 
393CbcRowCuts::truncate(int numberAfter)
394{
395  if (numberAfter<0||numberAfter>=numberCuts_)
396    return;
397  for (int i=numberAfter;i<numberCuts_;i++) {
398    delete rowCut_[i];
399    rowCut_[i]=NULL;
400  }
401  numberCuts_=numberAfter;
402  int hashSize= size_*hashMultiplier_;
403  for (int i=0;i<hashSize;i++) {
404    hash_[i].index=-1;
405    hash_[i].next=-1;
406  }
407  OsiRowCut2 ** temp = new  OsiRowCut2 * [size_];
408  lastHash_=-1;
409  for (int i=0;i<numberCuts_;i++) {
410    temp[i]=rowCut_[i];
411    int ipos = hashCut(*temp[i],hashSize);
412    int found = -1;
413    int jpos=ipos;
414    while ( true ) {
415      int j1 = hash_[ipos].index;
416      if ( j1 >= 0 ) {
417        if ( !same(*temp[i],*temp[j1]) ) {
418          int k = hash_[ipos].next;
419          if ( k != -1 )
420            ipos = k;
421          else
422            break;
423        } else {
424          found = j1;
425          break;
426        }
427      } else {
428        break;
429      }
430    }
431    if (found<0) {
432      assert (hash_[ipos].next==-1);
433      if (ipos==jpos) {
434        // first
435        hash_[ipos].index=i;
436      } else {
437        // find next space
438        while ( true ) {
439          ++lastHash_;
440          assert (lastHash_<hashSize);
441          if ( hash_[lastHash_].index == -1 ) 
442            break;
443        }
444        hash_[ipos].next = lastHash_;
445        hash_[lastHash_].index = i;
446      }
447    }
448  }
449  delete [] rowCut_;
450  rowCut_ = temp;
451}
452// Return 0 if added, 1 if not, -1 if not added because of space
453int 
454CbcRowCuts::addCutIfNotDuplicate(const OsiRowCut & cut,int whichType)
455{
456  int hashSize= size_*hashMultiplier_;
457  bool globallyValid=cut.globallyValid();
458  if (numberCuts_==size_) {
459    size_ = 2*size_+100;
460    hashSize=hashMultiplier_*size_;
461    OsiRowCut2 ** temp = new  OsiRowCut2 * [size_];
462    delete [] hash_;
463    hash_ = new CoinHashLink[hashSize];
464    for (int i=0;i<hashSize;i++) {
465      hash_[i].index=-1;
466      hash_[i].next=-1;
467    }
468    lastHash_=-1;
469    for (int i=0;i<numberCuts_;i++) {
470      temp[i]=rowCut_[i];
471      int ipos = hashCut(*temp[i],hashSize);
472      int found = -1;
473      int jpos=ipos;
474      while ( true ) {
475        int j1 = hash_[ipos].index;
476       
477        if ( j1 >= 0 ) {
478          if ( !same(*temp[i],*temp[j1]) ) {
479            int k = hash_[ipos].next;
480            if ( k != -1 )
481              ipos = k;
482            else
483              break;
484          } else {
485            found = j1;
486            break;
487          }
488        } else {
489          break;
490        }
491      }
492      if (found<0) {
493        assert (hash_[ipos].next==-1);
494        if (ipos==jpos) {
495          // first
496          hash_[ipos].index=i;
497        } else {
498          // find next space
499          while ( true ) {
500            ++lastHash_;
501            assert (lastHash_<hashSize);
502            if ( hash_[lastHash_].index == -1 ) 
503              break;
504          }
505          hash_[ipos].next = lastHash_;
506          hash_[lastHash_].index = i;
507        }
508      }
509    }
510    delete [] rowCut_;
511    rowCut_ = temp;
512  }
513  if (numberCuts_<size_) {
514    double newLb = cut.lb();
515    double newUb = cut.ub();
516    CoinPackedVector vector = cut.row();
517    int numberElements =vector.getNumElements();
518    int * newIndices = vector.getIndices();
519    double * newElements = vector.getElements();
520    CoinSort_2(newIndices,newIndices+numberElements,newElements);
521    int i;
522    bool bad=false;
523    for (i=0;i<numberElements;i++) {
524      double value = fabs(newElements[i]);
525      if (value<1.0e-12||value>1.0e12) 
526        bad=true;
527    }
528    if (bad)
529      return 1;
530    OsiRowCut2 newCut(whichType);
531    newCut.setLb(newLb);
532    newCut.setUb(newUb);
533    newCut.setRow(vector);
534    int ipos = hashCut(newCut,hashSize);
535    int found = -1;
536    int jpos=ipos;
537    while ( true ) {
538      int j1 = hash_[ipos].index;
539     
540      if ( j1 >= 0 ) {
541        if ( !same(newCut,*rowCut_[j1]) ) {
542          int k = hash_[ipos].next;
543          if ( k != -1 )
544            ipos = k;
545          else
546            break;
547        } else {
548          found = j1;
549          break;
550        }
551      } else {
552        break;
553      }
554    }
555    if (found<0) {
556      assert (hash_[ipos].next==-1);
557      if (ipos==jpos) {
558        // first
559        hash_[ipos].index=numberCuts_;
560      } else {
561        // find next space
562        while ( true ) {
563          ++lastHash_;
564          assert (lastHash_<hashSize);
565          if ( hash_[lastHash_].index == -1 ) 
566            break;
567        }
568        hash_[ipos].next = lastHash_;
569        hash_[lastHash_].index = numberCuts_;
570      }
571      OsiRowCut2 * newCutPtr = new OsiRowCut2(whichType);
572      newCutPtr->setLb(newLb);
573      newCutPtr->setUb(newUb);
574      newCutPtr->setRow(vector);
575      newCutPtr->setGloballyValid(globallyValid);
576      rowCut_[numberCuts_++]=newCutPtr;
577      //printf("addedGlobalCut of size %d to %x - cuts size %d\n",
578      //     cut.row().getNumElements(),this,numberCuts_);
579      return 0;
580    } else {
581      return 1;
582    }
583  } else {
584    return -1;
585  }
586}
587// Return 0 if added, 1 if not, -1 if not added because of space
588int 
589CbcRowCuts::addCutIfNotDuplicateWhenGreedy(const OsiRowCut & cut,int whichType)
590{
591  int hashSize= size_*hashMultiplier_;
592  if (numberCuts_==size_) {
593    size_ = 2*size_+100;
594    hashSize=hashMultiplier_*size_;
595    OsiRowCut2 ** temp = new  OsiRowCut2 * [size_];
596    delete [] hash_;
597    hash_ = new CoinHashLink[hashSize];
598    for (int i=0;i<hashSize;i++) {
599      hash_[i].index=-1;
600      hash_[i].next=-1;
601    }
602    lastHash_=-1;
603    for (int i=0;i<numberCuts_;i++) {
604      temp[i]=rowCut_[i];
605      int ipos = hashCut2(*temp[i],hashSize);
606      int found = -1;
607      int jpos=ipos;
608      while ( true ) {
609        int j1 = hash_[ipos].index;
610       
611        if ( j1 >= 0 ) {
612          if ( !same2(*temp[i],*temp[j1]) ) {
613            int k = hash_[ipos].next;
614            if ( k != -1 )
615              ipos = k;
616            else
617              break;
618          } else {
619            found = j1;
620            break;
621          }
622        } else {
623          break;
624        }
625      }
626      if (found<0) {
627        assert (hash_[ipos].next==-1);
628        if (ipos==jpos) {
629          // first
630          hash_[ipos].index=i;
631        } else {
632          // find next space
633          while ( true ) {
634            ++lastHash_;
635            assert (lastHash_<hashSize);
636            if ( hash_[lastHash_].index == -1 ) 
637              break;
638          }
639          hash_[ipos].next = lastHash_;
640          hash_[lastHash_].index = i;
641        }
642      }
643    }
644    delete [] rowCut_;
645    rowCut_ = temp;
646  }
647  if (numberCuts_<size_) {
648    double newLb = cut.lb();
649    double newUb = cut.ub();
650    CoinPackedVector vector = cut.row();
651    int numberElements =vector.getNumElements();
652    int * newIndices = vector.getIndices();
653    double * newElements = vector.getElements();
654    CoinSort_2(newIndices,newIndices+numberElements,newElements);
655    int i;
656    bool bad=false;
657    for (i=0;i<numberElements;i++) {
658      double value = fabs(newElements[i]);
659      if (value<1.0e-12||value>1.0e12) 
660        bad=true;
661    }
662    if (bad)
663      return 1;
664    OsiRowCut2 newCut(whichType);
665    newCut.setLb(newLb);
666    newCut.setUb(newUb);
667    newCut.setRow(vector);
668    int ipos = hashCut2(newCut,hashSize);
669    int found = -1;
670    int jpos=ipos;
671    while ( true ) {
672      int j1 = hash_[ipos].index;
673     
674      if ( j1 >= 0 ) {
675        if ( !same2(newCut,*rowCut_[j1]) ) {
676          int k = hash_[ipos].next;
677          if ( k != -1 )
678            ipos = k;
679          else
680            break;
681        } else {
682          found = j1;
683          break;
684        }
685      } else {
686        break;
687      }
688    }
689    if (found<0) {
690      assert (hash_[ipos].next==-1);
691      if (ipos==jpos) {
692        // first
693        hash_[ipos].index=numberCuts_;
694      } else {
695        // find next space
696        while ( true ) {
697          ++lastHash_;
698          assert (lastHash_<hashSize);
699          if ( hash_[lastHash_].index == -1 ) 
700            break;
701        }
702        hash_[ipos].next = lastHash_;
703        hash_[lastHash_].index = numberCuts_;
704      }
705      OsiRowCut2 * newCutPtr = new OsiRowCut2(whichType);
706      newCutPtr->setLb(newLb);
707      newCutPtr->setUb(newUb);
708      newCutPtr->setRow(vector);
709      rowCut_[numberCuts_++]=newCutPtr;
710      //printf("addedGreedyGlobalCut of size %d to %p - cuts size %d\n",
711      //     cut.row().getNumElements(),this,numberCuts_);
712      return 0;
713    } else {
714      return 1;
715    }
716  } else {
717    return -1;
718  }
719}
720// Add in cuts as normal cuts and delete
721void 
722CbcRowCuts::addCuts(OsiCuts & cs)
723{
724  for (int i=0;i<numberCuts_;i++) {
725    cs.insert(*rowCut_[i]);
726    delete rowCut_[i] ;
727    rowCut_[i] = NULL ;
728  }
729  numberCuts_=0;
730}
Note: See TracBrowser for help on using the repository browser.