[BCP] Variant of the BAC example (Erez Buchnik)

[Francois Margot]

Erez:

> > From: Erez Buchnik <erez.buchnik at gmail.com>
> > To: bcp at list.coin-or.org
> > Subject: [BCP] Variant of the BAC example
> > Date: Wed, 6 Apr 2011 11:08:55 +0200
> > 
> > Hello,
> > 
> > First of all, I am new to this subject, so I hope I'm sending this to the
> > right place - I'd appreciate it if you could redirect me if I'm not...
> > 
> > I've been experimenting with the BAC example for some time, trying to apply
> > the following ILP problem that is similar to the original one (formulated
> > for 15 binary variables X0,...X14):
> > 
> > Minimize:
> > 
> > obj = X0 + X1 + X2 + X3 + X4 + X5 + X6 + X7 + X8 + X9 + X10 + X11 + X12 +
> > X13 + X14
> > 
> > such that:
> > 
> > X0 + X2 >= 1
> > X0 + X4 >= 1
> > X0 + X6 >= 1
> > X5 + X8 >= 1
> > X9 + X4 >= 1
> > X9 + X6 >= 1
> > X9 + X6 + X12 + X14 >= 1
> > 
> > X1 == 1
> > X3 == 1
> > X5 == 1
> > X7 == 1
> > X3 + X10 >= 1
> > X5 == 1
> > X5 + X11 + X13 >= 1
> > 
> > A brute-force algorithm reveals that out of all the possible 32768 values
> > there are 768 that satisfy all the constraints, and only one that reaches
> > the minimum objective function value, which is 6.
> > 
> > This solution is as follows:
> > 
> > [ X0=1 ], [ X1=1 ], X2=0, [ X3=1 ], X4=0, [ X5=1 ], X6=0, [ X7=1 ], X8=0, [
> > X9=1 ], X10=0, X11=0, X12=0, X13=0, X14=0
> > 
> > I've applied programatically the problem coefficients to the desc structure
> > and tried to run it, but the algorithm finds no feasible solution. Attached
> > are two files, one with the dump of the successful run of the original BAC
> > example on the same code that I use (for reference), and one with the dump
> > for my problem. I've also added in the code dumps of the core and indexed
> > matrices.
> > 
> > NOTE: Since the constraints are generated automatically in my code, they may
> > be duplicated - removing the duplicates did not solve my problem, so I
> > assume this is not an issue.

As mentioned in the pdf file coming with the BAC example, it is not easy
to modify the BAC example to solve another problem. It is simpler to use
the SHELL example available at:
http://wpweb2.tepper.cmu.edu/fmargot/COIN/coin.html

That code reads an MPS or LP file and solves it using an elementary
branch-and-cut.

Francois