[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Help-glpk] Preprocessing

From: Andrew Makhorin
Subject: Re: [Help-glpk] Preprocessing
Date: Thu, 14 Oct 2010 22:31:49 +0400

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}
> }
> 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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]