Main Page | Class Hierarchy | Alphabetical List | Class List | File List | Class Members | Related Pages

CoinWarmStartBasis Class Reference

The default COIN simplex (basis-oriented) warm start class. More...

#include <CoinWarmStartBasis.hpp>

Inheritance diagram for CoinWarmStartBasis:

CoinWarmStart List of all members.

Public Types

enum  Status { isFree = 0x00, basic = 0x01, atUpperBound = 0x02, atLowerBound = 0x03 }

Public Member Functions

Methods to get and set basis information.
The status of variables is kept in a pair of arrays, one for structural variables, and one for artificials (aka logicals and slacks). The status is coded using the values of the Status enum.

See also:
CoinWarmStartBasis::Status for a description of the packing used in the status arrays.


int getNumStructural () const
 Return the number of structural variables.

int getNumArtificial () const
 Return the number of artificial variables.

int numberBasicStructurals ()
Status getStructStatus (int i) const
 Return the status of the specified structural variable.

void setStructStatus (int i, Status st)
 Set the status of the specified structural variable.

char * getStructuralStatus ()
const char * getStructuralStatus () const
char * getArtificialStatus ()
Status getArtifStatus (int i) const
 Return the status of the specified artificial variable.

void setArtifStatus (int i, Status st)
 Set the status of the specified artificial variable.

const char * getArtificialStatus () const
Basis `diff' methods
virtual CoinWarmStartDiff * generateDiff (const CoinWarmStart *const oldCWS) const
 Generate a `diff' that can convert the warm start basis passed as a parameter to the warm start basis specified by this.

virtual void applyDiff (const CoinWarmStartDiff *const cwsdDiff)
 Apply diff to this basis.

Methods to modify the warm start object
virtual void setSize (int ns, int na)
 Set basis capacity; existing basis is discarded.

virtual void resize (int newNumberRows, int newNumberColumns)
 Set basis capacity; existing basis is maintained.

virtual void deleteRows (int number, const int *which)
 Delete a set of rows from the basis.

virtual void deleteColumns (int number, const int *which)
 Delete a set of columns from the basis.

Constructors, destructors, and related functions
 CoinWarmStartBasis ()
 CoinWarmStartBasis (int ns, int na, const char *sStat, const char *aStat)
 CoinWarmStartBasis (const CoinWarmStartBasis &ws)
virtual CoinWarmStart * clone () const
virtual ~CoinWarmStartBasis ()
virtual CoinWarmStartBasis & operator= (const CoinWarmStartBasis &rhs)
virtual void assignBasisStatus (int ns, int na, char *&sStat, char *&aStat)
Miscellaneous methods
virtual void print () const
 Prints in readable format (for debug).


Private Attributes

Private data members
See also:
CoinWarmStartBasis::Status for a description of the packing used in the status arrays.


int numStructural_
 The number of structural variables.

int numArtificial_
 The number of artificial variables.

char * structuralStatus_
char * artificialStatus_

Related Functions

(Note that these are not member functions.)

CoinWarmStartBasis::Status getStatus (const char *array, int i)
void setStatus (char *array, int i, CoinWarmStartBasis::Status st)

Detailed Description

The default COIN simplex (basis-oriented) warm start class.

CoinWarmStartBasis provides for a warm start object which contains the status of each variable (structural and artificial).

Todo:
Modify this class so that the number of status entries per byte and bytes per status vector allocation unit are not hardcoded. At the least, collect this into a couple of macros.

Consider separate fields for allocated capacity and actual basis size. We could avoid some reallocation, at the price of retaining more space than we need. Perhaps more important, we could do much better sanity checks.

Definition at line 35 of file CoinWarmStartBasis.hpp.

Member Enumeration Documentation

enum CoinWarmStartBasis::Status
 

Status codes for variables

The status vectors are currently packed using two bits per status code, four codes per byte. The location of the status information for variable i is in byte i>>2 and occupies bits 0:1 if i%4 == 0, bits 2:3 if i%4 == 1, etc. The functions getStatus(const char*,int) and setStatus(char*,int,CoinWarmStartBasis::Status) are provided to hide details of the packing.

