[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