Re: [Help-glpk] changing subsets of the constraint matrix

[Heinrich Schuchardt]

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