Re: [Help-glpk] Feasibility pump heuristic

[Xypron]

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:           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]
>
>
>
> _______________________________________________
> Help-glpk mailing list
> address@hidden
> https://lists.gnu.org/mailman/listinfo/help-glpk
>