Enumeration values:
isFree  Nonbasic free variable.
basic  Basic variable.
atUpperBound  Nonbasic at upper bound.
atLowerBound  Nonbasic at lower bound.

Definition at line 48 of file CoinWarmStartBasis.hpp.

Referenced by deleteColumns(), deleteRows(), getArtifStatus(), getStatus(), getStructStatus(), and numberBasicStructurals(). 

00048               {
00049     isFree = 0x00,              
00050     basic = 0x01,               
00051     atUpperBound = 0x02,        
00052     atLowerBound = 0x03         
00053   };

Constructor & Destructor Documentation

CoinWarmStartBasis::CoinWarmStartBasis (   ) 
 

Default constructor

Creates a warm start object representing an empty basis (0 rows, 0 columns).

Definition at line 241 of file CoinWarmStartBasis.cpp.

References artificialStatus_, numArtificial_, numStructural_, and structuralStatus_.

Referenced by clone(). 

00242 {
00243   
00244   numStructural_ = 0;
00245   numArtificial_ = 0;
00246   structuralStatus_ = NULL;
00247   artificialStatus_ = NULL;
00248 }

CoinWarmStartBasis::CoinWarmStartBasis (  int  ns,
int  na,
const char *  sStat,
const char *  aStat
) 
 

Constructs a warm start object with the specified status vectors.

The parameters are copied. Consider assignBasisStatus(int,int,char*&,char*&) if the object should assume ownership.

See also:
CoinWarmStartBasis::Status for a description of the packing used in the status arrays.

Definition at line 44 of file CoinWarmStartBasis.cpp.

References artificialStatus_, and structuralStatus_. 

00045                                                                            :
00046   numStructural_(ns), numArtificial_(na),
00047   structuralStatus_(NULL), artificialStatus_(NULL) {
00048   // Round all so arrays multiple of 4
00049   int nint = (ns+15) >> 4;
00050   structuralStatus_ = new char[4*nint];
00051   structuralStatus_[4*nint-3]=0;
00052   structuralStatus_[4*nint-2]=0;
00053   structuralStatus_[4*nint-1]=0;
00054   memcpy (structuralStatus_, sStat, ((ns + 3) / 4) * sizeof(char));
00055   nint = (na+15) >> 4;
00056   artificialStatus_ = new char[4*nint];
00057   artificialStatus_[4*nint-3]=0;
00058   artificialStatus_[4*nint-2]=0;
00059   artificialStatus_[4*nint-1]=0;
00060   memcpy (artificialStatus_, aStat, ((na + 3) / 4) * sizeof(char));
00061 }

CoinWarmStartBasis::CoinWarmStartBasis (  const CoinWarmStartBasis &  ws  ) 
 

Copy constructor

Definition at line 63 of file CoinWarmStartBasis.cpp.

References artificialStatus_, numArtificial_, numStructural_, and structuralStatus_. 

00063                                                                    :
00064   numStructural_(ws.numStructural_), numArtificial_(ws.numArtificial_),
00065   structuralStatus_(NULL), artificialStatus_(NULL) {
00066   // Round all so arrays multiple of 4
00067   int nint = (numStructural_+15) >> 4;
00068   structuralStatus_ = new char[4*nint];
00069   memcpy (structuralStatus_, ws.structuralStatus_, 
00070           (4*nint) * sizeof(char));
00071   nint = (numArtificial_+15) >> 4;
00072   artificialStatus_ = new char[4*nint];
00073   memcpy (artificialStatus_, ws.artificialStatus_, 
00074           (4*nint) * sizeof(char));
00075 }

CoinWarmStartBasis::~CoinWarmStartBasis (   )  [virtual]
 

Destructor

Definition at line 249 of file CoinWarmStartBasis.cpp.

References artificialStatus_, and structuralStatus_. 

00250 {
00251   delete[] structuralStatus_;
00252   delete[] artificialStatus_;
00253 }

Member Function Documentation

void CoinWarmStartBasis::applyDiff (  const CoinWarmStartDiff *const  cwsdDiff  )  [virtual]
 

Apply diff to this basis.

Update this basis by applying diff. It's assumed that the allocated capacity of the basis is sufficiently large.

Definition at line 367 of file CoinWarmStartBasis.cpp.

