Re: [Help-glpk] glpk parallel

[Michael Hennebry]

On Sun, 23 May 2004, Gleb Beliakov wrote:

> Are there any plans to implement a parallel version of glpk
> (Especially LP - simplex and interior point methods),
> using Message Passing interface (MPI) standard?
> I would like to solve problems with 20-100 million constraints (very sparse
> matrix though), and
> >10000 variables.

You might be able to do it now if you have enough memory
and your matrix is sparse enough.
Even without 4 G of virtual memory, basic solutions only
need at most one constraint per variable.

Pick a subset of the constraints.

Solve to optimality.
If no constraint is violated, you're done.
Add one or more violated constraints.
Drop any constraints with positive slacks.
Go back to solve.


Dealing with an unbounded objective is left as an exercise for the reader.

-- 
Mike   address@hidden
"Nothing says it like words if you know how to use them."
                    --  the Professional Organization of English Majors