Re: Multicore LP solvers

[Reginald Beardsley]

Thank you. I'd not seen that, however, my question is really more literature oriented at the moment. A quick look at the presentation on the page reveals that it has all the issues that limit the simplex method in general.

With apologies for my lexical abuses to those who are better mathematicians than I:

For instances of Ax=y where x is sparse, i.e. has few non-zero elements, there is an identity that spans a large number of problems in a wide variety of mathematical disciplines ranging from linear algebra to computational geometry and graph theory.

This paper by David Donoho:

https://statistics.stanford.edu/sites/g/files/sbiybj6031/f/2005-04.pdf

along with this:

https://statistics.stanford.edu/sites/g/files/sbiybj6031/f/2004-09.pdf

is the motivation for my quest. The 2nd paper I regard as the single most important paper in applied mathematics since Norbert Wiener's "yellow peril". Working in reflection seismic research I often encountered practical problems from computational geometry, many of which are NP hard. For obvious reasons, I feared those greatly. So much so that when some new problem was presented to me, my first question was, "Is it NP?"

Donoho's 2004-09 is the single instance of which I am aware of a solution in tractable time of a problem which is NP hard at first glance. His 2005-04 hints at the possibility of a trivially parallel solution via computational geometry, graph theory or some homomorph of those. I saw a little twinkle when I was using GLPK to solve inverse problems based on the heat equation using basis pursuit. One day I realized I was solving problems I'd been taught could not be solved as Donoho discusses in the introduction to 2004-09. That led me on a 3 year journey through some 3000 pages of mathematics which eventually reached Grunbaum's monograph on regular polytopes in N-dimensional space. Rather a long journey for someone with a BA in English lit. The systems on ebay reminded me of that little twinkle.

Having read this list for many years now, it is the only place I can think of to ask about such things.

Have Fun!
Reg

On Saturday, March 27, 2021, 02:52:43 AM CDT, Domingo Alvarez Duarte <mingodad@gmail.com> wrote:

Hello Reginald !

Have looked at https://github.com/ERGO-Code/HiGHS they seem to be doing
a parallel LP solver.

Cheers !

On 26/3/21 21:26, Reginald Beardsley wrote:
> I haven't fooled around with GLPK and LP problems in general for several years now.
>
> The appearance of off lease machines with 28+ cores, 256 GB of RAM for almost nothing has me wondering what the general state of the art is in parallelizable algorithms for solving LP and related problems.
>
> I have "Computational Techniques of the Simplex Method" by Istvan Maros.  Unfortunately, the simplex method is not very amenable to multicore solution.
>
> My attempt to locate recent work via google scholar was not very productive, so I thought I'd ask here.  Can anyone suggest recent papers or books germane to the topic?  The little I did find was rather old.
>
> Thanks,
> Reg
>