References CoinWarmStartBasisDiff::diffNdxs_, CoinWarmStartBasisDiff::diffVals_, getArtificialStatus(), getStructuralStatus(), and CoinWarmStartBasisDiff::sze_. 

00368 {
00369 /*
00370   Make sure we have a CoinWarmStartBasisDiff
00371 */
00372   const CoinWarmStartBasisDiff *diff =
00373     dynamic_cast<const CoinWarmStartBasisDiff *>(cwsdDiff) ;
00374   if (!diff)
00375   { throw CoinError("Diff not derived from CoinWarmStartBasisDiff.",
00376                     "applyDiff","CoinWarmStartBasis") ; }
00377 /*
00378   Application is by straighforward replacement of words in the status arrays.
00379   Index entries for logicals (aka artificials) are tagged with 0x80000000.
00380 */
00381   const int numberChanges = diff->sze_ ;
00382   const unsigned int *diffNdxs = diff->diffNdxs_ ;
00383   const unsigned int *diffVals = diff->diffVals_ ;
00384   unsigned int *structStatus =
00385       reinterpret_cast<unsigned int *>(this->getStructuralStatus()) ;
00386   unsigned int *artifStatus =
00387       reinterpret_cast<unsigned int *>(this->getArtificialStatus()) ;
00388 
00389   for (int i = 0 ; i < numberChanges ; i++)
00390   { unsigned int diffNdx = diffNdxs[i] ;
00391     unsigned int diffVal = diffVals[i] ;
00392     if ((diffNdx&0x80000000) == 0)
00393     { structStatus[diffNdx] = diffVal ; }
00394     else
00395     { artifStatus[diffNdx&0x7fffffff] = diffVal ; } }
00396 
00397   return ; }

void CoinWarmStartBasis::assignBasisStatus (  int  ns,
int  na,
char *&  sStat,
char *&  aStat
)  [virtual]
 

Assign the status vectors to be the warm start information.

In this method the CoinWarmStartBasis object assumes ownership of the pointers and upon return the argument pointers will be NULL. If copying is desirable, use the array constructor or the assignment operator .

Note:
The pointers passed to this method will be freed using delete[], so they must be created using new[].

Definition at line 33 of file CoinWarmStartBasis.cpp.

References artificialStatus_, numArtificial_, numStructural_, and structuralStatus_. 

00034                                                    {
00035   delete[] structuralStatus_;
00036   delete[] artificialStatus_;
00037   numStructural_ = ns;
00038   numArtificial_ = na;
00039   structuralStatus_ = sStat;
00040   artificialStatus_ = aStat;
00041   sStat = NULL;
00042   aStat = NULL;
00043 }

virtual CoinWarmStart* CoinWarmStartBasis::clone (   )  const [inline, virtual]
 

