Adding row constraints one at a time is slow because of the internal data
structures that simplex solvers use. In large LPs/IPs, the constraint
matrix is almost always sparse, and so allocating an entire dense matrix
doesn't make sense. Instead, a packed sparse matrix is used. Because of
the way the simplex algorithm works, quick access is needed to /columns/ of
the constraint matrix, so the sparse matrix format used is ordered by
columns. When adding a row to such a matrix, the entire matrix needs to be
reordered. As the matrix gets large, this reordering becomes slower.
One solution is to just give the entire matrix to the solver all at once.
In GLPK, this matrix does not have to be column ordered, but it is
reordered before solving (see the glp_sort_matrix command; this doesn't
have to be called explicitly by the user but does get performed). In
CPLEX, the matrix does have to be column ordered, which is somewhat
annoying to do (see CPXcopylp). Gurobi seems to use a similar matrix
format ("Compressed Sparse Column (CSC) format" according to their
documentation). For COIN, a packed sparse matrix is used. The
documentation doesn't seem to explicitly state that it's column ordered,
but I assume it must be.
The up shot of all this is that it's worth thinking about what a nice Sage
interface for large LP/IPs would look like. I think allocating a large
dense matrix doesn't make sense because of the sizes involved. As Peter
pointed out, it's more natural to specify LP/IPs by rows than by columns,
but then a re-ordering must occur at some point.
Best wishes,
Stephen
On Mon, Apr 28, 2014 at 7:49 AM, Nathann Cohen <nathann.co...@gmail.com>wrote:
> Helloooooooooooooooooo !!!
>
>
>> I think this is right. Allocating & copying such a huge matrix repeatedly
>> would be terrible. Perhaps we should introduce an API function to
>> "add_constraints", which takes a list of lists, or a matrix? If a solver
>> doesn't support such a thing, we could fall back on the brute force method.
>>
>
> I am almost sure that all solvers support that. Some "allocate new
> constraints" function that would just be called befre creating the actual
> constraints :-)
>
> Nathann
>
> --
> You received this message because you are subscribed to the Google Groups
> "sage-support" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sage-support+unsubscr...@googlegroups.com.
> To post to this group, send email to sage-support@googlegroups.com.
> Visit this group at http://groups.google.com/group/sage-support.
> For more options, visit https://groups.google.com/d/optout.
>
--
You received this message because you are subscribed to the Google Groups
"sage-support" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-support+unsubscr...@googlegroups.com.
To post to this group, send email to sage-support@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/d/optout.
