[Top][All Lists]

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

Re: [Help-glpk] Feasibility pump heuristic

From: Robbie Morrison
Subject: Re: [Help-glpk] Feasibility pump heuristic
Date: Fri, 27 Jul 2012 06:24:47 +1200
User-agent: SquirrelMail/1.4.22

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,

paywalled :
preprint  :

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

Then read up about the Karush-Kahn-Tucker (KKT)
optimality conditions elsewhere:

> Thanks for you'r help.
> Patrik Dufresne
> -------------- next part --------------
> An HTML attachment was scrubbed...
> URL:

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]

reply via email to

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