`Virtual constructor'

Implements CoinWarmStart.

Definition at line 221 of file CoinWarmStartBasis.hpp.

References CoinWarmStartBasis(). 

00222   {
00223      return new CoinWarmStartBasis(*this);
00224   }

void CoinWarmStartBasis::deleteColumns (  int  number,
const int *  which
)  [virtual]
 

Delete a set of columns from the basis.

Warning:
The resulting basis is guaranteed valid only if all deleted variables are nonbasic.
Removal of a basic variable implies that some nonbasic variable must be made basic. This correction is left to the client.

Definition at line 179 of file CoinWarmStartBasis.cpp.

References basic, getStructStatus(), numStructural_, setStatus(), Status, and structuralStatus_. 

00180 {
00181   int i ;
00182   char * deleted = new char[numStructural_];
00183   int numberDeleted=0;
00184   memset(deleted,0,numStructural_*sizeof(char));
00185   for (i=0;i<number;i++) {
00186     int j = which[i];
00187     if (j>=0&&j<numStructural_&&!deleted[j]) {
00188       numberDeleted++;
00189       deleted[j]=1;
00190     }
00191   }
00192   int nCharNew  = 4*((numStructural_-numberDeleted+15)>>4);
00193   char * array = new char[nCharNew];
00194   // Make sure okay for zerofault etc
00195   array[nCharNew-3]=0;
00196   array[nCharNew-2]=0;
00197   array[nCharNew-1]=0;
00198   int put=0;
00199 # ifdef COIN_DEBUG
00200   int numberBasic=0;
00201 # endif
00202   for (i=0;i<numStructural_;i++) {
00203     Status status = getStructStatus(i);
00204     if (!deleted[i]) {
00205       setStatus(array,put,status) ;
00206       put++; }
00207 #   ifdef COIN_DEBUG
00208     else
00209     if (status==CoinWarmStartBasis::basic)
00210     { numberBasic++ ; }
00211 #   endif
00212   }
00213   delete [] structuralStatus_;
00214   structuralStatus_ = array;
00215   delete [] deleted;
00216   numStructural_ -= numberDeleted;
00217 #ifdef COIN_DEBUG
00218   if (numberBasic)
00219     std::cout<<numberBasic<<" basic structurals deleted"<<std::endl;
00220 #endif
00221 }

void CoinWarmStartBasis::deleteRows (  int  number,
const int *  which
)  [virtual]
 

Delete a set of rows from the basis.

Warning:
The resulting basis is guaranteed valid only if all deleted constraints are slack (hence the associated logicals are basic).
Removal of a tight constraint with a nonbasic logical implies that some basic variable must be made nonbasic. This correction is left to the client.

Definition at line 133 of file CoinWarmStartBasis.cpp.

References artificialStatus_, basic, getArtifStatus(), numArtificial_, setStatus(), and Status. 

00134 {
00135   int i ;
00136   char * deleted = new char[numArtificial_];
00137   int numberDeleted=0;
00138   memset(deleted,0,numArtificial_*sizeof(char));
00139   for (i=0;i<number;i++) {
00140     int j = which[i];
00141     if (j>=0&&j<numArtificial_&&!deleted[j]) {
00142       numberDeleted++;
00143       deleted[j]=1;
00144     }
00145   }
00146   int nCharNew  = 4*((numArtificial_-numberDeleted+15)>>4);
00147   char * array = new char[nCharNew];
00148   // Make sure okay for zerofault etc
00149   array[nCharNew-3]=0;
00150   array[nCharNew-2]=0;
00151   array[nCharNew-1]=0;
00152   int put=0;
00153 # ifdef COIN_DEBUG
00154   int numberNotBasic=0;
00155 # endif
00156   for (i=0;i<numArtificial_;i++) {
00157     Status status = getArtifStatus(i);
00158     if (!deleted[i]) {
00159       setStatus(array,put,status) ;
00160       put++; }
00161 #   ifdef COIN_DEBUG
00162     else
00163     if (status!=CoinWarmStartBasis::basic)
00164     { numberNotBasic++ ; }
00165 #   endif
00166   }
00167   delete [] artificialStatus_;
00168   artificialStatus_ = array;
00169   delete [] deleted;
00170   numArtificial_ -= numberDeleted;
00171 # ifdef COIN_DEBUG
00172   if (numberNotBasic)
00173     std::cout<<numberNotBasic<<" non basic artificials deleted"<<std::endl;
00174 # endif
00175 }

CoinWarmStartDiff * CoinWarmStartBasis::generateDiff (  const CoinWarmStart *const  oldCWS  )  const [virtual]
 

Generate a `diff' that can convert the warm start basis passed as a parameter to the warm start basis specified by this.

The capabilities are limited: the basis passed as a parameter can be no larger than the basis pointed to by this.

Definition at line 279 of file CoinWarmStartBasis.cpp.

References getArtificialStatus(), getNumArtificial(), getNumStructural(), and getStructuralStatus(). 

