[Coin-lpsolver] Constraint matrix

John J Forrest jjforre at us.ibm.com
Tue Mar 8 12:28:58 EST 2005


Kyle,

I will write a constructor for you.  If you still need more memory there 
are a few more tricks e.g.  replaceMatrix may not need two copies and you 
can switch off a row copy (but it will be slower).

May be ready by tomorrow.

John Forrest



Kyle Ellrott <kellrott at csbl.bmb.uga.edu> 
Sent by: coin-lpsolver-bounces at list.coin-or.org
03/08/2005 11:39 AM

To
coin-lpsolver at list.coin-or.org
cc

Subject
Re: [Coin-lpsolver] Constraint matrix






I've been playing around with the ClpSimplex solver directly as 
suggested.  Upon further research, given the nature of my problem, I 
may want to skip the Branch and Bound interface altogether (my 
branches, which rarely exist, are binary in nature, so no need for a 
linear cutting plane)
Currently I'm trying to tackle a problem with a size of 10861552 
Column, 103481 rows, and 21788000 elements, but as mentioned before 
there only exists the values +1,0,-1, so using a ClpPlusMinusOneMatrix 
is preferable.
Anyway, I'm still playing around with quickly constructing a large 
ClpPlusMinusOneMatrix.  Originally, when I used the CoinPackedMatrix, I 
utilized the triplet array description of the matrix to initialize 
(row, column, element) to initialize the structure.  But because this 
interface is not part of the ClpPlusMinusOneMatrix class, I rewrote my 
code to generate the matrix one column at a time, and attempt to use 
the appendCol call in ClpPlusMinusOneMatrix.  At this point I found 
out, this might not work,
 From the looks of the source code, and 
http://www.coin-or.org/Clp/userguide/ch03s02.html it looks as if the 
only way to initialize a ClpPlusMinusOneMatrix is to first create a 
ClpPackedMatrix, and then initialize the PlusMinus matrix by passing in 
the PackedMatrix.
But currently I run out of memory creating the ClpPackedMatrix on 
certain problems, so I can't even create the PlusMinus matrix.

The problem is that ClpPackedMatrix creation is a bit of a memory hog, 
because at it's worst point I have two copies of the matrix in memory 
at one time  (one in the linked list of CoinBuild, and on in the matrix 
inside of ClpSimplex), or I could try building the matrix one column at 
a time, but that takes way to much time.  The triplet method is a bit 
better, because it removes a bit of memory overhead associated in 
describing each of the columns separately, but PlusMinus doesn't take a 
CoinPackedMatrix as a constructor argument.  But even then, I still use 
a lot of memory creating a PackedMatrix before creating the smaller 
PlusMinus one.

Is it possible to create a ClpPlusMinusOneMatrix without creating a 
ClpPackedMatrix first?

I think the following call might be the way to go, but the 
documentation is kind of sparse in terms of how to use it...

  ClpPlusMinusOneMatrix::ClpPlusMinusOneMatrix                   (  int   
numberRows,
                                 int             numberColumns,
                                 bool            columnOrdered,
                                 const int *             indices,
                                 const CoinBigIndex * startPositive,
                                 const CoinBigIndex * startNegative
                 ) 


Kyle



