Hello Patrik
------------------------------------------------------------
To: help-glpk@gnu.org
Subject: [Help-glpk] Feasibility pump heuristic
From: Patrik Dufresne <ikus...@gmail.com>
Date: Thu, 26 Jul 2012 12:51:55 -0400
------------------------------------------------------------
> Hi,
>
> I'm using GLPK to model an integer linear problem and
> then solve it using glp_intopt(). Since, I'm a beginner
> with linear problem, I've try different option of the
> solver. One of them is the Feasibility pump heuristic
> (fp_heur). Enabling this option solve the problem
> within 24sec instead of 192sec when disabled.
>
> My first question, do you have any reference material
> to explain how the feasibility pump heuristic is
> working ?
This publication describes changes to GLPK 4.28 to test
novel MILP branching techniques. I don't know if it
covers the heuristic you mentioned but it should
provide some useful background:
Pryor, Jennifer; Chinneck, John W (2011), "Faster
integer-feasibility in mixed-integer linear
programs by branching to force change", Computers
and Operations Research 38 (8): 1143-1152,
doi:10.1016/j.cor.2010.10.025
paywalled :
http://www.sciencedirect.com/science/article/pii/S0305054810002546
preprint :
http://www.sce.carleton.ca/faculty/chinneck/docs/PryorChinneck.pdf
> When enabled, is the optimality is still garanteed ?
Yes, barring unknown errors in chipset, compilers,
libraries, and models.
This might be of interest in relation to GLPK:
http://en.wikibooks.org/wiki/GLPK/Background_theory
Then read up about the Karush-Kahn-Tucker (KKT)
optimality conditions elsewhere:
http://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions
> Thanks for you'r help.
>
> Patrik Dufresne
> -------------- next part --------------
> An HTML attachment was scrubbed...
> URL:
<http://lists.gnu.org/archive/html/help-glpk/attachments/20120726/ba56f1bc/attachment.html>
HTH, Robbie
---
Robbie Morrison
PhD student -- policy-oriented energy system simulation
Technical University of Berlin (TU-Berlin), Germany
University email (redirected) : morri...@iet.tu-berlin.de
Webmail (preferred) : rob...@actrix.co.nz
[from Webmail client]
_______________________________________________
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk
