Re: [Help-glpk] Feasibility pump heuristic

[Robbie Morrison]

Hello Patrik

------------------------------------------------------------
To:           address@hidden
Subject:      [Help-glpk] Feasibility pump heuristic
From:         Patrik Dufresne <address@hidden>
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) : address@hidden
Webmail (preferred)           : address@hidden
[from Webmail client]