00280 { 
00281 /*
00282   Make sure the parameter is CoinWarmStartBasis or derived class.
00283 */
00284   const CoinWarmStartBasis *oldBasis =
00285       dynamic_cast<const CoinWarmStartBasis *>(oldCWS) ;
00286   if (!oldBasis)
00287   { throw CoinError("Old basis not derived from CoinWarmStartBasis.",
00288                     "generateDiff","CoinWarmStartBasis") ; }
00289   const CoinWarmStartBasis *newBasis = this ;
00290 /*
00291   Make sure newBasis is equal or bigger than oldBasis. Calculate the worst case
00292   number of diffs and allocate vectors to hold them.
00293 */
00294   const int oldArtifCnt = oldBasis->getNumArtificial() ;
00295   const int oldStructCnt = oldBasis->getNumStructural() ;
00296   const int newArtifCnt = newBasis->getNumArtificial() ;
00297   const int newStructCnt = newBasis->getNumStructural() ;
00298 
00299   assert(newArtifCnt >= oldArtifCnt) ;
00300   assert(newStructCnt >= oldStructCnt) ;
00301 
00302   int sizeOldArtif = (oldArtifCnt+15)>>4 ;
00303   int sizeNewArtif = (newArtifCnt+15)>>4 ;
00304   int sizeOldStruct = (oldStructCnt+15)>>4 ;
00305   int sizeNewStruct = (newStructCnt+15)>>4 ;
00306   int maxBasisLength = sizeNewArtif+sizeNewStruct ;
00307 
00308   unsigned int *diffNdx = new unsigned int [maxBasisLength]; 
00309   unsigned int *diffVal = new unsigned int [maxBasisLength]; 
00310 /*
00311   Ok, setup's over. Now scan the logicals (aka artificials, standing in for
00312   constraints). For the portion of the status arrays which overlap, create
00313   diffs. Then add any additional status from newBasis.
00314 
00315   I removed the following bit of code & comment:
00316 
00317     if (sizeNew == sizeOld) sizeOld--; // make sure all taken
00318 
00319   I assume this is meant to trap cases where oldBasis does not occupy all of
00320   the final int, but I can't see where it's necessary.
00321 */
00322   const unsigned int *oldStatus =
00323       reinterpret_cast<const unsigned int *>(oldBasis->getArtificialStatus()) ;
00324   const unsigned int *newStatus = 
00325       reinterpret_cast<const unsigned int *>(newBasis->getArtificialStatus()) ;
00326   int numberChanged = 0 ;
00327   int i ;
00328   for (i = 0 ; i < sizeOldArtif ; i++)
00329   { if (oldStatus[i] != newStatus[i])
00330     { diffNdx[numberChanged] = i|0x80000000 ;
00331       diffVal[numberChanged++] = newStatus[i] ; } }
00332   for ( ; i < sizeNewArtif ; i++)
00333   { diffNdx[numberChanged] = i|0x80000000 ;
00334     diffVal[numberChanged++] = newStatus[i] ; }
00335 /*
00336   Repeat for structural variables.
00337 */
00338   oldStatus =
00339       reinterpret_cast<const unsigned int *>(oldBasis->getStructuralStatus()) ;
00340   newStatus =
00341       reinterpret_cast<const unsigned int *>(newBasis->getStructuralStatus()) ;
00342   for (i = 0 ; i < sizeOldStruct ; i++)
00343   { if (oldStatus[i] != newStatus[i])
00344     { diffNdx[numberChanged] = i ;
00345       diffVal[numberChanged++] = newStatus[i] ; } }
00346   for ( ; i < sizeNewStruct ; i++)
00347   { diffNdx[numberChanged] = i ;
00348     diffVal[numberChanged++] = newStatus[i] ; }
00349 /*
00350   Create the object of our desire.
00351 */
00352   CoinWarmStartBasisDiff *diff =
00353     new CoinWarmStartBasisDiff(numberChanged,diffNdx,diffVal) ;
00354 /*
00355   Clean up and return.
00356 */
00357   delete[] diffNdx ;
00358   delete[] diffVal ;
00359 
00360   return (dynamic_cast<CoinWarmStartDiff *>(diff)) ; }

const char* CoinWarmStartBasis::getArtificialStatus (   )  const [inline]
 

const overload for getArtificialStatus()

Definition at line 129 of file CoinWarmStartBasis.hpp.

References artificialStatus_. 

00129 { return artificialStatus_; }

char* CoinWarmStartBasis::getArtificialStatus (   )  [inline]
 

As for getStructuralStatus , but returns the status array for the artificial variables.

Definition at line 109 of file CoinWarmStartBasis.hpp.

References artificialStatus_.

Referenced by applyDiff(), and generateDiff(). 

00109 { return artificialStatus_; }

