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 08:17
Hi,

thanks for your quick response, see my annotations/answers below

> I have taken a look at presentation you have provided (could you send me
> full article to my email?).
yes, can send you the article by mail.

> 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.

In fact I found your discussion in 2006 when I was looking for
something similar to my approach. Nevertheless, I never heard of it
before, so I developed it independently. In fact both approaches are
similar as they use LP formulation for TSP by using something like a
network flow model and add further constraints to suppress invalid non-
integer solutions.


>
> 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...
Exactly

> 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
annotation: just O(n^2) of the O(n^3) graphs, but this doesn't matter

> So  - what is so special in one graph more that you think that this time it
> will provide exact solution? :-)
You're right, the SUM function can't identify invalid non-iteger
solutions in the basic n^3 model.
But this is different for the SUM in the N^6 model. Consider e.g. the
following non-valid solution with two cyclic routes, both with
'weight' 0.5 and start station 0:
1: 0-1-2-3-4-3-0
2: 0-5-1-5-2-4-0

The overall weights for each station (city) vistited by the two path
is 1 so contraint (1) in my proposal is fulfilled.
In the mirror-graph e.g. for station 2 at the third position there is
only
2-3-4-3-0-1-2
and here the SUM in constraint (7) detects a asymmetry in the weighted
visits of the stations:
weight 0.5 for station 2,4, 0,1, weight 1 for station 2, weight 0
for station 5

so constraint (7) would be violated.

Hope this clarifies the basic idea separating the particular routes/
pathes by the n^2 mirror-graphs in order to let the asymmetric
characteristics of the particular routes emerge and to detect/suppress
them by the SUM in constraint (7)


>
> 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.
If you mean the 'valley approach': I downloaded your CE and made some
trials with it some months ago.
Unfortunately my LP solver runs considerable slower with it, so I was
only able to run it with 14 cities in 3 valleys (with cost 1 for arcs
within a valley and cost 1000 for arcs jumping into another valley).
So again, if you find someone with an unemployed super-
computer... ;-)

Best regards,

Joachim Mertz
From: JM on 12 Jun 2008 08:56
> 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 underhttp://www.merlins-world.de


Correction: The model requires O(N^5) variables not O(N^6)
Sorry for the typo

Joachim Mertz
First  |  Prev  | 
Pages: 1 2 3 4
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.