[Top][All Lists]

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

[Help-glpk] Feasibility Pump

From: xypron
Subject: [Help-glpk] Feasibility Pump
Date: Mon, 14 Sep 2009 15:20:53 -0700 (PDT)

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 

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


View this message in context:
Sent from the Gnu - GLPK - Help mailing list archive at

reply via email to

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