From: Patrick Prosser Sent: 08 October 2010 11:58 To: 'Chris Beck' Subject: RE: Triangle packing in SCIP Chris, teaching stops Friday 10/12/10 so I'll be free when you are here. It will be great to meet up with you and Angela again and fun to do some work together. I forgot you are in Berlin ... you will get the race results before me. Here's the thing ... the encoding we have for triangle packing, we are essentially finding an independent set of a known size. Is there something funny about that graph and that decision problem? Could we reproduce this "no complexity peak" phenoma in other problems, possibly problems that map easily to indSet? And, we have kappa for triangle packing, could we define kappa for independent set decision problem? If we can we might be able to get a better handle on just what's happening. Here is a nice problem that maps to indSet, stable marriage with ties and incomplete lists (SMTI). It is NP-complete and poorly studied. I spoke to THE world experts on SMTI (Rob Irving, David Manlove, Eric McDermid). They accept that this is a legal mapping and that nobody has studied this, and very little has been studied empirically on SMTI. That could be a candidate The other thought is that there are loads of CP encodings that just use 0/1 variables, and have sometimes been beaten when we use more "natural" encodings. One example of this is the slab design problem, recent work by PvH & Michel in CPAIOR-08 and in CP07 Gargani & Refalo. The "old" 0/1 encodings have been rejected. But would they succumb to MIP? So the question is: Where have the hard problems gone? P -----Original Message----- From: Chris Beck [mailto:jcb@mie.utoronto.ca] Sent: 08 October 2010 11:39 To: Patrick Prosser Subject: Re: Triangle packing in SCIP On 10-10-08 12:14 PM, Patrick Prosser wrote: > Chris > Just tared& gziped here > http://www.dcs.gla.ac.uk/~pat/jchoco/trianglePacking/ > > Look for file jcb.gz > > You will need to > > gunzip jcb.gz > tar -xvf jcb > > Do you have/want my comet code to compare? I took mp02.co and basically converted it to C++ (once I figured out what you were doing :). I'm at home (Berlin) running things on my MacBook and so there is not too much point in doing any detailed analysis. I'll run a few big problems to see what happens, then I need to go and talk to some SCIP people (on Monday) so that they can give me an idea of what is going on. First impressions after running a couple of the 200 node instances: - solve is done in < 60 seconds (on my MacBook) and very little search (often 1 node, I haven't seen more than 8 nodes). This is consistent with you not seeing any complexity peak since there is very little search going on. - most of the run-time is in solving the first LP but the solution - first LP solution is very good (e.g. optimal is 66 and first LP solution is 66.67) - what seems to happen is that the heuristics at the root node are often able to find the optimal solution and since the LP solution is to tight, proof of optimality is immediate Angela & I are going to be in Glasgow Dec 6 - 14. I'm visiting Maria and Derek. Perhaps, we can plan for some time to look at this stuff? I can set you up with native SCIP and my model if you want - then we can do runs on the same hardware as the rest of your results. Chris > I'll tar& gzip results soon > > P > > > > -----Original Message----- > From: Chris Beck [mailto:jcb@mie.utoronto.ca] > Sent: 08 October 2010 11:07 > To: Patrick Prosser > Subject: Triangle packing in SCIP > > Hi Patrick, > > I've put together a SCIP implementation of your triangle packing MIP > model. Can you send me all your problem instances? (I can't figure out > an easy way to download them from your website without repeated calls). > > I have managed to down load some of the 20 variables files and so far > that all solve in the root node - no search. But they are small. > > 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 > > > The University of Glasgow, charity number SC004401 > -- 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