source: trunk/Cbc/src/CbcCountRowCut.cpp

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

script to format sources

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 18.8 KB
Line 
1/* $Id: CbcCountRowCut.cpp 2465 2019-01-03 19:26:52Z lou $ */
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  : OsiRowCut()
20  , owner_(NULL)
21  , ownerCut_(-1)
22  , numberPointingToThis_(0)
23  , whichCutGenerator_(-1)
24{
25#ifdef CHECK_CUT_COUNTS
26  printf("CbcCountRowCut default constructor %x\n", this);
27#endif
28}
29
30// Copy Constructor
31CbcCountRowCut::CbcCountRowCut(const OsiRowCut &rhs)
32  : OsiRowCut(rhs)
33  , owner_(NULL)
34  , ownerCut_(-1)
35  , numberPointingToThis_(0)
36  , whichCutGenerator_(-1)
37{
38#ifdef CHECK_CUT_COUNTS
39  printf("CbcCountRowCut constructor %x from RowCut\n", this);
40#endif
41}
42// Copy Constructor
43CbcCountRowCut::CbcCountRowCut(const OsiRowCut &rhs,
44  CbcNodeInfo *info, int whichOne,
45  int whichGenerator,
46  int numberPointingToThis)
47  : OsiRowCut(rhs)
48  , owner_(info)
49  , ownerCut_(whichOne)
50  , numberPointingToThis_(numberPointingToThis)
51  , whichCutGenerator_(whichGenerator)
52{
53#ifdef CHECK_CUT_COUNTS
54  printf("CbcCountRowCut constructor %x from RowCut and info %d\n",
55    this, numberPointingToThis_);
56#endif
57  //assert (!numberPointingToThis||numberPointingToThis==1000000000);
58}
59CbcCountRowCut::~CbcCountRowCut()
60{
61#ifdef CHECK_CUT_COUNTS
62  printf("CbcCountRowCut destructor %x - references %d\n", this,
63    numberPointingToThis_);
64#endif
65  // Look at owner and delete
66  if (owner_)
67    owner_->deleteCut(ownerCut_);
68  ownerCut_ = -1234567;
69}
70// Increment number of references
71void CbcCountRowCut::increment(int change)
72{
73  assert(ownerCut_ != -1234567);
74  numberPointingToThis_ += change;
75}
76
77// Decrement number of references and return number left
78int CbcCountRowCut::decrement(int change)
79{
80  assert(ownerCut_ != -1234567);
81  // See if plausible number
82  if (change < 900000000) {
83    //assert(numberPointingToThis_>=change);
84    assert(numberPointingToThis_ >= 0);
85    if (numberPointingToThis_ < change) {
86      assert(numberPointingToThis_ > 0);
87      COIN_DETAIL_PRINT(printf("negative cut count %d - %d\n", numberPointingToThis_, change));
88      change = numberPointingToThis_;
89    }
90    numberPointingToThis_ -= change;
91  }
92  return numberPointingToThis_;
93}
94
95// Set information
96void CbcCountRowCut::setInfo(CbcNodeInfo *info, int whichOne)
97{
98  owner_ = info;
99  ownerCut_ = whichOne;
100}
101// Returns true if can drop cut if slack basic
102bool CbcCountRowCut::canDropCut(const OsiSolverInterface *solver, int iRow) const
103{
104  // keep if COIN_DBL_MAX otherwise keep if slack zero
105  if (effectiveness() < 1.0e20) {
106    return true;
107  } else if (effectiveness() != COIN_DBL_MAX) {
108    if (iRow >= solver->getNumRows())
109      return true;
110    const double *rowActivity = solver->getRowActivity();
111    const double *rowLower = solver->getRowLower();
112    const double *rowUpper = solver->getRowUpper();
113    double tolerance;
114    solver->getDblParam(OsiPrimalTolerance, tolerance);
115    double value = rowActivity[iRow];
116    if (value < rowLower[iRow] + tolerance || value > rowUpper[iRow] - tolerance)
117      return false;
118    else
119      return true;
120  } else {
121    return false;
122  }
123}
124static double multiplier[] = { 1.23456789e2, -9.87654321 };
125static int hashCut(const OsiRowCut2 &x, int size)
126{
127  int xN = x.row().getNumElements();
128  double xLb = x.lb();
129  double xUb = x.ub();
130  const int *xIndices = x.row().getIndices();
131  const double *xElements = x.row().getElements();
132  unsigned int hashValue;
133  double value = 1.0;
134  if (xLb > -1.0e10)
135    value += xLb * multiplier[0];
136  if (xUb < 1.0e10)
137    value += xUb * multiplier[1];
138  for (int j = 0; j < xN; j++) {
139    int xColumn = xIndices[j];
140    double xValue = xElements[j];
141    int k = (j & 1);
142    value += (j + 1) * multiplier[k] * (xColumn + 1) * xValue;
143  }
144  // should be compile time but too lazy for now
145  union {
146    double d;
147    unsigned int i[2];
148  } xx;
149  if (sizeof(value) > sizeof(hashValue)) {
150    assert(sizeof(value) == 2 * sizeof(hashValue));
151    xx.d = value;
152    hashValue = (xx.i[0] + xx.i[1]);
153  } else {
154    assert(sizeof(value) == sizeof(hashValue));
155    xx.d = value;
156    hashValue = xx.i[0];
157  }
158  return hashValue % (size);
159}
160static int hashCut2(const OsiRowCut2 &x, int size)
161{
162  int xN = x.row().getNumElements();
163  double xLb = x.lb();
164  double xUb = x.ub();
165  const int *xIndices = x.row().getIndices();
166  const double *xElements = x.row().getElements();
167  unsigned int hashValue;
168  double value = 1.0;
169  if (xLb > -1.0e10)
170    value += xLb * multiplier[0];
171  if (xUb < 1.0e10)
172    value += xUb * multiplier[1];
173  for (int j = 0; j < xN; j++) {
174    int xColumn = xIndices[j];
175    double xValue = xElements[j];
176    int k = (j & 1);
177    value += (j + 1) * multiplier[k] * (xColumn + 1) * xValue;
178  }
179  // should be compile time but too lazy for now
180  if (sizeof(value) > sizeof(hashValue)) {
181    assert(sizeof(value) == 2 * sizeof(hashValue));
182    union {
183      double d;
184      unsigned int i[2];
185    } xx;
186    xx.d = value;
187    hashValue = (xx.i[0] + xx.i[1]);
188  } else {
189    assert(sizeof(value) == sizeof(hashValue));
190    union {
191      double d;
192      unsigned int i[2];
193    } xx;
194    xx.d = value;
195    hashValue = xx.i[0];
196  }
197  return hashValue % (size);
198}
199static bool same(const OsiRowCut2 &x, const OsiRowCut2 &y)
200{
201  int xN = x.row().getNumElements();
202  int yN = y.row().getNumElements();
203  bool identical = false;
204  if (xN == yN) {
205    double xLb = x.lb();
206    double xUb = x.ub();
207    double yLb = y.lb();
208    double yUb = y.ub();
209    if (fabs(xLb - yLb) < 1.0e-8 && fabs(xUb - yUb) < 1.0e-8) {
210      const int *xIndices = x.row().getIndices();
211      const double *xElements = x.row().getElements();
212      const int *yIndices = y.row().getIndices();
213      const double *yElements = y.row().getElements();
214      int j;
215      for (j = 0; j < xN; j++) {
216        if (xIndices[j] != yIndices[j])
217          break;
218        if (fabs(xElements[j] - yElements[j]) > 1.0e-12)
219          break;
220      }
221      identical = (j == xN);
222    }
223  }
224  return identical;
225}
226static bool same2(const OsiRowCut2 &x, const OsiRowCut2 &y)
227{
228  int xN = x.row().getNumElements();
229  int yN = y.row().getNumElements();
230  bool identical = false;
231  if (xN == yN) {
232    double xLb = x.lb();
233    double xUb = x.ub();
234    double yLb = y.lb();
235    double yUb = y.ub();
236    if (fabs(xLb - yLb) < 1.0e-8 && fabs(xUb - yUb) < 1.0e-8) {
237      const int *xIndices = x.row().getIndices();
238      const double *xElements = x.row().getElements();
239      const int *yIndices = y.row().getIndices();
240      const double *yElements = y.row().getElements();
241      int j;
242      for (j = 0; j < xN; j++) {
243        if (xIndices[j] != yIndices[j])
244          break;
245        if (fabs(xElements[j] - yElements[j]) > 1.0e-12)
246          break;
247      }
248      identical = (j == xN);
249    }
250  }
251  return identical;
252}
253CbcRowCuts::CbcRowCuts(int initialMaxSize, int hashMultiplier)
254{
255  numberCuts_ = 0;
256  size_ = initialMaxSize;
257  hashMultiplier_ = hashMultiplier;
258  int hashSize = hashMultiplier_ * size_;
259  if (size_) {
260    rowCut_ = new OsiRowCut2 *[size_];
261    hash_ = new CoinHashLink[hashSize];
262  } else {
263    rowCut_ = NULL;
264    hash_ = NULL;
265  }
266  for (int i = 0; i < hashSize; i++) {
267    hash_[i].index = -1;
268    hash_[i].next = -1;
269  }
270  lastHash_ = -1;
271}
272CbcRowCuts::~CbcRowCuts()
273{
274  for (int i = 0; i < numberCuts_; i++)
275    delete rowCut_[i];
276  delete[] rowCut_;
277  delete[] hash_;
278}
279CbcRowCuts::CbcRowCuts(const CbcRowCuts &rhs)
280{
281  numberCuts_ = rhs.numberCuts_;
282  hashMultiplier_ = rhs.hashMultiplier_;
283  size_ = rhs.size_;
284  int hashSize = size_ * hashMultiplier_;
285  lastHash_ = rhs.lastHash_;
286  if (size_) {
287    rowCut_ = new OsiRowCut2 *[size_];
288    hash_ = new CoinHashLink[hashSize];
289    for (int i = 0; i < hashSize; i++) {
290      hash_[i] = rhs.hash_[i];
291    }
292    for (int i = 0; i < numberCuts_; i++) {
293      if (rhs.rowCut_[i])
294        rowCut_[i] = new OsiRowCut2(*rhs.rowCut_[i]);
295      else
296        rowCut_[i] = NULL;
297    }
298  } else {
299    rowCut_ = NULL;
300    hash_ = NULL;
301  }
302}
303CbcRowCuts &
304CbcRowCuts::operator=(const CbcRowCuts &rhs)
305{
306  if (this != &rhs) {
307    for (int i = 0; i < numberCuts_; i++)
308      delete rowCut_[i];
309    delete[] rowCut_;
310    delete[] hash_;
311    numberCuts_ = rhs.numberCuts_;
312    hashMultiplier_ = rhs.hashMultiplier_;
313    size_ = rhs.size_;
314    lastHash_ = rhs.lastHash_;
315    if (size_) {
316      rowCut_ = new OsiRowCut2 *[size_];
317      int hashSize = size_ * hashMultiplier_;
318      hash_ = new CoinHashLink[hashSize];
319      for (int i = 0; i < hashSize; i++) {
320        hash_[i] = rhs.hash_[i];
321      }
322      for (int i = 0; i < numberCuts_; i++) {
323        if (rhs.rowCut_[i])
324          rowCut_[i] = new OsiRowCut2(*rhs.rowCut_[i]);
325        else
326          rowCut_[i] = NULL;
327      }
328    } else {
329      rowCut_ = NULL;
330      hash_ = NULL;
331    }
332  }
333  return *this;
334}
335void CbcRowCuts::eraseRowCut(int sequence)
336{
337  // find
338  assert(sequence >= 0 && sequence < numberCuts_);
339  OsiRowCut2 *cut = rowCut_[sequence];
340  int hashSize = size_ * hashMultiplier_;
341  int ipos = hashCut(*cut, hashSize);
342  int found = -1;
343  while (true) {
344    int j1 = hash_[ipos].index;
345    if (j1 >= 0) {
346      if (j1 != sequence) {
347        int k = hash_[ipos].next;
348        if (k != -1)
349          ipos = k;
350        else
351          break;
352      } else {
353        found = j1;
354        break;
355      }
356    } else {
357      break;
358    }
359  }
360  assert(found >= 0);
361  assert(hash_[ipos].index == sequence);
362  // shuffle up
363  while (hash_[ipos].next >= 0) {
364    int k = hash_[ipos].next;
365    hash_[ipos] = hash_[k];
366    ipos = k;
367  }
368  hash_[ipos].index = -1;
369  // move last to found
370  numberCuts_--;
371  assert(found == numberCuts_); // debug when fails
372  if (numberCuts_ && found < numberCuts_) {
373    ipos = hashCut(*rowCut_[numberCuts_], hashSize);
374    while (true) {
375      int j1 = hash_[ipos].index;
376      if (j1 != numberCuts_) {
377        int k = hash_[ipos].next;
378        ipos = k;
379        assert(ipos >= 0);
380      } else {
381        // change
382        hash_[ipos].index = found;
383        rowCut_[found] = rowCut_[numberCuts_];
384        rowCut_[numberCuts_] = NULL;
385        break;
386      }
387    }
388  }
389  delete cut;
390  rowCut_[numberCuts_] = NULL;
391  //assert (!rowCut_[numberCuts_-1]);
392}
393// Truncate
394void CbcRowCuts::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 CbcRowCuts::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 CbcRowCuts::addCutIfNotDuplicateWhenGreedy(const OsiRowCut &cut, int whichType)
589{
590  int hashSize = size_ * hashMultiplier_;
591  if (numberCuts_ == size_) {
592    size_ = 2 * size_ + 100;
593    hashSize = hashMultiplier_ * size_;
594    OsiRowCut2 **temp = new OsiRowCut2 *[size_];
595    delete[] hash_;
596    hash_ = new CoinHashLink[hashSize];
597    for (int i = 0; i < hashSize; i++) {
598      hash_[i].index = -1;
599      hash_[i].next = -1;
600    }
601    lastHash_ = -1;
602    for (int i = 0; i < numberCuts_; i++) {
603      temp[i] = rowCut_[i];
604      int ipos = hashCut2(*temp[i], hashSize);
605      int found = -1;
606      int jpos = ipos;
607      while (true) {
608        int j1 = hash_[ipos].index;
609
610        if (j1 >= 0) {
611          if (!same2(*temp[i], *temp[j1])) {
612            int k = hash_[ipos].next;
613            if (k != -1)
614              ipos = k;
615            else
616              break;
617          } else {
618            found = j1;
619            break;
620          }
621        } else {
622          break;
623        }
624      }
625      if (found < 0) {
626        assert(hash_[ipos].next == -1);
627        if (ipos == jpos) {
628          // first
629          hash_[ipos].index = i;
630        } else {
631          // find next space
632          while (true) {
633            ++lastHash_;
634            assert(lastHash_ < hashSize);
635            if (hash_[lastHash_].index == -1)
636              break;
637          }
638          hash_[ipos].next = lastHash_;
639          hash_[lastHash_].index = i;
640        }
641      }
642    }
643    delete[] rowCut_;
644    rowCut_ = temp;
645  }
646  if (numberCuts_ < size_) {
647    double newLb = cut.lb();
648    double newUb = cut.ub();
649    CoinPackedVector vector = cut.row();
650    int numberElements = vector.getNumElements();
651    int *newIndices = vector.getIndices();
652    double *newElements = vector.getElements();
653    CoinSort_2(newIndices, newIndices + numberElements, newElements);
654    int i;
655    bool bad = false;
656    for (i = 0; i < numberElements; i++) {
657      double value = fabs(newElements[i]);
658      if (value < 1.0e-12 || value > 1.0e12)
659        bad = true;
660    }
661    if (bad)
662      return 1;
663    OsiRowCut2 newCut(whichType);
664    newCut.setLb(newLb);
665    newCut.setUb(newUb);
666    newCut.setRow(vector);
667    int ipos = hashCut2(newCut, hashSize);
668    int found = -1;
669    int jpos = ipos;
670    while (true) {
671      int j1 = hash_[ipos].index;
672
673      if (j1 >= 0) {
674        if (!same2(newCut, *rowCut_[j1])) {
675          int k = hash_[ipos].next;
676          if (k != -1)
677            ipos = k;
678          else
679            break;
680        } else {
681          found = j1;
682          break;
683        }
684      } else {
685        break;
686      }
687    }
688    if (found < 0) {
689      assert(hash_[ipos].next == -1);
690      if (ipos == jpos) {
691        // first
692        hash_[ipos].index = numberCuts_;
693      } else {
694        // find next space
695        while (true) {
696          ++lastHash_;
697          assert(lastHash_ < hashSize);
698          if (hash_[lastHash_].index == -1)
699            break;
700        }
701        hash_[ipos].next = lastHash_;
702        hash_[lastHash_].index = numberCuts_;
703      }
704      OsiRowCut2 *newCutPtr = new OsiRowCut2(whichType);
705      newCutPtr->setLb(newLb);
706      newCutPtr->setUb(newUb);
707      newCutPtr->setRow(vector);
708      rowCut_[numberCuts_++] = newCutPtr;
709      //printf("addedGreedyGlobalCut of size %d to %p - cuts size %d\n",
710      //     cut.row().getNumElements(),this,numberCuts_);
711      return 0;
712    } else {
713      return 1;
714    }
715  } else {
716    return -1;
717  }
718}
719// Add in cuts as normal cuts and delete
720void CbcRowCuts::addCuts(OsiCuts &cs)
721{
722  for (int i = 0; i < numberCuts_; i++) {
723    cs.insert(*rowCut_[i]);
724    delete rowCut_[i];
725    rowCut_[i] = NULL;
726  }
727  numberCuts_ = 0;
728}
729
730/* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2
731*/
Note: See TracBrowser for help on using the repository browser.