const char* CoinWarmStartBasis::getStructuralStatus (   )  const [inline]
 

const overload for getStructuralStatus()

Definition at line 104 of file CoinWarmStartBasis.hpp.

References structuralStatus_. 

00104 { return structuralStatus_; }

char* CoinWarmStartBasis::getStructuralStatus (   )  [inline]
 

Return the status array for the structural variables

The status information is stored using the codes defined in the Status enum, 2 bits per variable, packed 4 variables per byte.

Definition at line 97 of file CoinWarmStartBasis.hpp.

References structuralStatus_.

Referenced by applyDiff(), and generateDiff(). 

00097 { return structuralStatus_; }

int CoinWarmStartBasis::numberBasicStructurals (   ) 
 

Return the number of basic structurals

A fast test for an all-slack basis.

Definition at line 256 of file CoinWarmStartBasis.cpp.

References basic, getStructStatus(), numStructural_, and Status. 

00257 {
00258   int i ;
00259   int numberBasic=0;
00260   for (i=0;i<numStructural_;i++) {
00261     Status status = getStructStatus(i);
00262     if (status==CoinWarmStartBasis::basic) 
00263       numberBasic++;
00264   }
00265   return numberBasic;
00266 }

CoinWarmStartBasis & CoinWarmStartBasis::operator= (  const CoinWarmStartBasis &  rhs  )  [virtual]
 

Assignment

Definition at line 78 of file CoinWarmStartBasis.cpp.

References artificialStatus_, numArtificial_, numStructural_, and structuralStatus_. 

00079 {
00080   if (this != &rhs) {
00081     numStructural_=rhs.numStructural_;
00082     numArtificial_=rhs.numArtificial_;
00083     delete [] structuralStatus_;
00084     delete [] artificialStatus_;
00085     // Round all so arrays multiple of 4
00086     int nint = (numStructural_+15) >> 4;
00087     structuralStatus_ = new char[4*nint];
00088     memcpy (structuralStatus_, rhs.structuralStatus_, 
00089             (4*nint) * sizeof(char));
00090     nint = (numArtificial_+15) >> 4;
00091     artificialStatus_ = new char[4*nint];
00092     memcpy (artificialStatus_, rhs.artificialStatus_, 
00093           (4*nint) * sizeof(char));
00094   }
00095   return *this;
00096 }

Friends And Related Function Documentation

CoinWarmStartBasis::Status getStatus (  const char *  array,
int  i
)  [related]
 

Get the status of the specified variable in the given status array.

Definition at line 282 of file CoinWarmStartBasis.hpp.

References Status. 

00282                                                                      {
00283   const int st = (array[i>>2] >> ((i&3)<<1)) & 3;
00284   return static_cast<CoinWarmStartBasis::Status>(st);
00285 }

void setStatus (  char *  array,
int  i,
CoinWarmStartBasis::Status  st
)  [related]
 

Set the status of the specified variable in the given status array.

Definition at line 291 of file CoinWarmStartBasis.hpp.

Referenced by deleteColumns(), and deleteRows(). 

00291                                                                         {
00292   char& st_byte = array[i>>2];
00293   st_byte &= ~(3 << ((i&3)<<1));
00294   st_byte |= (st << ((i&3)<<1));
00295 }

Member Data Documentation

char* CoinWarmStartBasis::artificialStatus_ [private]
 

The status of the artificial variables.

Definition at line 273 of file CoinWarmStartBasis.hpp.

Referenced by assignBasisStatus(), CoinWarmStartBasis(), deleteRows(), getArtificialStatus(), getArtifStatus(), operator=(), resize(), setArtifStatus(), setSize(), and ~CoinWarmStartBasis().

char* CoinWarmStartBasis::structuralStatus_ [private]
 

The status of the structural variables.

Definition at line 271 of file CoinWarmStartBasis.hpp.

Referenced by assignBasisStatus(), CoinWarmStartBasis(), deleteColumns(), getStructStatus(), getStructuralStatus(), operator=(), resize(), setSize(), setStructStatus(), and ~CoinWarmStartBasis().

The documentation for this class was generated from the following files:
Generated on Wed Dec 3 14:34:30 2003 for Coin by doxygen 1.3.5