Hello,
I don't know is this group adequate for this
post(sorry).
I want to implement simplex with low filled
filds matrix (in LISP lists).
I think that werion in LISP is more faster
than C implementation.So if anybody is
interesed in this please e-mail me.
Thanks in advance,
Robert
·············@si.htnet.hr
"Bralic Robert" <·············@si.htnet.hr> writes:
> I don't know is this group adequate for this
> post(sorry).
> I want to implement simplex with low filled
> filds matrix (in LISP lists).
> I think that werion in LISP is more faster
> than C implementation.So if anybody is
> interesed in this please e-mail me.
Bruno Haible's simplex implementation¹ may serve as a starting point.
(It takes its input as arrays, not lists, though.)
Vebjorn
¹ http://www-cgi.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/lisp/code/math/simplex/0.htm
Vebjorn Ljosa wrote:
> http://www-cgi.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/lisp/code/math/simplex/0.htm
It is now at
http://www-2.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/lisp/code/math/simplex/0.html
In article <············@ls219.htnet.hr>,
"Bralic Robert" <·············@si.htnet.hr> wrote:
> I don't know is this group adequate for this
> post(sorry).
> I want to implement simplex with low filled
> filds matrix (in LISP lists).
Do you mean Dantzig's simplex algorithm for solving linear
programming problems or the (unrelated) simplex algorithm
for fitting functions?
"Sashank Varma" <····@vanderbilt.edu> wrote in message
·······························@news.vanderbilt.edu...
> In article <············@ls219.htnet.hr>,
> "Bralic Robert" <·············@si.htnet.hr> wrote:
>
> > I don't know is this group adequate for this
> > post(sorry).
> > I want to implement simplex with low filled
> > filds matrix (in LISP lists).
>
> Do you mean Dantzig's simplex algorithm for solving linear
> programming problems or the (unrelated) simplex algorithm
> for fitting functions?
I mean normal Danzig's simplex but with
low filed matricxs.
Robert,
·············@si.tel.hr
"Bralic Robert" <·············@si.htnet.hr> wrote in message news:<············@ls219.htnet.hr>...
> I mean normal Danzig's simplex but with
> low filed matricxs.
Does "low filled" mean sparse matrices?
Does Haible's code handle sparse matrices?
In article <····························@posting.google.com>,
···············@yahoo.com (Mark McConnell) wrote:
> "Bralic Robert" <·············@si.htnet.hr> wrote in message
> news:<············@ls219.htnet.hr>...
> > I mean normal Danzig's simplex but with
> > low filed matricxs.
>
> Does "low filled" mean sparse matrices?
>
> Does Haible's code handle sparse matrices?
I don't know the technical definition of "sparse"
but I've used his code for years for years on
relatively modest problems (fewer than 100
constraints and fewer than 500 variables) and
never had a problem.
However, it is quite hard to read and I've never
had much success modifying it.
Sashank
Sashank Varma <····@vanderbilt.edu> wrote in message news:<··························@news.vanderbilt.edu>...
> In article <····························@posting.google.com>,
> ···············@yahoo.com (Mark McConnell) wrote:
>
> > "Bralic Robert" <·············@si.htnet.hr> wrote in message
> > news:<············@ls219.htnet.hr>...
> > > I mean normal Danzig's simplex but with
> > > low filed matricxs.
> >
> > Does "low filled" mean sparse matrices?
> >
> > Does Haible's code handle sparse matrices?
>
> I don't know the technical definition of "sparse"
> but I've used his code for years for years on
> relatively modest problems (fewer than 100
> constraints and fewer than 500 variables) and
> never had a problem.
"Sparse" means most of the matrix entries are zero. For instance,
maybe only 0.1% of the entries are non-zero. You'd code things
specially to store only the non-zeros and, more important, to help
keep the matrix from filling in with non-zeros as the computation
progresses.
In article <····························@posting.google.com>,
···············@yahoo.com (Mark McConnell) wrote:
> Sashank Varma <····@vanderbilt.edu> wrote in message
[...]
> > I don't know the technical definition of "sparse"
> > but I've used his code for years for years on
> > relatively modest problems (fewer than 100
> > constraints and fewer than 500 variables) and
> > never had a problem.
>
> "Sparse" means most of the matrix entries are zero. For instance,
> maybe only 0.1% of the entries are non-zero. You'd code things
> specially to store only the non-zeros and, more important, to help
> keep the matrix from filling in with non-zeros as the computation
> progresses.
Sorry for being so cryptic. Here's the decision logic
I'd recommend:
Grab Haible's code and try it on a problem of the size
and sparseness you need to solve. If it works, and works
rapidly, you're set.
Haible's code uses conventional matrices. It might be
that your typical problem when represented in this
ways exceeds your machines memory. If buying more
memory would solve the problem, then buy it.
If your problem exceeds the array size limitations of
your lisp implementation, try another implementation.
If no capable implementation exists for your OS/machine,
then implement a sparse array data structure (or better
yet, use someone else's implementation). Haible's code
uses only simple arrays and standard operations on them
(if my memory is correct) so you may be able to get away
with mechanically modifying it to accept your sparse
arrays.
How's it going?
I'm not sure how much time you want to spend on this. The easiest
solution is to use Bruno Haible's implementation. But, if your lisp
implementation allows you to call C programs and make use of the
result, you may also want to do that.. This would make sense if
you're used to using something like Ilog's CPLEX for your work.
Just because you're programming in lisp doesn't mean everything has to
be in lisp. Here's a link for a C simplex implementations.
http://www.sor.princeton.edu/~rvdb/LPbook/src/index.html
In LispWork's (for example), information about how to build a C
interface is in the Foreign Function Interface manual.
Rand
(please don't send me email, I'm running a spam experiment).