>
> Kyle,
>
> While Cbc i.e. Osi could allow more types of matrices I am not sure it 
> is a good idea for Branch and Cut.  A bit of extra storage before 
> entering branch and cut  is the least of your worries.  In branch and 
> cut the cut generators all expect a CoinPackedMatrix and if they add 
> any cuts they will destroy any special structure.
>
> If you are masochistic enough to want to try and stress the code you 
> could do the following:
>
> Get an OsiClpSolverInterface solver
> get a ClpSimplex pointer using getModelPtr()
> create model and pass in +-1 matrix - you can get clues from 
> Clp/Test/unitTest.cpp
> pass solver to Cbc
>
> It will do the initial solve.  If it does not add cuts it should stay 
> as +- matrix.  If it does cuts it "should" magically become an 
> ordinary matrix - if it fails then I will fix.
>
> John Forrest
>
>
>
>
> Kyle Ellrott <kellrott at csbl.bmb.uga.edu>
>
> Sent by: coin-lpsolver-bounces at list.coin-or.org
>
>
> 03/03/2005 11:09 AM
>
>
> To
>
> coin-lpsolver at list.coin-or.org
>
>
> cc
>
>
> Subject
>
> Re: [Coin-lpsolver] Constraint matrix
>
>
>
>
>
>
>
>
> I've been looking through the source tree to get a better understanding
>  of what's going on.  But I do have a few questions.
>  From my understanding CoinPackedMatrix is derived from 
> ClpPackedMatrix,
>  and adds a few functions (actually It looks like it adds about 38 
> pages
>  worth of code to ClpPackMatrix).  Do all those functions need to be
>  added before Cbc can utilize the matrix?
>
>  There is no equivalent Coin class for the ClpPlusMinusOneMatrix.  I'm
>  assuming one would have to be created before it could be used in the
>  CbcModel interface.  Of course I would also have to add a loadProblem
>  method to Cbc that used this hypothetical CoinPlusMinusOneMatrix. 
>  Then
>  maybe change the internal Cbc matrix pointers is a more generic
>  CoinMatrixBase (which doesn't exist either) which would be an abstract
>  based on ClpMatrixBase, rather then the current CoinPackedMatrix.
>
>  Is this what it would take to get a plus/minus one matrix working in
>  Cbc?  Or have I over complicated the problem?
>
>  Kyle
>
>
>
>  > Thank you, that helps ;-)
>  >
>  > But I do have one problem.  According the page mentioned, both
>  > ClpPlusMinusOneMatrix and ClpPackedMatrix both inherit from
>  > ClpMatrixBase.  The problem is that OsiClpSolverInterface's
>  > loadProblem only mentions CoinPackedMatrix (which I think is the 
> same
>  > as ClpPackedMatrix), but not the parent class of ClpMatrixBase.  So
>  > when I try to pass a ClpPlusMinusOneMatrix to 
> OsiClpSolverInterface's
>  > loadProblem, I get something like
>  >
>  > intpro_threading.cc:766: error: no matching function for call to `
>  >    OsiClpSolverInterface::loadProblem(ClpPlusMinusOneMatrix&, 
> double*&,
>  >    double*&, double*&, double*&, double*&)'
>  > /Users/kye/COIN/include/OsiClpSolverInterface.hpp:600: error:
>  > candidates are:
>  >    virtual void OsiClpSolverInterface::loadProblem(const
>  > CoinPackedMatrix&,
>  >    const double*, const double*, const double*, const double*, const
>  > double*)
>  >
>  > Any thoughts?
>  >
>  > Kyle
>  >
>  >
>  >
>  >> I think you will find this page of the CLP documentation will help
>  >> you:
>  >>
>  >> http://www.coin-or.org/Clp/userguide/ch03s02.html
>  >>
>  >> In other words, there's (supposed to be) a matrix class specific to
>  >> your situation.
>  >>
>  >> At 02:38 PM 3/2/2005, Kyle Ellrott wrote:
>  >>> I'm curious about the CoinPackedMatrix structure that I use to 
> setup
>  >>> my constraint matrix for my integer programming problem.  From 
> what
>  >>> I understand so far, it's input data is doubles.  But for my
>  >>> particular problem, the only values I put in it are -1, 1, and 0 
> (0
>  >>> being being cells that aren't mentioned in my description).  By
>  >>> using a double rather then a char, I'm using 8 time more memory 
> then
>  >>> I need to.
>  >>> Is there are more efficient method to describe this matrix?
>  >>>
>  >>> Kyle
>  >>>
>  >>> _______________________________________________
>  >>> Coin-lpsolver mailing list
>  >>> Coin-lpsolver at list.coin-or.org
>  >>> http://list.coin-or.org/mailman/listinfo/coin-lpsolver
>  >>
>  >
>  > _______________________________________________
>  > Coin-lpsolver mailing list
>  > Coin-lpsolver at list.coin-or.org
>  > http://list.coin-or.org/mailman/listinfo/coin-lpsolver
>
>  _______________________________________________
>  Coin-lpsolver mailing list
>  Coin-lpsolver at list.coin-or.org
>  http://list.coin-or.org/mailman/listinfo/coin-lpsolver
>
> _______________________________________________
> Coin-lpsolver mailing list
> Coin-lpsolver at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/coin-lpsolver
  _______________________________________________
Coin-lpsolver mailing list
Coin-lpsolver at list.coin-or.org
http://list.coin-or.org/mailman/listinfo/coin-lpsolver

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/clp/attachments/20050308/d6b73303/attachment.html>


More information about the Clp mailing list