[Cbc] muti-thread compile for cbc-2.7.8

[Matteo Fischetti DEI]

Hi Noli.

Let me summarize the situation.

1. Proximity search is only available in CBC\trunk; in interactive mode, 
it is activated by -proximity on.

2. On stable CBC 2.7.8 the proximity flag is accepted but not used (yet)

3. In interactive mode, you can check the LOG to see the effect of the 
proximity heuristic, e.g.

 > cbc ..\seymour.lp -proximity on -solve
Welcome to the CBC MILP Solver
Version: *Trunk (unstable)*
Build Date: Nov 29 2012
...
Cbc0012I Integer solution of 428 found by feasibility pump after 0 
iterations and 0 nodes (16.67 seconds)
Cbc0012I Integer solution of 427 found by RINS after 0 iterations and 0 
nodes (19.44 seconds)
...
*Cbc0012I Integer solution of 426 found by **Proximity Search **after 0 
iterations and 0 nodes (37.95 seconds) *
...

4. Proximity search is a refinement heuristic, hence it is NOT applied 
when no solution is found at the root

5. Now I come to your important question below:

 >>> However, I could not understand why 2.7.8 runs faster than the 
trunk. The trunk solved the same MIP double the time (i.e. 2x longer) 
than using 2.7.8 with or without the proximity search. It seems that 
proximity search does not matter if you run threads (i.e. threads 8).

My explanation is that you are just facing "erraticism" here, meaning 
that small changes of the initial conditions (including using a 
different architecture/compiler/n. of threads) can randomly change LP 
sol.s --> branching --> search path, sometimes allowing you to converge 
much earlier.

I recently had a provocative talk about this (well know) behavior, see 
Mike Trick's blog at

_http://mat.tepper.cmu.edu/blog/?p=1695_

Coming to your specific instance (TimberHarvest_0010p.lp), tonight I ran 
99 times cbc\trunk (1-thread) with the command

 > cbc ..\TimberHarvest_0010p.lp   -randomCbcSeed 0 -randomSeed 0 -solve

where -randomCbcSeed and -randomSeed allow you to change the internal 
CLP and CBC random seeds (0 uses clock as seed).

I posted at

_www.dei.unipd.it/~fisch/rand.txt_

the LOGs; here is an extract:

     run    CPU sec.s         nodes
     --------------------------------

     #001      422.80       688,438
     #002      120.42       541,641
     #003      289.89       980,125
     #004      442.28       472,552
     #005      599.50       694,749
     #006      638.95     1,192,398
     #007      220.62       464,118
     #008      446.78       581,108
     #009      231.38       627,515
     #010      275.19       714,783
...
     #069       79.25       262,105
...
     #099     1816.64     1,998,075


So, depending on the random seeds, your instance can be solved in 79 or 
1816 sec.s (!!)

6. Of course, not all instances behave the same, but you better know 
that sometimes erraticism can play a relevant role, e.g., when you make 
parameter tuning--or when you try to explain why a certain idea (out of 
100 you tried) is working magically well...

7. In my view, erraticism is an opportunity rather than an issue--e.g., 
by running multiple times the same solver with different random seeds 
(possibly in parallel), you can hopefully find better heuristic 
solutions at the root node.

Here is an example: running 5  times

 > cbc   ..\seymour.lp -randomCbcSeed 0 -randomSeed 0 -solve

produces the following root-node heuristic solutions:

run #1: Objective value: 429.00000000
run #2: Objective value: 428.00000000
run #3: Objective value: 426.00000000
run #4 :Objective value: 427.00000000
run #5: Objective value:                427.00000000

Analogously, running

 > cbc    ..\seymour.lp -randomCbcSeed 0  -randomSeed 0 -proximity on 
-passF 0 -solve

produced (still at the root):

run #1: Objective value:                426.00000000
run #2: Objective value:                425.00000000
run #3: Objective value:                425.00000000
run #4: Objective value:                424.00000000
run #5: Objective value:                423.00000000  <-  optimal value

7. Any comment on the subject is welcome.

Best

--Matteo--



-- 
Prof. Matteo Fischetti
DEI, University of Padova
via Gradenigo 6/A
I-35131 Padova (Italy)
e-mail: matteo.fischetti at unipd.it
web: www.dei.unipd.it/~fisch
reports: www.dei.unipd.it/~fisch/papers
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/cbc/attachments/20121130/4eaa42b0/attachment-0001.html>