OsiDylpWarmStartBasis.cpp

#ifdef COIN_USE_DYLP

#ifdef _MSC_VER

/* Turn off compiler warning about long names */

#  pragma warning(disable:4786)

#endif // _MSC_VER

/* Cut name lengths for readability. */

#define ODWSB OsiDylpWarmStartBasis
#define CWSB CoinWarmStartBasis

namespace {
  char sccsid[] = "%W%  %G%" ;
  char cvsid[] = "$Id: OsiDylpWarmStartBasis.cpp,v 1.2 2003/10/23 17:32:22 lou-oss Exp $" ;
}

#include <vector>
#include <cassert>
#include <iostream>
#include "OsiDylpWarmStartBasis.hpp"

using std::vector ;

/*
  A macro to standardize the size of the status arrays. CWSB::Status is the
  status enum, and currently it occupies 2 bits, packed 4 per char (note the
  implicit assumption that a char is 1 byte).  This macro calculates the
  number of bytes needed to hold ns status entires, rounded up to the nearest
  int.
*/

#define STATPERBYTE 4
#define STATALLOCUNIT sizeof(int)
#define STATBYTES(zz_ns_zz) \
  (((zz_ns_zz+STATALLOCUNIT*STATPERBYTE-1)/(STATALLOCUNIT*STATPERBYTE))* \
   STATALLOCUNIT)
  


ODWSB::OsiDylpWarmStartBasis ()

  : CWSB(),
    phase_(dyINV),
    constraintStatus_(0)

{ /* intentionally left blank */ }


ODWSB::OsiDylpWarmStartBasis (const OsiDylpWarmStartBasis &ws)

  : CWSB(ws),
    phase_(ws.phase_),
    constraintStatus_(0)

{ int constatsze = STATBYTES(getNumArtificial()) ;
  constraintStatus_ = new char[constatsze] ;
  memcpy(constraintStatus_,ws.constraintStatus_,constatsze) ; }


CoinWarmStart *ODWSB::clone () const

{ const ODWSB *odwsb_orig = dynamic_cast<const ODWSB *>(this) ;
  ODWSB *odwsb_new = 0 ;
  if (odwsb_orig)
  { odwsb_new = new OsiDylpWarmStartBasis(*odwsb_orig) ; }
  return (dynamic_cast<CoinWarmStart *>(odwsb_new)) ; }

ODWSB::OsiDylpWarmStartBasis
  (int ns, int na, const char *sStat, const char *aStat, const char *cStat)

  : CWSB(ns,na,sStat,aStat),
    phase_(dyPRIMAL1),
    constraintStatus_(0)

{ int constatsze = STATBYTES(na) ;
  constraintStatus_ = new char[constatsze] ;
/*
  If a status array is given, copy it in. If there's no array provided, assume
  all constraints are active. Set up a byte with the correct pattern and use it
  to initialize the constraint status.
*/
  if (cStat)
  { memcpy(constraintStatus_,cStat,constatsze) ; }
  else
  { char byteActive = 0 ;
    int i ;
    for (i = 0 ; i <= 3 ; i++) setStatus(&byteActive,i,CWSB::atLowerBound) ;
    memset(constraintStatus_,byteActive,constatsze) ; } }

OsiDylpWarmStartBasis& ODWSB::operator= (const OsiDylpWarmStartBasis &rhs)

{ if (this != &rhs)
  { CWSB::operator=(rhs) ;
    phase_ = rhs.phase_ ;
    delete[] constraintStatus_ ;
    int constatsze = STATBYTES(getNumArtificial()) ;
    constraintStatus_ = new char[constatsze] ;
    memcpy(constraintStatus_,rhs.constraintStatus_,constatsze) ; }
  
  return *this ; }


void ODWSB::assignBasisStatus
  (int ns, int na, char *&sStat, char *&aStat, char *&cStat)

{ CWSB::assignBasisStatus(ns,na,sStat,aStat) ;
  phase_ = dyPRIMAL1 ;
  delete[] constraintStatus_ ;
  constraintStatus_ = cStat ;
  cStat = 0 ; }

void ODWSB::assignBasisStatus (int ns, int na, char *&sStat, char *&aStat)

