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

Last change on this file since 1877 was 1877, checked in by forrest, 7 years ago

fix bug in parallel
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 16.0 KB
Line 
1/* $Id: CbcCountRowCut.cpp 1877 2013-03-22 14:24:12Z 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  delete cut;
368  // move last to found
369  numberCuts_--;
370  if (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      } else {
378        // change
379        hash_[ipos].index=found;
380        rowCut_[found]=rowCut_[numberCuts_];
381        rowCut_[numberCuts_]=NULL;
382        break;
383      }
384    }
385  }
386  assert (!rowCut_[numberCuts_]);
387}
388// Return 0 if added, 1 if not, -1 if not added because of space
389int 
390CbcRowCuts::addCutIfNotDuplicate(const OsiRowCut & cut,int whichType)
391{
392  int hashSize= size_*hashMultiplier_;
393  if (numberCuts_==size_) {
394    size_ = 2*size_+100;
395    hashSize=hashMultiplier_*size_;
396    OsiRowCut2 ** temp = new  OsiRowCut2 * [size_];
397    delete [] hash_;
398    hash_ = new CoinHashLink[hashSize];
399    for (int i=0;i<hashSize;i++) {
400      hash_[i].index=-1;
401      hash_[i].next=-1;
402    }
403    for (int i=0;i<numberCuts_;i++) {
404      temp[i]=rowCut_[i];
405      int ipos = hashCut(*temp[i],hashSize);
406      int found = -1;
407      int jpos=ipos;
408      while ( true ) {
409        int j1 = hash_[ipos].index;
410       
411        if ( j1 >= 0 ) {
412          if ( !same(*temp[i],*temp[j1]) ) {
413            int k = hash_[ipos].next;
414            if ( k != -1 )
415              ipos = k;
416            else
417              break;
418          } else {
419            found = j1;
420            break;
421          }
422        } else {
423          break;
424        }
425      }
426      if (found<0) {
427        assert (hash_[ipos].next==-1);
428        if (ipos==jpos) {
429          // first
430          hash_[ipos].index=i;
431        } else {
432          // find next space
433          while ( true ) {
434            ++lastHash_;
435            assert (lastHash_<hashSize);
436            if ( hash_[lastHash_].index == -1 ) 
437              break;
438          }
439          hash_[ipos].next = lastHash_;
440          hash_[lastHash_].index = i;
441        }
442      }
443    }
444    delete [] rowCut_;
445    rowCut_ = temp;
446  }
447  if (numberCuts_<size_) {
448    double newLb = cut.lb();
449    double newUb = cut.ub();
450    CoinPackedVector vector = cut.row();
451    int numberElements =vector.getNumElements();
452    int * newIndices = vector.getIndices();
453    double * newElements = vector.getElements();
454    CoinSort_2(newIndices,newIndices+numberElements,newElements);
455    int i;
456    bool bad=false;
457    for (i=0;i<numberElements;i++) {
458      double value = fabs(newElements[i]);
459      if (value<1.0e-12||value>1.0e12) 
460        bad=true;
461    }
462    if (bad)
463      return 1;
464    OsiRowCut2 newCut(whichType);
465    newCut.setLb(newLb);
466    newCut.setUb(newUb);
467    newCut.setRow(vector);
468    int ipos = hashCut(newCut,hashSize);
469    int found = -1;
470    int jpos=ipos;
471    while ( true ) {
472      int j1 = hash_[ipos].index;
473     
474      if ( j1 >= 0 ) {
475        if ( !same(newCut,*rowCut_[j1]) ) {
476          int k = hash_[ipos].next;
477          if ( k != -1 )
478            ipos = k;
479          else
480            break;
481        } else {
482          found = j1;
483          break;
484        }
485      } else {
486        break;
487      }
488    }
489    if (found<0) {
490      assert (hash_[ipos].next==-1);
491      if (ipos==jpos) {
492        // first
493        hash_[ipos].index=numberCuts_;
494      } else {
495        // find next space
496        while ( true ) {
497          ++lastHash_;
498          assert (lastHash_<hashSize);
499          if ( hash_[lastHash_].index == -1 ) 
500            break;
501        }
502        hash_[ipos].next = lastHash_;
503        hash_[lastHash_].index = numberCuts_;
504      }
505      OsiRowCut2 * newCutPtr = new OsiRowCut2(whichType);
506      newCutPtr->setLb(newLb);
507      newCutPtr->setUb(newUb);
508      newCutPtr->setRow(vector);
509      rowCut_[numberCuts_++]=newCutPtr;
510      return 0;
511    } else {
512      return 1;
513    }
514  } else {
515    return -1;
516  }
517}
518// Return 0 if added, 1 if not, -1 if not added because of space
519int 
520CbcRowCuts::addCutIfNotDuplicateWhenGreedy(const OsiRowCut & cut,int whichType)
521{
522  int hashSize= size_*hashMultiplier_;
523  if (numberCuts_==size_) {
524    size_ = 2*size_+100;
525    hashSize=hashMultiplier_*size_;
526    OsiRowCut2 ** temp = new  OsiRowCut2 * [size_];
527    delete [] hash_;
528    hash_ = new CoinHashLink[hashSize];
529    for (int i=0;i<hashSize;i++) {
530      hash_[i].index=-1;
531      hash_[i].next=-1;
532    }
533    for (int i=0;i<numberCuts_;i++) {
534      temp[i]=rowCut_[i];
535      int ipos = hashCut2(*temp[i],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 ( !same2(*temp[i],*temp[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=i;
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 = i;
571        }
572      }
573    }
574    delete [] rowCut_;
575    rowCut_ = temp;
576  }
577  if (numberCuts_<size_) {
578    double newLb = cut.lb();
579    double newUb = cut.ub();
580    CoinPackedVector vector = cut.row();
581    int numberElements =vector.getNumElements();
582    int * newIndices = vector.getIndices();
583    double * newElements = vector.getElements();
584    CoinSort_2(newIndices,newIndices+numberElements,newElements);
585    int i;
586    bool bad=false;
587    for (i=0;i<numberElements;i++) {
588      double value = fabs(newElements[i]);
589      if (value<1.0e-12||value>1.0e12) 
590        bad=true;
591    }
592    if (bad)
593      return 1;
594    OsiRowCut2 newCut(whichType);
595    newCut.setLb(newLb);
596    newCut.setUb(newUb);
597    newCut.setRow(vector);
598    int ipos = hashCut2(newCut,hashSize);
599    int found = -1;
600    int jpos=ipos;
601    while ( true ) {
602      int j1 = hash_[ipos].index;
603     
604      if ( j1 >= 0 ) {
605        if ( !same2(newCut,*rowCut_[j1]) ) {
606          int k = hash_[ipos].next;
607          if ( k != -1 )
608            ipos = k;
609          else
610            break;
611        } else {
612          found = j1;
613          break;
614        }
615      } else {
616        break;
617      }
618    }
619    if (found<0) {
620      assert (hash_[ipos].next==-1);
621      if (ipos==jpos) {
622        // first
623        hash_[ipos].index=numberCuts_;
624      } else {
625        // find next space
626        while ( true ) {
627          ++lastHash_;
628          assert (lastHash_<hashSize);
629          if ( hash_[lastHash_].index == -1 ) 
630            break;
631        }
632        hash_[ipos].next = lastHash_;
633        hash_[lastHash_].index = numberCuts_;
634      }
635      OsiRowCut2 * newCutPtr = new OsiRowCut2(whichType);
636      newCutPtr->setLb(newLb);
637      newCutPtr->setUb(newUb);
638      newCutPtr->setRow(vector);
639      rowCut_[numberCuts_++]=newCutPtr;
640      return 0;
641    } else {
642      return 1;
643    }
644  } else {
645    return -1;
646  }
647}
648// Add in cuts as normal cuts and delete
649void 
650CbcRowCuts::addCuts(OsiCuts & cs)
651{
652  for (int i=0;i<numberCuts_;i++) {
653    cs.insert(*rowCut_[i]);
654    delete rowCut_[i] ;
655    rowCut_[i] = NULL ;
656  }
657  numberCuts_=0;
658}
Note: See TracBrowser for help on using the repository browser.