[Help-glpk] Feasibility Pump

[xypron]

Hello Andrew,

thanks to your implementation of the feasibility pump many MIPs can be
solved with GLPK much more efficiently.

== Number of Iterations ==
When I read the paper 

Tobias Achterberg, Timo Berthold
Improving the Feasibility Pump
Discrete Optimization 4 (2007) 77-86
(also available as
http://opus.kobv.de/zib/volltexte/2005/875/pdf/ZR-05-42.pdf
http://opus.kobv.de/zib/volltexte/2005/875/pdf/ZR-05-42.pdf 
)

I remarked that the number of iterations described vastly exceeded what you
chose in glpios10.c:
"if (nfail < 3) goto loop;"

I suggest either to offer a parameter to specify the number of iterations or
to 
choose a much larger value >= 50.

This should allow to find a feasible solution for more problems.

== Improvement Passes ==

When the feasibility pump reaches an integer solution GLPK tries to improve
on it
by factor 1.1 or 0.9. The effect will vary drastically, if I change the
original
problem by adding an offset to the objective function:
a) Minimize obj : x;
b) Minimize obj : x + 100;

In problems with large penalty costs the current implementation will often
lead
to an integer infeasable problem in the improvement step.

I suggest instead the required improvement to be a fraction of the
remaining gap of the last integer solution found with respect to the
original
objective function.

== Objective Feasibility Pump ==
Said paper by Achterberg proposes to include the objective function into
the search.

Would you deem it worthwhile to integrate the Achterberg algorithm
into GLPK?

Best regards

Xypron

-- 
View this message in context: 
http://www.nabble.com/Feasibility-Pump-tp25444734p25444734.html
Sent from the Gnu - GLPK - Help mailing list archive at Nabble.com.