Re: Multicore LP solvers

A google scholar search turns up several papers on parallel interior point methods.

>     On 03/27/2021 9:16 AM Reginald Beardsley <[email protected]> wrote:
>      
>      
>     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 littl
 e 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 <[email protected]> wrote:
>        
>        
>       Hello Reginald !
> 
>       Have looked at https://github.com/ERGO-Code/HiGHS 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
>       >
> 
>