Extended counter-example for extended M.Diaby Linear Model
in [Theory]
|
Prev: 2000 solution manuals, solution manual, Student Study Guide solutions
Next: Example for a non-rec.enum. language whose complement isn't rec.enum., too.
From: JM on 12 Jun 2008 05:35 >> A statement of the simplified (n^6) model is available at: Hi, may be this is of interest for both of you: I have developed a linear programming model for a general TSP with N^6 variables published under http://www.merlins-world.de Would be glad to get your feedback. Regards Joachim PS: Dear Radek, good look for your search for super-computer capacities. If you find it please let me know as I'm interested in running my model for more than 20 cities ;-)
From: Rados�aw Hofman on 12 Jun 2008 05:40 Oh, that is OK - I am running my calculations for this new O(n^6) model... The problem is that there are still millions of non-zero variables for my graph left so it takes much time... Anyway - I am very glad that you agreed with arguments why your model is O(n^6) - in my opinion it is still unable to solve large instance of TSP problem, but further on we may have discussion about merit not about formulation :-). Best regards, Radek Hofman
From: Radosław Hofman on 12 Jun 2008 06:18 Hi, I have taken a look at presentation you have provided (could you send me full article to my email?). It seems that your idea is almost the same as Diaby's (anyway - there are only few approaches used for P=NP claims, so it is not surprising :-) ). I do not say that there is any kind of influence to your model - several years ago I was also trying to build exact algorithm for NP-complete problem and one of ideas I have evaluated was nearly the same... So that is why I think that it is your own model. Any way if you think about why O(n^3) fails (slide 13) then you may observe that there is difference between integer and non-integer solution because SUM function cannot identify what is taken into account. If then you propose O(n^6) model then in other words one might say that you build model of O(n^3) graphs where each graph is exactly like graph in O(n^3) model... So, if O(n^3) fails then why do you think that large number of such graphs do not fail? Because “SUM” of graph prevents it? But you have seen that SUM fails... I think you might agree with this: - O(n^3) fails - 2 x O(n^3) fails - 3 x O(n^3) fails .... - k x O(n^3) fails .... - (n^3-1) * O(n^3) fails So - what is so special in one graph more that you think that this time it will provide exact solution? :-) My first CE from 2006 was for model with O(n^9) variables with only one constraint missing. This constraint is added to my new CE, so please try your framework against it - unfortunately it has 27 cities, but I am able to run calculations for this using my laptop. Best regards, Radek Hofman ----- Original Message ----- From: "JM" <joachim.mertz(a)gmx.de> Newsgroups: comp.theory Sent: Thursday, June 12, 2008 11:35 AM Subject: Re: Extended counter-example for extended M.Diaby Linear Model > >>> A statement of the simplified (n^6) model is available at: > > > Hi, > > may be this is of interest for both of you: > I have developed a linear programming model for a general TSP with N^6 > variables published under > http://www.merlins-world.de > > Would be glad to get your feedback. > > Regards > > Joachim > > PS: Dear Radek, good look for your search for super-computer > capacities. If you find it please let me know as I'm interested in > running my model for more than 20 cities ;-) >
From: moustapha.diaby on 12 Jun 2008 06:55 On Jun 12, 5:40 am, "Rados³aw Hofman" <rad...(a)teycom.pl> wrote: > Oh, that is OK - I am running my calculations for this new O(n^6) model... > The problem is that there are still millions of non-zero variables for my > graph left so it takes much time... > > Anyway - I am very glad that you agreed with arguments why your model is > O(n^6) - The "projection" I presented is n^6. Higher order projections onto the same space are possible (for the n^9 model in particular). in my opinion it is still unable to solve large instance of TSP > problem, but further on we may have discussion about merit not about > formulation :-). > Your argumentation in support of this opinion has been trivially invalid. //MD
From: Radoslaw Hofman on 12 Jun 2008 07:40
Uzytkownik <moustapha.diaby(a)business.uconn.edu> napisal w wiadomosci news:525c3789-6e6d-4b24-85bb-3162402f4cf3(a)d1g2000hsg.googlegroups.com... in my opinion it is still unable to solve large instance of TSP > problem, but further on we may have discussion about merit not about > formulation :-). > Your argumentation in support of this opinion has been trivially invalid. :-)))))) I will agree when I shall se mathematical proof :-) Best regards, Radek Hofman |