Re: [Help-glpk] Preprocessing

[Andrew Makhorin]

Hi Xypron,

> @ARTICLE{Gondzio94presolveanalysis,
>     author = {Jacek Gondzio},
>     title = {Presolve Analysis of Linear Programs Prior to Applying an 
> Interior Point Method},
>     journal = {INFORMS Journal on Computing},
>     year = {1994},
>     volume = {9},
>     pages = {73--91}
> }
> http://www.maths.ed.ac.uk/~gondzio/software/presolve.ps
> gives a nice overview of preprocessing for linear programming.

I have this article in my library. Note that some transformations
described there are important only for interior point methods; for
example, the simplex method is not sensitive to dense columns. 

> Most of the ideas have already been implemented in GLPK.
> 
> According to my understanding the following are not yet implemented in GLPK:
> - identify linear dependent rows and columns, especially duplicates
> - improving sparsity
> 
> Would you consider these preprocessing steps worthwhile to implement?

I will think how to implement new features of glpk in a more systematic
way. Currently I am working over some improvements in the branch-and-cut
solver, and it is difficult for me to switch between different tasks.


Best regards,

Andrew Makhorin