{ int constatsze = STATBYTES(na) ;
  char byteActive = 0 ;
  int i ;

  CWSB::assignBasisStatus(ns,na,sStat,aStat) ;
  phase_ = dyPRIMAL1 ;

  delete[] constraintStatus_ ;
  constraintStatus_ = new char[constatsze] ;
  for (i = 0 ; i <= 3 ; i++) setStatus(&byteActive,i,CWSB::atLowerBound) ;
  memset(constraintStatus_,byteActive,constatsze) ; }

ODWSB::~OsiDylpWarmStartBasis () { delete[] constraintStatus_ ; }

void ODWSB::setSize (int ns, int na)

{ CWSB::setSize(ns,na) ;
  phase_ = dyINV ;
  delete[] constraintStatus_ ;
  int constatsze = STATBYTES(na) ;
  constraintStatus_ = new char[constatsze] ;
  assert(((int) CWSB::isFree == 0)) ;
  memset(constraintStatus_,0,constatsze) ; }

void ODWSB::resize (int numRows, int numCols)

{ int concnt = getNumArtificial() ;
  
  CWSB::resize(numRows,numCols) ;

  if (numRows != concnt)
  { int oldsze = STATBYTES(concnt) ;
    int newsze = STATBYTES(numRows) ;
    char *newStat = new char[newsze] ;
/*
  If the new capacity is smaller, truncate the existing basis.
*/
    if (oldsze > newsze)
    { memcpy(newStat,constraintStatus_,newsze) ; }
/*
  If the new capacity is larger, copy the existing basis, then mark the
  additional constraints as active. We need to be a bit careful here, because
  the allocated sizes are rounded out. The strategy is to (possibly) overlap
  one byte, correcting it after initialization.
*/
    else
    { char byteActive = 0 ;
      int i,actualBytes ;
      actualBytes = concnt/STATPERBYTE ;
      for (i = 0 ; i <= 3 ; i++) setStatus(&byteActive,i,CWSB::atLowerBound) ;
      memcpy(newStat,constraintStatus_,oldsze) ;
      memset(newStat+actualBytes,byteActive,newsze-actualBytes) ;
      for (i = 0 ; i < concnt%STATPERBYTE ; i++)
        setStatus(newStat+actualBytes,i,
                  getStatus(constraintStatus_+actualBytes,i)) ; }

    delete [] constraintStatus_ ;
    constraintStatus_ = newStat ; } }


/*
  To elaborate on the above comment: When a tight constraint is removed, new
  extreme points are exposed. There's a reasonable likelihood they'll be
  desireable points (since the tight constraint was most likely tight because
  it was blocking movement in a desireable direction). In essence, we want to
  take the next primal pivot and see what comes tight. That's a fair bit of
  work, and on balance best left to the client to decide if it's appropriate,
  or if something else should be done.
*/

void ODWSB::deleteRows (int number, const int *which)

{ int oldconcnt = getNumArtificial() ;
  int i,k ;

  CWSB::deleteRows(number,which) ;

  int delcnt = 0 ;
  vector<bool> deleted = vector<bool>(oldconcnt) ;
  for (k = 0 ; k < number ; k++)
  { i = which[k] ;
    if (i >= 0 && i < oldconcnt && !deleted[i])
    { delcnt++ ;
      deleted[i] = true ; } }

  int newsze = STATBYTES(oldconcnt-delcnt) ;
  char *newStat = new char[newsze] ;

  k = 0 ;
  for (i = 0 ; i < oldconcnt ; i++)
  { Status status = getConStatus(i);
    if (!deleted[i])
    { setStatus(newStat,k,status) ;
      k++ ; } }
  
  delete [] constraintStatus_ ;
  constraintStatus_ = newStat ; }

/*
  The good news is that CWSB::deleteColumns works just fine for ODWSB.
*/



int ODWSB::numberActiveConstraints () const

{ int i ;
  int concnt = getNumArtificial() ;
  int actcnt = 0 ;

  for (i = 0 ; i < concnt ; i++)
    if (getStatus(constraintStatus_,i) == CWSB::atLowerBound) actcnt++ ;
  
  return (actcnt) ; }


