[Cbc] New Heuristic (due to Fischetti and Monaci)

[Noli Sicad]

Hi John,

> 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 (matteo.fischetti at unipd.it)
>
> Feedback about unsuccessful applications may also be sent to me as I may
> need to improve my implementation.

I got amazing results with this new heuristic algorithm.

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

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.

Thanks for this new heuristic for CBC.

Regards,

Noli