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. _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