CoinWarmStartDiff *ODWSB::generateDiff
  (const CoinWarmStart *const oldCWS) const
{
/*
  Make sure the parameter is an OsiDylpWarmStartBasis.
*/
  const OsiDylpWarmStartBasis *oldBasis =
      dynamic_cast<const OsiDylpWarmStartBasis *>(oldCWS) ;
  if (!oldBasis)
  { throw CoinError("Old basis not OsiDylpWarmStartBasis.",
                    "generateDiff","OsiDylpWarmStartBasis") ; }
  const OsiDylpWarmStartBasis *newBasis = this ;
/*
  Make sure newBasis is equal or bigger than oldBasis. Calculate the worst case
  number of diffs and allocate vectors to hold them.
*/
  const int oldArtifCnt = oldBasis->getNumArtificial() ;
  const int newArtifCnt = newBasis->getNumArtificial() ;

  assert(newArtifCnt >= oldArtifCnt) ;
/*
  Ok, we're good to go. Call CWSB::generateDiff to deal with the logical and
  structural arrays.
*/
  const CoinWarmStartBasisDiff *cwsbDiff =
    dynamic_cast<const CoinWarmStartBasisDiff *>(CWSB::generateDiff(oldCWS)) ;
/*
  Now generate diffs for the constraint array.
*/

  int sizeOldArtif = (oldArtifCnt+15)>>4 ;
  int sizeNewArtif = (newArtifCnt+15)>>4 ;
  int maxBasisLength = sizeNewArtif ;

  unsigned int *diffNdx = new unsigned int [maxBasisLength]; 
  unsigned int *diffVal = new unsigned int [maxBasisLength]; 
/*
  Scan the constraint status.
  For the portion of the status arrays which overlap, create
  diffs. Then add any additional status from newBasis.
*/
  const unsigned int *oldStatus =
      reinterpret_cast<const unsigned int *>(oldBasis->getConstraintStatus()) ;
  const unsigned int *newStatus = 
      reinterpret_cast<const unsigned int *>(newBasis->getConstraintStatus()) ;
  int numberChanged = 0 ;
  int i ;
  for (i = 0 ; i < sizeOldArtif ; i++)
  { if (oldStatus[i] != newStatus[i])
    { diffNdx[numberChanged] = i ;
      diffVal[numberChanged++] = newStatus[i] ; } }
  for ( ; i < sizeNewArtif ; i++)
  { diffNdx[numberChanged] = i ;
    diffVal[numberChanged++] = newStatus[i] ; }
/*
  Create the object of our desire.
*/
  OsiDylpWarmStartBasisDiff *diff =
    new OsiDylpWarmStartBasisDiff(numberChanged,diffNdx,diffVal,cwsbDiff) ;
/*
  Clean up and return.
*/
  delete[] diffNdx ;
  delete[] diffVal ;

  return (dynamic_cast<CoinWarmStartDiff *>(diff)) ; }

void ODWSB::applyDiff (const CoinWarmStartDiff *const cwsdDiff)
{
/*
  Make sure we have an OsiDylpWarmStartBasisDiff
*/
  const OsiDylpWarmStartBasisDiff *diff =
    dynamic_cast<const OsiDylpWarmStartBasisDiff *>(cwsdDiff) ;
  if (!diff)
  { throw CoinError("Diff not OsiDylpWarmStartBasisDiff.",
                    "applyDiff","OsiDylpWarmStartBasis") ; }
/*
  Call CWSB::applyDiff to deal with the logical and structural status.
*/
  CWSB::applyDiff(cwsdDiff) ;
/*
  Now fix up the constraint status array. Application of the diff is by
  straighforward replacement of words in the status array.
*/
  const int numberChanges = diff->consze_ ;
  const unsigned int *diffNdxs = diff->condiffNdxs_ ;
  const unsigned int *diffVals = diff->condiffVals_ ;
  unsigned int *constraintStatus =
      reinterpret_cast<unsigned int *>(this->getConstraintStatus()) ;

  for (int i = 0 ; i < numberChanges ; i++)
  { unsigned int diffNdx = diffNdxs[i] ;
    unsigned int diffVal = diffVals[i] ;
    constraintStatus[diffNdx] = diffVal ; }

  return ; }




void ODWSB::print () const

