[Top][All Lists]

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

Re: [Help-glpk] glpk 4.60 release information

From: Chris Matrakidis
Subject: Re: [Help-glpk] glpk 4.60 release information
Date: Mon, 4 Apr 2016 20:18:33 +0300


>         Some improvements were made in the primal and dual simplex
>         solvers to make the solution process more numerically stable.

Indeed, the latest version is very stable: I tried several problems
that had issues before without any problems. However, the perturbation
code disables the check whether the objective limit has been reached,
which results in a lot more iterations. In order to address this, I
tried to keep track whether objective coefficients are modified and
only disable the check in this case. I attach two patches that achieve
-The fist one adds all potential coefficient changes away from the
original, and subtracts only the ones that definitely restore the
original coefficient. This is an upper bound to the number of modified
coefficients and as such disables the check a few times more than
strictly necessary.
-The second patch (relative to the first one) works a bit harder to
count the exact number of modified coefficients at every point.

A test case that nicely shows the improvement is with rmatr100-p5 from
miplib (using a saved solution):
glpsol --pcost rmatr100-p5.mps.gz --use rmatr100-p5.sol.gz

All cases finish the search with 3577 nodes, but the number of
iterations needed are:
original           960889 iterations
first patch       480941 iterations
second patch  468640 iterations

Best Regards,

Chris Matrakidis

Attachment: 0001-keep-track-of-perturbed-coefficients-in-dual-simplex.patch
Description: Binary data

Attachment: 0002-keep-track-of-perturbed-coefficients-in-dual-simplex.patch
Description: Binary data

reply via email to

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