[Coin-lpsolver] Re: [Coin-discuss] Open Source Simplex solver?

[John J Forrest]

Antonio,

>Great. Do you want me to give a look at the code and comment it further
>(assuming I have any other comments)? Where can I download it from?

At present you can not download it from anywhere as IBM bureaucracy is
going very slowly.  However I can describe the ClpMatrixBase class and ask
for comments.  I include parts of the OsiPackedMatrix header file.

**** However I suspect that it may not be as readable as I would like as it
will be re-formatted

Some functions have the ClpSimplex model passed in so scaling can be
applied or tolerances used.  These are
mostly simplex specific calls.

This is an abstract class and it bears a strong resemblance to a subset of
OsiPackedMatrix. So it has:

    /** Whether the packed matrix is column major ordered or not. */
  virtual bool isColOrdered() const = 0;
   /** Number of entries in the packed matrix. */
  virtual int getNumElements() const = 0;
   /** Number of columns. */
  virtual int getNumCols() const = 0;
   /** Number of rows. */
  virtual int getNumRows() const = 0;


XX John Forrest - the next section is not used at all in my simplex
       code but may be useful for compatibility.

   /** A vector containing the elements in the packed matrix.
      Note that there might be gaps in this list, entries that do not
       belong to any major-dimension vector. To get the actual elements
       one should look at this vector together with vectorStarts and vectorLengths. */
   virtual const double * getElements() const = 0;
   /** A vector containing the minor indices of the elements in the packed
        matrix. Note that there might be gaps in this list, entries that do not
        belong to any major-dimension vector. To get the actual elements one
        should look at this vector together with vectorStarts and
        vectorLengths. */
   virtual const int * getIndices() const = 0;

   virtual const int * getVectorStarts() const = 0;
   /** The lengths of the major-dimension vectors. */
   virtual const int * getVectorLengths() const = 0 ;

XX John Forrest - these two are new - the releasePackedMatrix would
      also apply to any temporary data created by getElements etc

   /// Return a complete OsiPackedMatrix
   virtual OsiPackedMatrix * getPackedMatrix() const = 0;
   /// Allow any parts of a created OsiPackedMatrix to be deleted
   virtual void releasePackedMatrix() const {};

XX John Forrest - We do need deleteRows and deleteCols so the Osi Clp
      interface can be used by BCP etc

   /** Delete the columns whose indices are listed in <code>indDel</code>. */
    virtual void deleteCols(const int numDel, const int * indDel) = 0;
    /** Delete the rows whose indices are listed in <code>indDel</code>. */
    virtual void deleteRows(const int numDel, const int * indDel) = 0;

XX John Forrest - for speed I want a row copy of matrix but the
      default says we don't use so the default just returns null

  /** Returns a new matrix in reverse order without gaps
      Is allowed to return NULL if doesn't want to have row copy */
  virtual ClpMatrixBase * reverseOrderedCopy() const {return NULL;};

XX John Forrest - simplex needs to be able to create a basis to be
      factorized so the first says how much memory will be needed
      and second fills in memory

  /** Returns number of elements in basis
      column is basic if entry >=0 */
  virtual OsiBigIndex numberInBasis(const int * columnIsBasic) const = 0;
  /// Fills in basis (Returns number of elements and updates numberBasic)
  virtual OsiBigIndex fillBasis(const ClpSimplex * model,
                        const int * columnIsBasic, int & numberBasic,
                        int * row, int * column,
                        double * element) const = 0;

XX John Forrest - simplex may do a lot better if problem scaled.
      We don't actually modify column copy - just compute scales.
      non-zero can be returned if you don't want to scale

  /** Creates scales for column copy (rowCopy in model may be modified)
      default does not allow scaling
      returns non-zero if no scaling done */
  virtual int scale(ClpSimplex * model) const
  { return 1;};

XX John Forrest - Simplex needs to be able to get a column of matrix
      (scaled) and add in columns

  /** Unpacks a column into an OsiIndexedvector
      Note that model is NOT const.  Bounds and objective could
      be modified if doing column generation */
  virtual void unpack(ClpSimplex * model,OsiIndexedVector * rowArray,
               int column) const =0;
  /** Adds multiple of a column into an OsiIndexedvector
      You can use quickAdd to add to vector */
  virtual void add(const ClpSimplex * model,OsiIndexedVector * rowArray,
               int column, double multiplier) const =0;

XX John Forrest - The functions without ClpSimplex are basically the
      same as in OsiPackedMatrix
      The one with ClpSimplex needs to know a bit more about tolerances etc

  //---------------------------------------------------------------------------
  /**@name Matrix times vector methods
     They can be faster if scalar is +- 1
     Also for simplex I am not using basic/non-basic split */
  //@{
    /** Return <code>y + A * x * scalar</code> in <code>y</code>.
        @precond <code>x<code> must be of size <code>numColumns()</code>
        @precond <code>y<code> must be of size <code>numRows()</code> */
  virtual void times(double scalar,
                   const double * x, double * y) const=0;
  /// And for scaling - default aborts for when scaling not supported
  virtual void times(double scalar,
                 const double * x, double * y,
                 const double * rowScale,
                 const double * columnScale) const;
    /** Return <code>y + x * scalar * A</code> in <code>y</code>.
        @precond <code>x<code> must be of size <code>numRows()</code>
        @precond <code>y<code> must be of size <code>numColumns()</code> */
    virtual void transposeTimes(double scalar,
                        const double * x, double * y) const = 0;
  /// And for scaling - default aborts for when scaling not supported
    virtual void transposeTimes(double scalar,
                        const double * x, double * y,
                        const double * rowScale,
                        const double * columnScale) const;
    /** Return <code>x * scalar *A + y</code> in <code>z</code>.
      Can use y as temporary array (will be empty at end)
      Squashes small elements and knows about ClpSimplex */
  virtual void transposeTimes(const ClpSimplex * model, double scalar,
                        const OsiIndexedVector * x,
                        OsiIndexedVector * y,
                        OsiIndexedVector * z) const = 0;

XX John Forrest - we have some constructors etc plus clone

   virtual ClpMatrixBase * clone() const = 0;