{ char conlett[] = {'I','?','?','A'} ;
  char statlett[] = {'F','B','U','L'} ;
  int i,basic_logicals,basic_structurals ;

  std::cout << "ODWSB: " ;
  std::cout << getNumArtificial() << " constraints (" <<
               numberActiveConstraints() << " active), " ;
  std::cout << getNumStructural() << " variables." << std::endl ;

  std::cout << "Rows: " ;
  for (i = 0 ; i < getNumArtificial() ; i++)
  { std::cout << conlett[getConStatus(i)] ; }
  std::cout << std::endl ;

  std::cout << "      " ;
  basic_logicals = 0 ;
  for (i = 0 ; i < getNumArtificial() ; i++)
  { std::cout << statlett[getArtifStatus(i)] ;
    if (getArtifStatus(i) == CWSB::basic) basic_logicals++ ; }
  std::cout << std::endl ;
  
  std::cout << "Cols: " ;
  basic_structurals = 0 ;
  for (i = 0 ; i < getNumStructural() ; i++)
  { std::cout << statlett[getStructStatus(i)] ;
    if (getStructStatus(i) == CWSB::basic) basic_structurals++ ; }

  std::cout << std::endl << "   basic: ("
            << basic_structurals << " + " << basic_logicals << ")" ;
  std::cout << std::endl ;
  
  return ; }





/* Routines for OsiDylpWarmStartBasisDiff */

/*
  Constructor given constraint diff data and a pointer to a
  CoinWarmStartBasisDiff object.
*/
OsiDylpWarmStartBasisDiff::OsiDylpWarmStartBasisDiff (int sze,
  const unsigned int *const diffNdxs, const unsigned int *const diffVals,
  const CoinWarmStartBasisDiff *const cwsbd)

  : CoinWarmStartBasisDiff(*cwsbd),
    consze_(sze),
    condiffNdxs_(0),
    condiffVals_(0)

{ if (sze > 0)
  { condiffNdxs_ = new unsigned int[sze] ;
    memcpy(condiffNdxs_,diffNdxs,sze*sizeof(unsigned int)) ;
    condiffVals_ = new unsigned int[sze] ;
    memcpy(condiffVals_,diffVals,sze*sizeof(unsigned int)) ; }
  
  return ; }

/*
  Copy constructor
*/
OsiDylpWarmStartBasisDiff::OsiDylpWarmStartBasisDiff
  (const OsiDylpWarmStartBasisDiff &odwsbd)
  : CoinWarmStartBasisDiff(odwsbd),
    consze_(odwsbd.consze_),
    condiffNdxs_(0),
    condiffVals_(0)
{ if (odwsbd.consze_ > 0)
  { condiffNdxs_ = new unsigned int[odwsbd.consze_] ;
    memcpy(condiffNdxs_,odwsbd.condiffNdxs_,
           odwsbd.consze_*sizeof(unsigned int)) ;
    condiffVals_ = new unsigned int[odwsbd.consze_] ;
    memcpy(condiffVals_,odwsbd.condiffVals_,
           odwsbd.consze_*sizeof(unsigned int)) ; }
  
  return ; }

/*
  Assignment --- for convenience when assigning objects containing
  CoinWarmStartBasisDiff objects.
*/
OsiDylpWarmStartBasisDiff&
OsiDylpWarmStartBasisDiff::operator= (const OsiDylpWarmStartBasisDiff &rhs)

{ if (this != &rhs)
  { CoinWarmStartBasisDiff::operator=(rhs) ;
    if (consze_ > 0)
    { delete[] condiffNdxs_ ;
      delete[] condiffVals_ ; }
    consze_ = rhs.consze_ ;
    if (consze_ > 0)
    { condiffNdxs_ = new unsigned int[consze_] ;
      memcpy(condiffNdxs_,rhs.condiffNdxs_,consze_*sizeof(unsigned int)) ;
      condiffVals_ = new unsigned int[consze_] ;
      memcpy(condiffVals_,rhs.condiffVals_,consze_*sizeof(unsigned int)) ; }
    else
    { condiffNdxs_ = 0 ;
      condiffVals_ = 0 ; } }
  
  return (*this) ; }


#endif // COIN_USE_DYLP

---