[Coin-announce] Branch-and-cut solver now available on COIN-OR

[John J Forrest]

When the COIN LP solver (Clp) was being written, the Osi interface to Clp
demanded an *integer * solver, so I wrote a very simple branch and bound
code.  Somehow I kept adding to the code and eventually it grew into its
own project.    Simple Branch and Bound (or Sbb) is no longer quite as
simple. It is now branch and cut.  Its design goal is to be simpler than
BCP and to work on many problems without tuning.

Some features:
- add your own cuts or those in the cut generation library
- add your own  heuristics
- add your own methods of selecting branching node and variable
- use with any solver has an Osi interface
- 100% open-source integer program solver

Any cuts in the Cgl library may be used with Sbb.  If a user writes a new
cut generator to the Cgl specifications then the new cut can be used by
adding the header file and  two lines of code to the main program.

There will be a family of heuristics (at present there only is one) which
can be added to Sbb in a way that is similar to how the cut generators are
added.

The node and variable choice methods can be overridden.  It is intended
that the method of branching can be overridden (I should soon have a
variant of Special Ordered sets in as an example).

Sbb uses the Osi solver interface, and any simplex solver having an Osi
interface may be used with Sbb. Of course, for development I am using Clp
so that the effort will be 100% COIN.

Sbb is still very much a work in progress but I expect it to be approaching
its final form sometime this year.  At present it can solve 40 out of 59
problems in the miplib3 test set in 30 minutes or less.  I expect to be
able to claim another 5 to 10 in a month or so.

I append  the test results to show that it is not vaporware.  I would be
interested to have statistics from any other solver to get a comparison.

John Forrest

--------------------------------------------------------------

Problems were run with January 6 version.  The main program was
Sbb/Samples/sample2.cpp
Code was compiled with gcc 3.2.1 with  Clp, Coin, Cgl at -O2 and Sbb at -g
optimization levels

A maximum time of 30 minutes was allowed on a 1.7ghz Pentium 4 Thinkpad

My miplib test set has 59 problems.  40 finished in 30 minutes or less

10teams took 141.71 seconds, 88 nodes with objective 924
air03 took 1.02 seconds, 0 nodes with objective 340160
bell3a took 73.83 seconds, 5894 nodes with objective 878430
bell5 took 137.4 seconds, 6092 nodes with objective 8.96641e+06
blend2 took 35.07 seconds, 647 nodes with objective 7.59898
cap6000 took 918.47 seconds, 1840 nodes with objective -2.45138e+06
dcmulti took 6.46 seconds, 99 nodes with objective 188182
dsbmip took 12.6 seconds, 31 nodes with objective -305.198
egout took 0.32 seconds, 4 nodes with objective 568.101
enigma took 181.37 seconds, 10543 nodes with objective 0
fixnet6 took 42.03 seconds, 318 nodes with objective 3983
flugpl took 0.27 seconds, 28 nodes with objective 1.2015e+06
gen took 0.22 seconds, 1 nodes with objective 112313
gesa2_o took 154.28 seconds, 827 nodes with objective 2.57799e+07
gesa3 took 18.44 seconds, 108 nodes with objective 2.7991e+07
gesa3_o took 17.95 seconds, 132 nodes with objective 2.7991e+07
khb05250 took 122.26 seconds, 2440 nodes with objective 1.0694e+08
l152lav took 153.67 seconds, 474 nodes with objective 4722
lseu took 1.95 seconds, 85 nodes with objective 1120
misc03 took 6.75 seconds, 82 nodes with objective 3360
misc06 took 2.83 seconds, 22 nodes with objective 12850.9
misc07 took 592.56 seconds, 3390 nodes with objective 2810
mitre took 409.2 seconds, 157 nodes with objective 115155
mod008 took 30.99 seconds, 784 nodes with objective 307
mod010 took 0.33 seconds, 0 nodes with objective 6548
nw04 took 116.71 seconds, 6 nodes with objective 16862
p0033 took 0.16 seconds, 3 nodes with objective 3089
p0201 took 4.46 seconds, 36 nodes with objective 7615
p0282 took 15.5 seconds, 122 nodes with objective 258411
p0548 took 1.14 seconds, 18 nodes with objective 8691
p2756 took 24.92 seconds, 120 nodes with objective 3124
pp08a took 1278.81 seconds, 18313 nodes with objective 7350
pp08aCUTS took 1340.17 seconds, 15032 nodes with objective 7350
qnet1_o took 63.42 seconds, 438 nodes with objective 16029.7
rentacar took 143.61 seconds, 20 nodes with objective 3.03568e+07
rgn took 8.38 seconds, 358 nodes with objective 82.2
stein27 took 31.27 seconds, 1304 nodes with objective 18
stein45 took 1054.34 seconds, 13054 nodes with objective 30
vpm1 took 23.26 seconds, 411 nodes with objective 20
vpm2 took 810.27 seconds, 10943 nodes with objective 13.75

The following did not finish in 30 minutes
I expect to be able to do another five in reasonable time by end January

air04
air05
arki001
dano3mip
danoint
fast0507
fiber
gesa2
gt2
harp2
mod011
modglob
noswot
pk1
qiu
qnet1
rout
set1ch