limp-cbc-0.3.2.0: cbits/coin/CbcCountRowCut.cpp
/* $Id: CbcCountRowCut.cpp 1883 2013-04-06 13:33:15Z stefan $ */
// Copyright (C) 2002, International Business Machines
// Corporation and others. All Rights Reserved.
// This code is licensed under the terms of the Eclipse Public License (EPL).
#if defined(_MSC_VER)
// Turn off compiler warning about long names
# pragma warning(disable:4786)
#endif
#include <cassert>
#include "OsiRowCut.hpp"
#include "CbcModel.hpp"
#include "CbcCountRowCut.hpp"
#include "CbcNode.hpp"
//#define CHECK_CUT_COUNTS
// Default Constructor
CbcCountRowCut::CbcCountRowCut ()
:
OsiRowCut(),
owner_(NULL),
ownerCut_(-1),
numberPointingToThis_(0),
whichCutGenerator_(-1)
{
#ifdef CHECK_CUT_COUNTS
printf("CbcCountRowCut default constructor %x\n", this);
#endif
}
// Copy Constructor
CbcCountRowCut::CbcCountRowCut (const OsiRowCut & rhs)
: OsiRowCut(rhs),
owner_(NULL),
ownerCut_(-1),
numberPointingToThis_(0),
whichCutGenerator_(-1)
{
#ifdef CHECK_CUT_COUNTS
printf("CbcCountRowCut constructor %x from RowCut\n", this);
#endif
}
// Copy Constructor
CbcCountRowCut::CbcCountRowCut (const OsiRowCut & rhs,
CbcNodeInfo * info, int whichOne,
int whichGenerator,
int numberPointingToThis)
: OsiRowCut(rhs),
owner_(info),
ownerCut_(whichOne),
numberPointingToThis_(numberPointingToThis),
whichCutGenerator_(whichGenerator)
{
#ifdef CHECK_CUT_COUNTS
printf("CbcCountRowCut constructor %x from RowCut and info %d\n",
this, numberPointingToThis_);
#endif
//assert (!numberPointingToThis||numberPointingToThis==1000000000);
}
CbcCountRowCut::~CbcCountRowCut()
{
#ifdef CHECK_CUT_COUNTS
printf("CbcCountRowCut destructor %x - references %d\n", this,
numberPointingToThis_);
#endif
// Look at owner and delete
if (owner_)
owner_->deleteCut(ownerCut_);
ownerCut_ = -1234567;
}
// Increment number of references
void
CbcCountRowCut::increment(int change)
{
assert(ownerCut_ != -1234567);
numberPointingToThis_ += change;
}
// Decrement number of references and return number left
int
CbcCountRowCut::decrement(int change)
{
assert(ownerCut_ != -1234567);
// See if plausible number
if (change < 900000000) {
//assert(numberPointingToThis_>=change);
assert(numberPointingToThis_ >= 0);
if (numberPointingToThis_ < change) {
assert(numberPointingToThis_ > 0);
COIN_DETAIL_PRINT(printf("negative cut count %d - %d\n", numberPointingToThis_, change));
change = numberPointingToThis_;
}
numberPointingToThis_ -= change;
}
return numberPointingToThis_;
}
// Set information
void
CbcCountRowCut::setInfo(CbcNodeInfo * info, int whichOne)
{
owner_ = info;
ownerCut_ = whichOne;
}
// Returns true if can drop cut if slack basic
bool
CbcCountRowCut::canDropCut(const OsiSolverInterface * solver, int iRow) const
{
// keep if COIN_DBL_MAX otherwise keep if slack zero
if (effectiveness() < 1.0e20) {
return true;
} else if (effectiveness() != COIN_DBL_MAX) {
if (iRow >= solver->getNumRows())
return true;
const double * rowActivity = solver->getRowActivity();
const double * rowLower = solver->getRowLower();
const double * rowUpper = solver->getRowUpper();
double tolerance;
solver->getDblParam(OsiPrimalTolerance, tolerance) ;
double value = rowActivity[iRow];
if (value < rowLower[iRow] + tolerance ||
value > rowUpper[iRow] - tolerance)
return false;
else
return true;
} else {
return false;
}
}
static double multiplier[] = {1.23456789e2,-9.87654321};
static int hashCut (const OsiRowCut2 & x, int size)
{
int xN =x.row().getNumElements();
double xLb = x.lb();
double xUb = x.ub();
const int * xIndices = x.row().getIndices();
const double * xElements = x.row().getElements();
unsigned int hashValue;
double value=1.0;
if (xLb>-1.0e10)
value += xLb*multiplier[0];
if (xUb<1.0e10)
value += xUb*multiplier[1];
for( int j=0;j<xN;j++) {
int xColumn = xIndices[j];
double xValue = xElements[j];
int k=(j&1);
value += (j+1)*multiplier[k]*(xColumn+1)*xValue;
}
// should be compile time but too lazy for now
if (sizeof(value)>sizeof(hashValue)) {
assert (sizeof(value)==2*sizeof(hashValue));
union { double d; int i[2]; } xx;
xx.d = value;
hashValue = (xx.i[0] + xx.i[1]);
} else {
assert (sizeof(value)==sizeof(hashValue));
union { double d; unsigned int i[2]; } xx;
xx.d = value;
hashValue = xx.i[0];
}
return hashValue%(size);
}
static int hashCut2 (const OsiRowCut2 & x, int size)
{
int xN =x.row().getNumElements();
double xLb = x.lb();
double xUb = x.ub();
const int * xIndices = x.row().getIndices();
const double * xElements = x.row().getElements();
unsigned int hashValue;
double value=1.0;
if (xLb>-1.0e10)
value += xLb*multiplier[0];
if (xUb<1.0e10)
value += xUb*multiplier[1];
for( int j=0;j<xN;j++) {
int xColumn = xIndices[j];
double xValue = xElements[j];
int k=(j&1);
value += (j+1)*multiplier[k]*(xColumn+1)*xValue;
}
// should be compile time but too lazy for now
if (sizeof(value)>sizeof(hashValue)) {
assert (sizeof(value)==2*sizeof(hashValue));
union { double d; int i[2]; } xx;
xx.d = value;
hashValue = (xx.i[0] + xx.i[1]);
} else {
assert (sizeof(value)==sizeof(hashValue));
union { double d; unsigned int i[2]; } xx;
xx.d = value;
hashValue = xx.i[0];
}
return hashValue%(size);
}
static bool same (const OsiRowCut2 & x, const OsiRowCut2 & y)
{
int xN =x.row().getNumElements();
int yN =y.row().getNumElements();
bool identical=false;
if (xN==yN) {
double xLb = x.lb();
double xUb = x.ub();
double yLb = y.lb();
double yUb = y.ub();
if (fabs(xLb-yLb)<1.0e-8&&fabs(xUb-yUb)<1.0e-8) {
const int * xIndices = x.row().getIndices();
const double * xElements = x.row().getElements();
const int * yIndices = y.row().getIndices();
const double * yElements = y.row().getElements();
int j;
for( j=0;j<xN;j++) {
if (xIndices[j]!=yIndices[j])
break;
if (fabs(xElements[j]-yElements[j])>1.0e-12)
break;
}
identical = (j==xN);
}
}
return identical;
}
static bool same2 (const OsiRowCut2 & x, const OsiRowCut2 & y)
{
int xN =x.row().getNumElements();
int yN =y.row().getNumElements();
bool identical=false;
if (xN==yN) {
double xLb = x.lb();
double xUb = x.ub();
double yLb = y.lb();
double yUb = y.ub();
if (fabs(xLb-yLb)<1.0e-8&&fabs(xUb-yUb)<1.0e-8) {
const int * xIndices = x.row().getIndices();
const double * xElements = x.row().getElements();
const int * yIndices = y.row().getIndices();
const double * yElements = y.row().getElements();
int j;
for( j=0;j<xN;j++) {
if (xIndices[j]!=yIndices[j])
break;
if (fabs(xElements[j]-yElements[j])>1.0e-12)
break;
}
identical = (j==xN);
}
}
return identical;
}
CbcRowCuts::CbcRowCuts(int initialMaxSize, int hashMultiplier)
{
numberCuts_=0;
size_ = initialMaxSize;
hashMultiplier_ = hashMultiplier;
int hashSize=hashMultiplier_*size_;
if (size_) {
rowCut_ = new OsiRowCut2 * [size_];
hash_ = new CoinHashLink[hashSize];
} else {
rowCut_ = NULL;
hash_ = NULL;
}
for (int i=0;i<hashSize;i++) {
hash_[i].index=-1;
hash_[i].next=-1;
}
lastHash_=-1;
}
CbcRowCuts::~CbcRowCuts()
{
for (int i=0;i<numberCuts_;i++)
delete rowCut_[i];
delete [] rowCut_;
delete [] hash_;
}
CbcRowCuts::CbcRowCuts(const CbcRowCuts& rhs)
{
numberCuts_=rhs.numberCuts_;
hashMultiplier_ = rhs.hashMultiplier_;
size_ = rhs.size_;
int hashSize= size_*hashMultiplier_;
lastHash_=rhs.lastHash_;
if (size_) {
rowCut_ = new OsiRowCut2 * [size_];
hash_ = new CoinHashLink[hashSize];
for (int i=0;i<hashSize;i++) {
hash_[i] = rhs.hash_[i];
}
for (int i=0;i<numberCuts_;i++) {
if (rhs.rowCut_[i])
rowCut_[i]=new OsiRowCut2(*rhs.rowCut_[i]);
else
rowCut_[i]=NULL;
}
} else {
rowCut_ = NULL;
hash_ = NULL;
}
}
CbcRowCuts&
CbcRowCuts::operator=(const CbcRowCuts& rhs)
{
if (this != &rhs) {
for (int i=0;i<numberCuts_;i++)
delete rowCut_[i];
delete [] rowCut_;
delete [] hash_;
numberCuts_=rhs.numberCuts_;
hashMultiplier_ = rhs.hashMultiplier_;
size_ = rhs.size_;
lastHash_=rhs.lastHash_;
if (size_) {
rowCut_ = new OsiRowCut2 * [size_];
int hashSize= size_*hashMultiplier_;
hash_ = new CoinHashLink[hashSize];
for (int i=0;i<hashSize;i++) {
hash_[i] = rhs.hash_[i];
}
for (int i=0;i<numberCuts_;i++) {
if (rhs.rowCut_[i])
rowCut_[i]=new OsiRowCut2(*rhs.rowCut_[i]);
else
rowCut_[i]=NULL;
}
} else {
rowCut_ = NULL;
hash_ = NULL;
}
}
return *this;
}
void
CbcRowCuts::eraseRowCut(int sequence)
{
// find
assert (sequence>=0&&sequence<numberCuts_);
OsiRowCut2 * cut = rowCut_[sequence];
int hashSize= size_*hashMultiplier_;
int ipos = hashCut(*cut,hashSize);
int found = -1;
while ( true ) {
int j1 = hash_[ipos].index;
if ( j1 >= 0 ) {
if (j1!=sequence) {
int k = hash_[ipos].next;
if ( k != -1 )
ipos = k;
else
break;
} else {
found = j1;
break;
}
} else {
break;
}
}
assert (found>=0);
assert (hash_[ipos].index==sequence);
// shuffle up
while (hash_[ipos].next>=0) {
int k = hash_[ipos].next;
hash_[ipos]=hash_[k];
ipos=k;
}
delete cut;
// move last to found
numberCuts_--;
if (numberCuts_) {
ipos = hashCut(*rowCut_[numberCuts_],hashSize);
while ( true ) {
int j1 = hash_[ipos].index;
if (j1!=numberCuts_) {
int k = hash_[ipos].next;
ipos = k;
} else {
// change
hash_[ipos].index=found;
rowCut_[found]=rowCut_[numberCuts_];
rowCut_[numberCuts_]=NULL;
break;
}
}
}
assert (!rowCut_[numberCuts_]);
}
// Return 0 if added, 1 if not, -1 if not added because of space
int
CbcRowCuts::addCutIfNotDuplicate(const OsiRowCut & cut,int whichType)
{
int hashSize= size_*hashMultiplier_;
if (numberCuts_==size_) {
size_ = 2*size_+100;
hashSize=hashMultiplier_*size_;
OsiRowCut2 ** temp = new OsiRowCut2 * [size_];
delete [] hash_;
hash_ = new CoinHashLink[hashSize];
for (int i=0;i<hashSize;i++) {
hash_[i].index=-1;
hash_[i].next=-1;
}
for (int i=0;i<numberCuts_;i++) {
temp[i]=rowCut_[i];
int ipos = hashCut(*temp[i],hashSize);
int found = -1;
int jpos=ipos;
while ( true ) {
int j1 = hash_[ipos].index;
if ( j1 >= 0 ) {
if ( !same(*temp[i],*temp[j1]) ) {
int k = hash_[ipos].next;
if ( k != -1 )
ipos = k;
else
break;
} else {
found = j1;
break;
}
} else {
break;
}
}
if (found<0) {
assert (hash_[ipos].next==-1);
if (ipos==jpos) {
// first
hash_[ipos].index=i;
} else {
// find next space
while ( true ) {
++lastHash_;
assert (lastHash_<hashSize);
if ( hash_[lastHash_].index == -1 )
break;
}
hash_[ipos].next = lastHash_;
hash_[lastHash_].index = i;
}
}
}
delete [] rowCut_;
rowCut_ = temp;
}
if (numberCuts_<size_) {
double newLb = cut.lb();
double newUb = cut.ub();
CoinPackedVector vector = cut.row();
int numberElements =vector.getNumElements();
int * newIndices = vector.getIndices();
double * newElements = vector.getElements();
CoinSort_2(newIndices,newIndices+numberElements,newElements);
int i;
bool bad=false;
for (i=0;i<numberElements;i++) {
double value = fabs(newElements[i]);
if (value<1.0e-12||value>1.0e12)
bad=true;
}
if (bad)
return 1;
OsiRowCut2 newCut(whichType);
newCut.setLb(newLb);
newCut.setUb(newUb);
newCut.setRow(vector);
int ipos = hashCut(newCut,hashSize);
int found = -1;
int jpos=ipos;
while ( true ) {
int j1 = hash_[ipos].index;
if ( j1 >= 0 ) {
if ( !same(newCut,*rowCut_[j1]) ) {
int k = hash_[ipos].next;
if ( k != -1 )
ipos = k;
else
break;
} else {
found = j1;
break;
}
} else {
break;
}
}
if (found<0) {
assert (hash_[ipos].next==-1);
if (ipos==jpos) {
// first
hash_[ipos].index=numberCuts_;
} else {
// find next space
while ( true ) {
++lastHash_;
assert (lastHash_<hashSize);
if ( hash_[lastHash_].index == -1 )
break;
}
hash_[ipos].next = lastHash_;
hash_[lastHash_].index = numberCuts_;
}
OsiRowCut2 * newCutPtr = new OsiRowCut2(whichType);
newCutPtr->setLb(newLb);
newCutPtr->setUb(newUb);
newCutPtr->setRow(vector);
rowCut_[numberCuts_++]=newCutPtr;
return 0;
} else {
return 1;
}
} else {
return -1;
}
}
// Return 0 if added, 1 if not, -1 if not added because of space
int
CbcRowCuts::addCutIfNotDuplicateWhenGreedy(const OsiRowCut & cut,int whichType)
{
int hashSize= size_*hashMultiplier_;
if (numberCuts_==size_) {
size_ = 2*size_+100;
hashSize=hashMultiplier_*size_;
OsiRowCut2 ** temp = new OsiRowCut2 * [size_];
delete [] hash_;
hash_ = new CoinHashLink[hashSize];
for (int i=0;i<hashSize;i++) {
hash_[i].index=-1;
hash_[i].next=-1;
}
for (int i=0;i<numberCuts_;i++) {
temp[i]=rowCut_[i];
int ipos = hashCut2(*temp[i],hashSize);
int found = -1;
int jpos=ipos;
while ( true ) {
int j1 = hash_[ipos].index;
if ( j1 >= 0 ) {
if ( !same2(*temp[i],*temp[j1]) ) {
int k = hash_[ipos].next;
if ( k != -1 )
ipos = k;
else
break;
} else {
found = j1;
break;
}
} else {
break;
}
}
if (found<0) {
assert (hash_[ipos].next==-1);
if (ipos==jpos) {
// first
hash_[ipos].index=i;
} else {
// find next space
while ( true ) {
++lastHash_;
assert (lastHash_<hashSize);
if ( hash_[lastHash_].index == -1 )
break;
}
hash_[ipos].next = lastHash_;
hash_[lastHash_].index = i;
}
}
}
delete [] rowCut_;
rowCut_ = temp;
}
if (numberCuts_<size_) {
double newLb = cut.lb();
double newUb = cut.ub();
CoinPackedVector vector = cut.row();
int numberElements =vector.getNumElements();
int * newIndices = vector.getIndices();
double * newElements = vector.getElements();
CoinSort_2(newIndices,newIndices+numberElements,newElements);
int i;
bool bad=false;
for (i=0;i<numberElements;i++) {
double value = fabs(newElements[i]);
if (value<1.0e-12||value>1.0e12)
bad=true;
}
if (bad)
return 1;
OsiRowCut2 newCut(whichType);
newCut.setLb(newLb);
newCut.setUb(newUb);
newCut.setRow(vector);
int ipos = hashCut2(newCut,hashSize);
int found = -1;
int jpos=ipos;
while ( true ) {
int j1 = hash_[ipos].index;
if ( j1 >= 0 ) {
if ( !same2(newCut,*rowCut_[j1]) ) {
int k = hash_[ipos].next;
if ( k != -1 )
ipos = k;
else
break;
} else {
found = j1;
break;
}
} else {
break;
}
}
if (found<0) {
assert (hash_[ipos].next==-1);
if (ipos==jpos) {
// first
hash_[ipos].index=numberCuts_;
} else {
// find next space
while ( true ) {
++lastHash_;
assert (lastHash_<hashSize);
if ( hash_[lastHash_].index == -1 )
break;
}
hash_[ipos].next = lastHash_;
hash_[lastHash_].index = numberCuts_;
}
OsiRowCut2 * newCutPtr = new OsiRowCut2(whichType);
newCutPtr->setLb(newLb);
newCutPtr->setUb(newUb);
newCutPtr->setRow(vector);
rowCut_[numberCuts_++]=newCutPtr;
return 0;
} else {
return 1;
}
} else {
return -1;
}
}
// Add in cuts as normal cuts and delete
void
CbcRowCuts::addCuts(OsiCuts & cs)
{
for (int i=0;i<numberCuts_;i++) {
cs.insert(*rowCut_[i]);
delete rowCut_[i] ;
rowCut_[i] = NULL ;
}
numberCuts_=0;
}