[Cbc] markshare1 mip2003 problem

[fmargot at andrew.cmu.edu]

Rolf:

markshare* problems are designed to be hard to solve by branch-and-cut.
See the paper Cornuejols, Gerard; Dawande, Milind "A class of hard small 
$0$-$1$ programs". Combinatorial optimization and network flows. 
INFORMS J. Comput.  11  (1999), 205--210.

As far as I know, all generic solvers fail to solve markshare1 in a
reasonable amount of time. Only reformulation work. See for example
the paper

K. Aardal, R. E. Bixby, C. A. J. Hurkens, A. K. Lenstra, J. W. Smeltink
"Market split and basis reduction: Towards a solution of the 
Cornuejols-Dawande instances", INFORMS Journal on Computing, 12 (2000) 192-202.

Francois

On Tue, 19 Jun 2007, Rolf Steenge wrote:

> Hi,
>
>
>
> The markshare1 is a small problem from the mip2003 library having only 7
> rows and 62 columns.
>
> (find the mps file enclosed)
>
>
>
> I tried to solve this problem with CBC (version 1.1.0) but I could not find
> the documented solution of 1.
>
> The best solution I can get is 7, by using pure branch and bound (no cuts)
> after more than 3 million nodes.
>
>
>
> I tried various other settings like cbcdefaultstrategy, some of the newer
> cuts like twomir and also the feasibility pump.
>
>
>
> Maybe I'v missed something, is there a way to solve this problem?
>
>
>
> Best regards,
>
> Rolf Steenge
>
>