From: Chris Beck [jcb@mie.utoronto.ca] Sent: 08 October 2010 14:23 To: Patrick Prosser Subject: 100 node results Attachments: check.tri100all.scip.darwin.x86_64.gnu.opt.spx.reims.default.res Hi Patrick, Attached is the summary table for the 1050 instances with 100 nodes. The "ok" on the right-hand side indicates that the optimal solution matches your results. I am not sure how the instances map into kappa but as I scroll through the file and look at the number of nodes, it looks like it gets larger in the 100- {21-23}-* region. The summary bit is at the bottom: ------------------------------[Nodes]---------------[Time]------ Cnt Pass Time Fail total(k) geom. total geom. ---------------------------------------------------------------- 1050 1050 0 0 10 6.2 3088.5 2.6 shifted geom. [ 100/ 10.0] 10.1 2.8 ---------------------------------------------------------------- Total nodes over 1050 problems: 10K Geometric mean of number nodes: 6.2 - so almost no search. The max number of nodes I could see was 33. Geometric mean run-time: 2.6 seconds. Total time for solving all 1050 problems on my MacBook: 3088.5 secs It would be interesting to plot the median # nodes against kappa to see what we see. Given how little search is done here, I am wondering if the answer to "Where have all the hard problems gone?" is just that these instances are not big enough. I know you argued against this in your paper but as the LP relaxation here is so good, I wonder if what we really should be looking for is the complexity peak for solving the LP (if that even makes any sense). If we went to 500 or 1000 nodes, would we see the complexity peak? I'll talk to one of the SCIP guys on Monday to see if I can get more insight into what is really working here. Chris -- J. Christopher Beck Toronto Intelligent Decision Engineering Lab Mechanical& Industrial Engineering University of Toronto 5 King's College Rd Toronto, ON CANADA M5S 3G8 ph: (416) 946-8854 fax: (416) 978-7753