Hello Patrik, glpios10.c has the following lines: * M.Fischetti, F.Glover, and A.Lodi. "The feasibility pump." Math. * Program., Ser. A 104, pp. 91-104 (2005). */ You can find the article at http://www.dei.unipd.it/~fisch/papers/feasibility_pump.pdf
Further reading is: http://www.dei.unipd.it/~fisch/papers/feasibility_pump_201.pdf http://www.zib.de/Publications/Reports/ZR-05-42.pdf Best regards Xypron On 26.07.2012 20:24, Robbie Morrison wrote: > 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 > _______________________________________________ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk