[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] changing subsets of the constraint matrix
From: |
Heinrich Schuchardt |
Subject: |
Re: [Help-glpk] changing subsets of the constraint matrix |
Date: |
Tue, 24 Nov 2015 20:06:45 +0100 |
User-agent: |
Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Icedove/31.8.0 |
Hello Joe,
if the changed coeeficients are only in some rows or in some columns you
could use glp_set_mat_col or glp_set_mat_row to only touch these parts
of the matrix.
In the current data structure GLPAIJ the elements of a row or column are
not sorted.
So finding a single elements in a n x m matrix takes O(min(n, m)) time.
The same is true for replacing a whole row or column.
What is the time you need to call glp_load_matrix compared to time
needed to call glp_simplex? Just call Linux API function clock_gettime
before and after the two calls. I would expect glp_load_matrix taking
only tiny a fraction of the time needed for glp_simplex.
Best regards
Heinrich Schuchardt
On 24.11.2015 19:30, Atwood, Joseph wrote:
> Good Morning
>
> We have an application that requires that we run hundreds of thousands
> (or even several million) slightly revised sparse LP problems per run.
> These problems are not huge but are not trivial with constraint matrices
> with up to 10,000+ constraints and variables. At each iteration we are
> changing from 1 to 0.01 percent of the non-zero coefficients.
>
>
>
> We have written a Fortran interface to the compiled glpk code and we
> have found that we can substantially decrease the total computation time
> by having the Fortran interface (1) loop through the LP problems, (2)
> pass the revised matrix coefficients directly into glpk, (3) pull the
> revised solutions and objective back into Fortran, and (4) having
> Fortran pass the results back to our R session upon completion of the LP
> runs. Our current Fortran code passes the revised LP problem’s entire
> set of non-zero constraint coefficients back into glpk at each iteration.
>
>
>
> Is there a way (or would the glpk maintainers consider adding a way)
> that we could pass only the revised coefficients rather than having to
> pass the entire set of nonzero coefficients into glpk?
>
>
>
> lpSolveAPI has the ability to pass only the revised coefficients into
> the problem, and as a result, using lpSolveAPI (directly from R) runs
> substantially faster than running glpkAPI (directly from R). We have
> written a Fortran interface for both lpSolve and glpk and find that the
> Fortran-glpk interface improves performance substantially relative to
> using lpSolve.
>
>
>
> With lpSolve, passing only the changed coefficients gives a performance
> boost relative to passing the complete set of nonzero coefficients at
> each iteration.
>
> We are wanting to determine whether we could similarly decrease
> computation time for glpk by passing only the revised coefficients.
>
> Joe Atwood