Math Sparse Linear Programing -- Math Commons

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Math Sparse Linear Programing -- Math Commons

Bill Igoe
Hi Gang,

I recently alter the code for both SimplexSolver and SimplexTableau to use
the OpenMapRealMatrix object rather than the Array2DRowRealMatrix.  Most
large Linear Programming programming problems in fact have a very sparse
Simplex Tableau --- lots of zeros  -- perhaps 90 percent of the matrix is
zeros!.  When using Array2DRealMatrix,  one invariable runs into a heap
space problem quite quickly.  Instead, by using the OpenMapRealMatrix the
code not physically allocate space for a complete K by N matrix as does the
Array2DRealMatrix.  The modifications to existing code were quite modest.
I think this approach is quite valuable for practitioners of large scale
linear programming problems.  There is a reduction in speed as the
System.arraycopy procedure is no longer employed.  The cost however
provides users with a vastly larger sandbox of memory for problem solving.


My code is thus:
LargeSimplexSolver.java
LargeSImplexTableau.java
 LargeSolutionCallback.java
and
SimplexMapMatrix a minor  extension of OpenMaprealMatrix.

I am willing to share the modifications if the math common group  thinks
such an effort is worthwhile.

Cheers to you all and keep up the good work.

Bill Igoe
Reply | Threaded
Open this post in threaded view
|

Re: Math Sparse Linear Programing -- Math Commons

Gilles Sadowski-2
Hi.

Le sam. 26 janv. 2019 à 04:24, Bill Igoe <[hidden email]> a écrit :

>
> Hi Gang,
>
> I recently alter the code for both SimplexSolver and SimplexTableau to use
> the OpenMapRealMatrix object rather than the Array2DRowRealMatrix.  Most
> large Linear Programming programming problems in fact have a very sparse
> Simplex Tableau --- lots of zeros  -- perhaps 90 percent of the matrix is
> zeros!.  When using Array2DRealMatrix,  one invariable runs into a heap
> space problem quite quickly.  Instead, by using the OpenMapRealMatrix the
> code not physically allocate space for a complete K by N matrix as does the
> Array2DRealMatrix.  The modifications to existing code were quite modest.
> I think this approach is quite valuable for practitioners of large scale
> linear programming problems.  There is a reduction in speed as the
> System.arraycopy procedure is no longer employed.  The cost however
> provides users with a vastly larger sandbox of memory for problem solving.
>
>
> My code is thus:
> LargeSimplexSolver.java
> LargeSImplexTableau.java
>  LargeSolutionCallback.java
> and
> SimplexMapMatrix a minor  extension of OpenMaprealMatrix.
>
> I am willing to share the modifications if the math common group  thinks
> such an effort is worthwhile.

If it extends the field of potential applications, it certainly looks
like a worthwile enhancement.

But I'd first try to avoid adding new classes if just for the sake
of changing a type used internally by the algorithm (dense vs
sparse matrix).
Wouldn't it be possible to add a constructor with a flag argument
that would trigger usage of one or the other type?

Regards,
Gilles

>
> Cheers to you all and keep up the good work.
>
> Bill Igoe

---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: Math Sparse Linear Programing -- Math Commons

Eric Barnhill
In reply to this post by Bill Igoe
It sounds like this is a worthwhile upgrade to the performance of the
Simplex solvers. I agree with Gilles that from a design perspective, the
class is accomplishing the same task only with an internal modification
difference, so if possible it should be set with an argument rather than a
whole new class.

Eric



On Fri, Jan 25, 2019 at 7:24 PM Bill Igoe <[hidden email]> wrote:

> Hi Gang,
>
> I recently alter the code for both SimplexSolver and SimplexTableau to use
> the OpenMapRealMatrix object rather than the Array2DRowRealMatrix.  Most
> large Linear Programming programming problems in fact have a very sparse
> Simplex Tableau --- lots of zeros  -- perhaps 90 percent of the matrix is
> zeros!.  When using Array2DRealMatrix,  one invariable runs into a heap
> space problem quite quickly.  Instead, by using the OpenMapRealMatrix the
> code not physically allocate space for a complete K by N matrix as does the
> Array2DRealMatrix.  The modifications to existing code were quite modest.
> I think this approach is quite valuable for practitioners of large scale
> linear programming problems.  There is a reduction in speed as the
> System.arraycopy procedure is no longer employed.  The cost however
> provides users with a vastly larger sandbox of memory for problem solving.
>
>
> My code is thus:
> LargeSimplexSolver.java
> LargeSImplexTableau.java
>  LargeSolutionCallback.java
> and
> SimplexMapMatrix a minor  extension of OpenMaprealMatrix.
>
> I am willing to share the modifications if the math common group  thinks
> such an effort is worthwhile.
>
> Cheers to you all and keep up the good work.
>
> Bill Igoe
>
Reply | Threaded
Open this post in threaded view
|

Re: Math Sparse Linear Programing -- Math Commons

Gilles Sadowski-2
Hi Bill.

Did you open a JIRA report?
A unit test would be welcome (one that makes the current implementation
crash but produces the expected results with your modifications).

Regards,
Gilles

Le lun. 28 janv. 2019 à 23:58, Eric Barnhill <[hidden email]> a écrit :

>
> It sounds like this is a worthwhile upgrade to the performance of the
> Simplex solvers. I agree with Gilles that from a design perspective, the
> class is accomplishing the same task only with an internal modification
> difference, so if possible it should be set with an argument rather than a
> whole new class.
>
> Eric
>
>
>
> On Fri, Jan 25, 2019 at 7:24 PM Bill Igoe <[hidden email]> wrote:
>
> > Hi Gang,
> >
> > I recently alter the code for both SimplexSolver and SimplexTableau to use
> > the OpenMapRealMatrix object rather than the Array2DRowRealMatrix.  Most
> > large Linear Programming programming problems in fact have a very sparse
> > Simplex Tableau --- lots of zeros  -- perhaps 90 percent of the matrix is
> > zeros!.  When using Array2DRealMatrix,  one invariable runs into a heap
> > space problem quite quickly.  Instead, by using the OpenMapRealMatrix the
> > code not physically allocate space for a complete K by N matrix as does the
> > Array2DRealMatrix.  The modifications to existing code were quite modest.
> > I think this approach is quite valuable for practitioners of large scale
> > linear programming problems.  There is a reduction in speed as the
> > System.arraycopy procedure is no longer employed.  The cost however
> > provides users with a vastly larger sandbox of memory for problem solving.
> >
> >
> > My code is thus:
> > LargeSimplexSolver.java
> > LargeSImplexTableau.java
> >  LargeSolutionCallback.java
> > and
> > SimplexMapMatrix a minor  extension of OpenMaprealMatrix.
> >
> > I am willing to share the modifications if the math common group  thinks
> > such an effort is worthwhile.
> >
> > Cheers to you all and keep up the good work.
> >
> > Bill Igoe
> >

---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]