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

[Andrew Makhorin]

On Tue, 2015-11-24 at 18:30 +0000, 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?   

Glpk doesn't have such a feature.

In principle, it would be quite easy to add the following routine
(similar to glp_load_mat):

void glp_patch_mat(glp_prob *P, int ne, const int ia[], const int ja[],
const double ar[]);

where ne is the number of coefficients to be changed, ia, ja, and ar
specify, resp., row indices, column indices, and numeric values of the
coefficients to be changed (ar[k] = 0 means removing coefficient, if it
exists).

Please note, however, that solving lp includes much more than specifying
the constraint matrix, so I am not sure that using glp_patch_mat instead
of glp_load_mat (which replaces the whole matrix) will significantly
reduce the overall solution time.

How many simplex iterations are usually needed to solve one lp instance?
Do you restart the search from the current basis on solving the next lp,
or start it from scratch every time?

> 
>  
> 
> 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
> 
>  
> 
> 
> _______________________________________________
> Help-glpk mailing list
> address@hidden
> https://lists.gnu.org/mailman/listinfo/help-glpk