Re: [Help-glpk] MathProg (GMPL) with Tables (i.e. SQLIte3) and CBC MILP solver works

[Noli Sicad]

Hi,

CBC and MathProg work even better / faster now with the "New Heuristic
(due to Fischetti and Monaci)" in CBC trunk.

Here's the post of John Forrest in CBC ML.

#########################################
I am pleased to say that I have spent a very small amount of time
implementing the Proximity Search heuristic by Fischetti and Monaci.

At present it is only in Cbc trunk and by default is off.  The
simplest way to switch it on using stand-alone version is "-proximity
on".

Proximity Search is the new "No-Neighborhood Search" 0-1 MIP
refinement heuristic recently proposed by Fischetti and Monaci (2012).
The idea is to define a sub-MIP without additional constraints but
with a modified objective function intended to attract the search in
the proximity of the incumbent. The approach works well for 0-1 MIPs
whose solution landscape is not too irregular (meaning the there is
reasonable probability of finding an improved solution by flipping a
small number of binary variables), in particular when it is applied to
the first heuristic solutions found at the root node. Feedback about
(un)successful applications are very welcome, and can be send directly
to Matteo Fischetti (address@hidden)

Feedback about unsuccessful applications may also be sent to me as I
may need to improve my implementation.

John Forrest
#####################################

Matteo Fischetti webpage
http://www.dei.unipd.it/~fisch/

I think this is the paper - "backdoor_branching.pdf"
http://www.dei.unipd.it/~fisch/papers/

My MIP CBC-MathProg model with SQLIte database / tables is solved in 6
minutes and 3 seconds. It was solved by CBC without this new heuristic
algorithm in 17 minutes before.

The MPS and Free MPS formats derived from the CBC - MathProg model
(above) are solved at 2 min and 45 sec. It was previously solved by
CBC at 9 minutes.

NEOS server (SCIP - CPLEX) solved this model in 1 min and 42 secs.

CBC with"-proximity on" also solve a very hard to solve constraints
(below) in 4 minutes.

#####

Evenflow_Harvest_Volume_HV_Alpha(1): + 0.99 Harvest(1) - Harvest(2)
 <= -0
 Evenflow_Harvest_Volume_HV_Alpha(2): + 0.99 Harvest(2) - Harvest(3)
 <= -0
 Evenflow_Harvest_Volume_HV_Alpha(3): + 0.99 Harvest(3) - Harvest(4)
 <= -0
 Evenflow_Harvest_Volume_HV_Alpha(4): + 0.99 Harvest(4) - Harvest(5)
 <= -0
 Evenflow_Harvest_Volume_HV_Alpha(5): + 0.99 Harvest(5) - Harvest(6)
 <= -0
 Evenflow_Harvest_Volume_HV_Beta(1): + 1.01 Harvest(1) - Harvest(2)
 >= -0
 Evenflow_Harvest_Volume_HV_Beta(2): + 1.01 Harvest(2) - Harvest(3)
 >= -0
 Evenflow_Harvest_Volume_HV_Beta(3): + 1.01 Harvest(3) - Harvest(4)
 >= -0
 Evenflow_Harvest_Volume_HV_Beta(4): + 1.01 Harvest(4) - Harvest(5)
 >= -0
 Evenflow_Harvest_Volume_HV_Beta(5): + 1.01 Harvest(5) - Harvest(6)
 >= -0
####

I would be good to have this "New Heuristic by Fischetti and Monaci"
(now in CBC trunk) implemented in GLPK.

Thanks.

Noli



On 11/21/12, Noli Sicad <address@hidden> wrote:
> Hi,
>
> CBC 2.7.7 and GLPK-4.45 works (compile and install) out of the box in Mac OS
> X.
>
> See this log (below).
>
> It is quick, it takes only 9 minutes. Unlike the freemps format solves
> in CBC as well, takes 17 minutes to solve this MIP model.
>
> The CBC MathProg - ThridParty is ported by Stefan Vigerske who works
> with GAMS now.
>
> http://www.math.hu-berlin.de/~stefan/
>
> The CBC MathProg does not return the solution to MathProg environment,
> just input to CBC solver. It is only working using GLPK-4.45.
>
> Noli
>
> ####
>
> Nolis-MacBook-Pro:Case_Studies nsicad$ cbc
> MIP_model_I_P6r_spl_1500_working_evenflow_0025p.mod% -printi all
> -solve -solu solution.out
> Welcome to the CBC MILP Solver
> Version: 2.7.7
> Build Date: Nov 20 2012
>
> command line - cbc
> MIP_model_I_P6r_spl_1500_working_evenflow_0025p.mod% -printi all
> -solve -solu solution.out (default strategy 1)
> GMPL model file ./MIP_model_I_P6r_spl_1500_working_evenflow_0025p.mod
> and data file ./
> Reading model section from
> ./MIP_model_I_P6r_spl_1500_working_evenflow_0025p.mod...
> Reading data section from
> ./MIP_model_I_P6r_spl_1500_working_evenflow_0025p.mod...
> 599 lines were read
> Reading Origin1...
> Connected to SQLite 3.7.6.2 -
> /Users/nsicad/Documents/A_Document_1/Pete_book/Lincoln_stands.sqlite
> SELECT ID FROM Lincoln_stands
> Display statement at line 41
> STAND:
>    1
>    2
>    3
>    4
>    5
>    6
> ..
>
> FlowCover was tried 100 times and created 0 cuts of which 0 were
> active after adding rounds of cuts (0.061 seconds)
> TwoMirCuts was tried 100 times and created 87 cuts of which 0 were
> active after adding rounds of cuts (0.131 seconds)
>
> Result - Optimal solution found
>
> Objective value:                -345556.66666667
> Enumerated nodes:               1007292
> Total iterations:               12059944
> Time (CPU seconds):             543.33
> Time (Wallclock seconds):       546.31
>
> Total time (CPU seconds):       543.37   (Wallclock seconds):       546.37
>
> Nolis-MacBook-Pro:Case_Studies nsicad$
>