Re: Discussion regarding Mr. Diabys algorithm
Radosław Hofman
>> show anything: Integer Programming is NP-complete anyway..
>>
>> A.L.
>
> Thank you for having commopn sense and expressing it.
> //MD
>
Hi,
You do not read what other write. A.L. wrote why your method cannot be proof
for P=NP pointing that mine "discovers" were made YEEEEAAAARS ago!
What is quite funny that you have used papers which are pointed to be
showing why your algorithm will not work to justify your method... :-)))
Cheers,
Radek Hofman
Radosław Hofman
--------------------------------------------------------------------------------
From: Radosław Hofman [mailto:rad...@teycom.pl]
Sent: Monday, November 06, 2006 8:22 AM
To: 'Moustapha Diaby'
Cc: tc...@alum.mit.edu; sgu...@genesyslab.com; '#DEEPAK PONVEL CHERMAKANI#';
'Radosław Hofman'
Subject: RE: Tim Chow's doubt
Wow,
And I thought that I'm writing article about nothing important, because
Diaby's algorithm cannot be used on instances of n>50 due to worlds
computational resource limitations, but... :) I shall join discussion :)
First, to appreciate my position, think of it this way: you are in the
context of a discussion about wildlife; you make the statement that "monkeys
climb trees"; someone comes to you, and says "I don't believe you! ...what
do you mean by "tree"?""; you do your best to explain "tree"; then the
person comes back to you at a later time and goes: "...ahhhh! I have done
some work and now know exactly what is "tree." You are wrong because there
are trees that are really huge and cannot be therefore, climbed by monkeys!"
...
==> following your example - you claim that a monkey is capable of climbing
to top of EVERY tree, and my position is that if a tree is over 40.000 feet
high then it simply cannot breath there :). And I refuse to accept your
argument that "you have not seen such tree"
I am going to tell you again: Mr. Hofman *really* does not have a clue...
==> or maybe (what was pointed by Tim Chow) you do not understand meaning of
mine objection
May be you should ask him to apply his reasoning (I believe around page 25
of his document) to the assignment problem polytope and explain why the
constraints of this polytope cannot express all the possible assignments
when the problem size is large, and let you know.
==> Have you forgotten that I attached source code of program generating
counter example flow with all equations from your paper? Have you ran it?
==> I asked you to solve instance for n=32 showing that I have proof that
your method will fail for such n. You didn't point any errors in mine
counter example and wrote that "it is to large for you to solve, but your
method surely will solve it"... naive, isn't it?
For your benefit, I am going to suggest the following: forget the
mathematics in my paper. Rather, try to get an intuitive sense of what is
going on: Take a piece of paper; draw Graph G; chose an arc from stage 1;
let it be (a, 1, b), assume there is a flow of L ( L > 0) on it. Now because
of constraints 2.14, that flow will never flow again on an arc (a, * ,*) or
(*, *, b) (except when it is flowing out of node (b, 2). As it is flowing
out of node (b, 2), suppose it splits between nodes (c, 3) and (d, 3). Then
because of the relations between the z's and y's and constraints 2.14, the
portion that goes into (c,3) will never again flow onto any arc involving
cities a, b, or c (except when leaving (c, 3)). Similarly, for the flow into
(d, 3). Since flows must be also connected and conserved, this creates the
patterns formalized in Proposition 2, regardless of the number of cities.
==> I have tried this method - and you are right - I could not find example
even for x_isj. Then I used Soplex and... wow - LP solver found something
exactly fitting to all restrictions but consisting on non TSP tours. That is
fig 2 in my paper. If you understand why it fits to every restriction for
x_isj model then you will be able to imagine how to "draw" this thing for
larger instances defeating next dimensions (y_isjupv and z_isjupvkrt).
==> Have you considered graph from figure 13? This is counter example for
your method - please pick up any arc and try to find one equation from your
BLP model it will violate. Only one violated is 2.13 but you find it useless
to put it in BLP model. Even if 2.13 was stronger and included in model then
your model would be defeated by greater n (see fig 15). You have to
UNDERSTAND how this examples are built, then you can say why even if you
mention all restriction for 3 or more dimensions it still will not work.
In Mr. Hofman's "counter-example," either flow from a given arc (k, r, t)
flows back on an arc (k, s, *) or (*, s, t) at stage s > r (there would then
be y-variables y(krtks*) or y(krt*st) that would be positive because of flow
conservation). But, if that is the case, then constraints 2.14 would be
violated. If that is not the case, then because of flow connectivity and
conservation, Proposition 2 of my paper is true.
==> You don't understand *a bit* how this flow is built! Please download and
run my program - it will generate all variables, all y's and z's - you will
see that there is no back flow. There is flow from for example:
5->6; 6->7; 7->8; 8->9; 9->10; 10->7; 7->8; 8->9; 9->10; 10->7.... and so on
we then have
y_5,5,6,6,6,7; y_5,5,6,7,7,8; y_5,5,6,8,8,9; y_5,5,6,9,9,10;
y_5,5,6,10,10,7...
==> But flow following 6->7 is different:
6->7; 7->8; 8->9; 9->10; 10->11; 11->8; 8->9; 9->10; 10->11; 11->8... and so
on
==> we then have
y_6,6,7,7,7,8; y_6,6,7,8,8,9; y_6,6,7,9,9,10; y_6,6,7,10,10,11;
y_6,6,7,11,11,8...
==> Which equation is violated? NONE!!!
==> Combining many such flows makes exactly same flow reaching every node
from valleys B and C, and persisting flow consistency at every node and arc.
If you had downloaded variables values than you would stop writing not true
suppositions. Please - try to understand HOW this example is built.
Bottom line: there is no need to waste your time with Mr. Hoffman's naive
constructs. It is a pile of gibberish as I have said before.
==>Well... I don't understand Quantum mechanics... "it is a pile of
gibberish" - isn't it? :-)))))
Cheers,
Radek Hofman
Radoslaw Hofman
A.L. wrote:
> >Yes, it is. But if theer is an algorithm, then there must be a proof
> >that the minimum cost is actulally the cost of the problem that has
> >been originally formulated.
>
> i.e. that this is cost of a tour, but not, say 5 tours or any other
> object...
Diaby claims there is such proof in his paper... No one yet convinced
him that he is wrong :)
Cheers,
Radek Hofman
A.L.
<rad...@teycom.pl> wrote:
>>> Proving that TSP is equivalent to Integer Linear Programming doesn't
>>> show anything: Integer Programming is NP-complete anyway..
>>>
>>> A.L.
>>
>> Thank you for having commopn sense and expressing it.
>> //MD
>>
>
>Hi,
>
>You do not read what other write. A.L. wrote why your method cannot be proof
>for P=NP pointing that mine "discovers" were made YEEEEAAAARS ago!
>
Again, historically, attempts to use LP to solve TSP and thus
proving that P=LP appear as frequently as attempts to provide
elementary proof of Fermat Theorem. One such attempt is discussed in
Yanakakis paper and dates (as I recall) 1986 or 1987.
A.L.
moustap...@business.uconn.edu
>
> ==> You don't understand *a bit* how this flow is built! Please download and
> run my program - it will generate all variables, all y's and z's - you will
> see that there is no back flow. There is flow from for example:
>
> 5->6; 6->7; 7->8; 8->9; 9->10; 10->7; 7->8; 8->9; 9->10; 10->7.... and so on
>
> we then have
>
> y_5,5,6,6,6,7; y_5,5,6,7,7,8; y_5,5,6,8,8,9; y_5,5,6,9,9,10;
> y_5,5,6,10,10,7...
>
> ==> But flow following 6->7 is different:
>
> 6->7; 7->8; 8->9; 9->10; 10->11; 11->8; 8->9; 9->10; 10->11; 11->8... and so
> on
>
> ==> we then have
>
> y_6,6,7,7,7,8; y_6,6,7,8,8,9; y_6,6,7,9,9,10; y_6,6,7,10,10,11;
> y_6,6,7,11,11,8...
>
> ==> Which equation is violated? NONE!!!
>
> ==> Combining many such flows makes exactly same flow reaching every node
> from valleys B and C, and persisting flow consistency at every node and arc.
> If you had downloaded variables values than you would stop writing not true
> suppositions. Please - try to understand HOW this example is built.
What happened to the z-variables?
Radoslaw Hofman
with their values. It takes no more then couple of minutes:
http://www.teycom.pl/diaby/variables_z.zip
You can serch this file and find out answer - I was just showing idea that
your "back flow" restriction can be deceeved :-))
Cheers,
Radek Hofman
Uzytkownik <moustap...@business.uconn.edu> napisal w wiadomosci
news:1162817329....@b28g2000cwb.googlegroups.com...
moustap...@business.uconn.edu
> You can serch this file and find out answer - I was just showing idea that
> your "back flow" restriction can be deceeved :-))
>
OK, I have let myself be drawn into this again... I have downloaded. I
do not see what you see.
Why don't you just point out one example from your numbers where the
"back flow" restriction is deceived?
Radoslaw Hofman
Examples for 5,5,6 (after space there is FLOW - it should be considered as
X/2592):
y_5_5_6_5_5_6 144
y_5_5_6_6_6_11 48
y_5_5_6_6_6_7 48
y_5_5_6_6_6_15 48
y_5_5_6_7_7_12 16
y_5_5_6_7_7_16 16
y_5_5_6_15_7_12 16
y_5_5_6_15_7_16 16
y_5_5_6_11_7_12 16
y_5_5_6_11_7_16 16
y_5_5_6_15_7_8 16
y_5_5_6_7_7_8 16
y_5_5_6_11_7_8 16
y_5_5_6_16_8_9 24
y_5_5_6_8_8_9 24
y_5_5_6_8_8_13 24
y_5_5_6_16_8_13 24
y_5_5_6_12_8_9 24
y_5_5_6_12_8_13 24
and so on...
Now z's:
z_5_5_6_6_6_11_11_7_12 16
z_5_5_6_6_6_11_11_7_16 16
z_5_5_6_6_6_11_11_7_8 16
z_5_5_6_6_6_15_15_7_8 16
z_5_5_6_6_6_15_15_7_12 16
z_5_5_6_6_6_15_15_7_16 16
z_5_5_6_6_6_7_7_7_8 16
z_5_5_6_6_6_7_7_7_12 16
z_5_5_6_6_6_7_7_7_16 16
z_5_5_6_6_6_11_16_8_9 8
z_5_5_6_6_6_11_12_8_13 8
z_5_5_6_6_6_11_8_8_9 8
z_5_5_6_6_6_11_16_8_13 8
z_5_5_6_6_6_11_12_8_9 8
z_5_5_6_6_6_11_8_8_13 8
z_5_5_6_6_6_15_12_8_9 8
z_5_5_6_6_6_15_8_8_13 8
z_5_5_6_6_6_15_12_8_13 8
z_5_5_6_6_6_15_8_8_9 8
z_5_5_6_6_6_15_16_8_9 8
z_5_5_6_6_6_15_16_8_13 8
z_5_5_6_6_6_7_16_8_13 8
z_5_5_6_6_6_7_16_8_9 8
z_5_5_6_6_6_7_12_8_9 8
z_5_5_6_6_6_7_8_8_13 8
z_5_5_6_6_6_7_8_8_9 8
z_5_5_6_6_6_7_12_8_13 8
And so on...
Can't you use simple Ctrl+F on notepad?
Cheers,
Radek Hofman
Uzytkownik <moustap...@business.uconn.edu> napisal w wiadomosci
news:1162823035....@b28g2000cwb.googlegroups.com...
moustap...@business.uconn.edu
Ok, I have looked at it. Where does flow from (5, 5, 6) "back-flow"
back to either city 5 or 6?
tc...@lsa.umich.edu
Looks like A.L. doesn't read what others write either...
A.L., quick multiple choice quiz for you:
1. Who is claiming that LP can be used to solve the TSP?
a. Hofman
b. Diaby
2. Who in this discussion first pointed out that such attempts are doomed?
a. Hofman
b. Diaby
c. A.L.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
moustap...@business.uconn.edu
>
> Looks like A.L. doesn't read what others write either...
>
> A.L., quick multiple choice quiz for you:
>
> 1. Who is claiming that LP can be used to solve the TSP?
> a. Hofman
> b. Diaby
>
> 2. Who in this discussion first pointed out that such attempts are doomed?
> a. Hofman
> b. Diaby
> c. A.L.
Let's create distractions from the question I put to Mr. Hofman in my
last post (which is the real issue if we want to end this nonsense):
In the example he posted, where does flow from arc (5,5,6) flow back to
either city 5 or 6?
//MD
A.L.
>In article <dhauk2deompf632o4...@4ax.com>,
>A.L. <alew...@fala2005.com> wrote:
><On Mon, 6 Nov 2006 09:05:28 +0100, "Radosław Hofman"
><<rad...@teycom.pl> wrote:
><>You do not read what other write. A.L. wrote why your method cannot be proof
><>for P=NP pointing that mine "discovers" were made YEEEEAAAARS ago!
><
><Again, historically, attempts to use LP to solve TSP and thus
><proving that P=LP appear as frequently as attempts to provide
><elementary proof of Fermat Theorem. One such attempt is discussed in
><Yanakakis paper and dates (as I recall) 1986 or 1987.
>
>Looks like A.L. doesn't read what others write either...
>
>A.L., quick multiple choice quiz for you:
>
>1. Who is claiming that LP can be used to solve the TSP?
> a. Hofman
> b. Diaby
>
>2. Who in this discussion first pointed out that such attempts are doomed?
> a. Hofman
> b. Diaby
> c. A.L.
I don't care. Although this thread is quite amusing, I have figured
it out that this one is even more:
http://www.alaska.net/~clund/e_djublonskopf/Flatearthsociety.htm
A.L.
deepakc
We eagerly await your reply to Diaby's latest Question.
Diaby's question is "In the example you posted, where does flow from
arc (5,5,6) flow back to either city 5 or 6 ??? "
-Deepak
deepakc
I guess Sir Radoslaw must be in the Train now. Thats why he has not yet
responded to Diaby's Query.
I am sure he will respond to Diaby's Question, as soon as he reaches
home/office.
I am off to sleep now. Here it is going to become mid-night, in my part
of the world.
Good nite everyone.
-Deepak
deepakc
Its morning here now, and there is no further posting at GoogleGroups.
I am more refreshed, and now I understand the meaning of AL's Joke on
"Flat Earth Society", and I hope Sir Diaby understands it too.
To make it clearer...........Sir Diaby must look at the full file (not
at just the posting of Radoslaw), and Diaby must use "Ctrl+F" (or
"find" function of Notepad), in order to finally locate where the
"backflow" occurs.
I hope Sir Diaby has already done that, and is able to see that
"backflow" actually does occur.
The work (both theoretical and experimental) of Sir Radoslaw is
excellent, and deserves appreciation (in fact Sir Tim Chow of MIT has
said it before I said it).
Using common sense and confidence, Sir Radoslaw has managed to poke a
hole in Diaby's "monstrously complex" model. I have never seen any
paper with a model as huge and complex, as Diaby's model.
Anyway, we will now wait and see what Diaby has to say about the "full
picture".
Thanks,
-Deepak
moustap...@business.uconn.edu
I have looked over the whole file and done "ctrl F" on it all thru.
I did not find any case of "back flow" for arc (5,5,6), not from the
y-variables, nor the z-variables.
So, may be you or Hofman can highlight a couple of the back-flows you
see (it is possible to open the file with MS Word) and post that file?
By the way, why haven't you posted my last email to you also?
//MD
deepakc
Hofman will respond to you soon, regarding the experiments.
I am pasting our latest email conversation, in which you have responded
to the two Questions. I find your answers to both QUESTION 1 and
QUESTION 2, very unsatisfying, because what you have told me is the
formulation, and you are repeating Propositions that are already
mentioned in your paper. You mention phrases like "I am quite
comfortable", "thats what the mathematics say", "I do not have the
paper in front of me".
Anyway, never mind those phrases. The underlying issue is that You have
still not EXPLICITLY PROVED answers to the fundamentals QUESTION 1 and
QUESTION 2.
Pls read our email conversation pasted below.
Thanks, -Deepak
-----Original Message-----
From: Moustapha Diaby [mailto:Moustap...@business.uconn.edu]
Sent: Mon 11/6/2006 10:53 AM
To: #DEEPAK PONVEL CHERMAKANI#
Subject: RE: Tim Chow's doubt - Hofman's 2 Questions on Diaby's Algo
remain unanswered
Deepak - I think you misunderstand the purpose of my communicatio with
you... But, it is all the same... See my answers below. //MD
ANSWER TO QUESTION 1:
The issue is formally addressed by Proposition 1 of the paper: No TSP
tour is excluded from the feasible set of the IP formulation (see
Proposition 1 and its proof). The feasible set of the LP relaxation
includes that of the IP and must therefore include all the TSP tours.
ANSWER TO QUESTION 2:
No. If you examine the positive components of any feasible solution you
must find that they have the structure described in Proposition 2 (That
is what the mathematics say -- And, I am quite comfortable with the
correctness). With such a structure each vertex of the polytope
described by the constraints corresponds to a TSP tour (Note I am
saying "corresponds to", not *is*: the solution needs to be properly
"interpreted"). This is what is proven in either Proposition 3 or 4 (I
don't have the paper in front of me, but its the proposition about
BFS's and TSP tours). Each corner of the polytope corresponds to a TSP
but has several alternative algebraic representations in terms of what
we call in LP lingo, Basic Feasible Solutions. So, everything you are
asking for above, is already in the paper.
-----Original Message-----
From: #DEEPAK PONVEL CHERMAKANI# [mailto:dee...@pmail.ntu.edu.sg]
Sent: Sun 11/5/2006 10:56 PM
To: Moustapha Diaby
Cc: tc...@alum.mit.edu; rad...@teycom.pl; sgu...@genesyslab.com
Subject: RE: Tim Chow's doubt - Hofman's 2 Questions on Diaby's Algo
remain unanswered
Dear Sir Diaby,
I have carefully read the below argument of yours, regarding the flows.
My Brain concludes that "given the angle of your argument, what you say
sounds true"
But Hofman's argument sounds more convincing on the overall picture,
because we have still not yet received an answer from you on Hofman's 2
unanswered Questions of his argument.
Hofman's 2 Questions are:-
QUESTION ONE: - Is your Algorithm capable of pinpointing all (N!) TSP
tours, if every tour has equal length ??? The answer is obviously NO,
because in the overall picture, your Algorithm involves a Polynomial
number of variables. I know that Linear Programming guarantees to find
atleast one optimal tour, within Polynomial time, by walking across the
vertexes of your new Assignment Polytope that has Polynomial size.
However, then that leads to Question 2.
QUESTION TWO: - Is it possible for your Algorithm to give the correct
solution for the CONVEX COMBINATION OF PATHS, but where EACH SINGLE
PATH IN THIS COMBINATION is a wrong solution ??? According to me, this
is possible because you have not explicitly proved this anywhere in
your paper. Yes, I will believe you only if you write a new proof in
your paper, stating that it is never possible for your Algorithm to
give the correct solution for the CONVEX COMBINATION OF PATHS, but
where EACH SINGLE PATH IN THIS COMBINATION is a wrong solution.
I think that until we get answers to Hofman's 2 unanswered Questions
above, we will never be able to agree with your Algorithm, even though
we may agree with certain angles of your argument.
So if you really want our support, and the world's support, I think you
will have to give EXPICIT proofs answering both QUESTION ONE and
QUESTION TWO.
We hope you will be able to give us/world the EXPLICIT answers.
Thanks,
-Deepak
Radoslaw Hofman
> Ok, I have looked at it. Where does flow from (5, 5, 6) "back-flow"
> back to either city 5 or 6?
>
Hi,
No, it never does. That's the point :)
Algorithm building this flow is very simple
It picks up an arc isj
- for every folowing layer it lists all "possible" arcs (upv) flow may
reach
* checking is done in check_y procedure for (isj,upv)
* check_y disables any kind of back-flow
- then total flow through isj is divided proportionaly to all possible
upv's
Analogical with z's - we pick up any y with isj, upv arcs. Then for every
following layers we pick up list of arcs and mark "possible" arcs (using
check_z(isj,upv,krt)) - then we divide y proportionaly.
Such algorithm prepares flow meeting:
- no back flows
- consistency at every node
- consisteny on suceeding layers
check_z(isj,upv,krt) is simple:
return ((check_y(isj,upv))&&(check_y(isj,krt))&&(check_y(upv,krt)));
If you look at check_y(isj,upv) I check there all restrictions from 2.14
where are: no broken flows, no back-flow, no flow on previous layers. no
flow on same layer ect.
This means that when algorithm is looking for possible nodes at some layer
for picked up arc it marks only LEGAL arcs. Becouse we have many paths
through every layer it is possible to prepare LEGAL flow for any picked arc
or pair of arcs to exit point, and because we are using all path
simultanously they sum up to deceeve every sum-based restriction.
Maybe you will study listing of mine program - I was hoping to prepare clear
code, I use variables names as in your paper so it should be very easy for
you.
Cheers,
Radek Hofman
Radoslaw Hofman
Uzytkownik "deepakc" <dee...@pmail.ntu.edu.sg> napisal w wiadomosci
news:1162828041....@e3g2000cwe.googlegroups.com...
Hi,
I haven't noticed that question was put also here so I repeat my answer (it
is 8 AM in my place, so unfortunatelly we all live in different zones).
--------------------------------------------
Radoslaw Hofman
> I have looked over the whole file and done "ctrl F" on it all thru.
>
> see (it is possible to open the file with MS Word) and post that file?
Hi, sorry but there are no back-flows there :). If they were this counter
example wouldn't fit to all restrictions!
Why do you think they are? Because it is impossible that without "back
flows" all other restrictions are met? :-)
It is possible... Again I refer to source code - look at check_y procedure
Cheers,
Radek Hofman
Radoslaw Hofman
Uzytkownik "deepakc" <dee...@pmail.ntu.edu.sg> napisal w wiadomosci
news:1162875710.8...@m7g2000cwm.googlegroups.com...
> -----Original Message-----
> From: Moustapha Diaby [mailto:Moustap...@business.uconn.edu]
> ANSWER TO QUESTION 1:
> The issue is formally addressed by Proposition 1 of the paper: No TSP
> tour is excluded from the feasible set of the IP formulation (see
> Proposition 1 and its proof). The feasible set of the LP relaxation
> includes that of the IP and must therefore include all the TSP tours.
This is true until we are talking about IP. If we change from IP to LP then
it is impossible. LP may provide answer "lying" outside original polytope.
> ANSWER TO QUESTION 2:
> No. If you examine the positive components of any feasible solution you
> must find that they have the structure described in Proposition 2 (That
> is what the mathematics say -- And, I am quite comfortable with the
> correctness). With such a structure each vertex of the polytope
> described by the constraints corresponds to a TSP tour (Note I am
> saying "corresponds to", not *is*: the solution needs to be properly
> "interpreted"). This is what is proven in either Proposition 3 or 4 (I
> don't have the paper in front of me, but it's the proposition about
> BFS's and TSP tours). Each corner of the polytope corresponds to a TSP
> but has several alternative algebraic representations in terms of what
> we call in LP lingo, Basic Feasible Solutions. So, everything you are
> asking for above, is already in the paper.
Meaning of question is (forget about polytope, vertexes and other): is it
possible that we assign some values having nothing to do with TSP tours, but
we use so much of them that we are able to meet all restrictions from BLP
model. You didn't prove that this is impossible.
Getting back to polytope - please stop thinking in way of "structure"... If
you allow many solutions at once you cannot have exact picture of all flows
through arc, pair of arcs or even triple of arcs. Imagine that you are
picking up y variable (pair of arcs) - is it possible that flow thru rest of
graph is switching between groups of nodes forming path which has nothing to
do with TSP tour? Of course it is possible, because you cannot create any
kind of restrictions to prevent such z variables:
z_isj_upv_A,r0,B
z_isj_upv_B,r1,C
z_isj_upv_C,r2,A
...
It preserves all restrictions for consistency of flow and following layers
having same flow being consequence of picked pair.
Is this too hard to imagine that if we take enough of such paths then we
will be able to get them together and:
Variables y and z may be considered in such way:
Y_isj_*:
- model with x_upv but whole flow must go through isj
Z_isj_upv_*
- model with x_krt but whole flow must go through isj and upv
If then best possible model for x_* can be deceived (what is shown on figure
2 in my paper) then building up example for y is nothing more but taking
many illegal flows such that each conducts whole flow through one of arcs
and combine it together. Making counter example for z is analogical - get
many models for y_isj_upv and combine the together.
If these flows are similar in some way then if we combine them we obtain
perfectly balanced flow, for all possible restrictions but having nothing to
do with TSP tour. To prove it we may show that overall cost of such flow is
lower then optimal TSP tour.
Cheers,
Radek Hofman
deepakc
I agree with you, regarding what you have said above. From theory, I am
100% sure that Diaby's Algorithm is capable of outputting a solution
that is:-
1.) not a TSP tour.
2.) not optimal, if it is a TSP tour
Do you think you will be able to show us some computer-implementation
results (hopefully by the end of this week), which will clearly show
this to the world ??
Or if not by end of this week, could you please give us an estimate, of
how much more time will be necessary.
Your work will be very crucial, in proving to the world, that Diaby's
super-massive model, has a hole. :-)
Thanks,
-Deepak
deepakc
I would like to apologize to Sir Hofman, because we do not need any
more Computer Implementation.
We do not need any more Proof, and we do not need any more
Computer-Implementation, because Hofman has already shown this using
the Counter-Example, in his paper
"http://www.teycom.pl/docs/Report_on_article_P_eq_NP.pdf"
Using the counter-example, Sir Hofman has already shown everyone that
it is possible to generate a solution, whose length is less than the
optimal length.
GOSHHH, I do not understanding why are we even having this long
discussion !!!
Because Hofman's paper & counter-example, has already proved beyond
doubt, that it is possible for Diaby's Algorithm to give ABSOLUTELY
WRONG SOLUTIONS.
Does Diaby have any comments on the counter-example given in
http://www.teycom.pl/docs/Report_on_article_P_eq_NP.pdf ???
deepakc
I would like to apologize to Sir Hofman, because we do not need any
more Computer Implementation.
We do not need any more Proof, and we do not need any more
Computer-Implementation, because Hofman has already shown this using
the Counter-Example, in his paper
"http://www.teycom.pl/docs/Report_on_article_P_eq_NP.pdf"
Using the counter-example, Sir Hofman has already shown everyone that
it is possible to generate a solution, whose length is less than the
optimal length.....and therefore this solution is WRONG.
Radoslaw Hofman
> Do you think you will be able to show us some computer-implementation
> results (hopefully by the end of this week), which will clearly show
> this to the world ??
Hi,
You can download this from address:
http://www.teycom.pl/diaby/diaby_counter_example.zip
This is program in perl, which is avaliable for almous every platform (I use
ActivePerl for windows).
This program
1. Generates all variables with their values and stores them in
variables_z.txt file (33 MB)
2. Generates LPT file for any LP solver (169 MB)
Once file with variables was generated it can be used in next runs of
program (to avoid wasting time to generate variables every time).
It generates Diaby's BLP model with equations numbers from last version of
article. Only equations containing at least one non-zero variable are
generated - other are omitted.
Very important - before equation is printed it may be evaluated - variables
are substituted with their values and equality is checked - of course each
equation is fulfilled :).
LPT file may be loaded to SoPlex solver, which confirms that solution is
optimal for presented model, and overall cost is lower then optimal TSP
tour.
To run program simply type:
perl program_file_name.pl >output.lpt
Once variables are generated you may assign value 1 to $debug variable and
program will produce information about every equation checking, but it
produces lot's of output. You may run soplex instead (remember that file for
soplex must be generated with $debug=0).
Running time is about 3 h on mine laptop.
Cheers,
Radek Hofman
moustap...@business.uconn.edu
On Nov 7, 5:52 am, "Radoslaw Hofman" <rad...@teycom.pl> wrote:
> Uzytkownik "deepakc" <deep...@pmail.ntu.edu.sg> napisal w wiadomoscinews:1162890080.5...@b28g2000cwb.googlegroups.com...
OK, I am now completely satisfied that neither of you has a clue (at
best)... You are free to go on with your nonsense. Please, just don't
clug up my email with it any more.
//MD
deepakc
If you can convince us that you are correct, I assure you that we will
nominate you for Nobel Prize.
Please calmly convince us, with what is exactly wrong with Hofman's
Counter-Example.
I looked at your previous posts, saying that Hofman's work is
"gibberish", and that Hofman has formulated your Model wrongly in his
PERL program.
Is that really true ???
Pls tell us which part of his PERL program is wrong.
I will strongly repeat again...Please calmly convince us, with what is
exactly wrong with Hofman's Counter-Example in
"http://www.teycom.pl/docs/Report_on_article_P_eq_NP.pdf"
If you can convince us that you are correct, and that Hofman is wrong,
I assure you that we will nominate you for Nobel Prize.
-Deepak
deepakc
If you can convince us that you are correct, I assure you that we will
nominate you for Nobel Prize.
Please calmly convince us, with what is exactly wrong with Hofman's
Counter-Example.
I looked at your previous posts, saying that Hofman's work is
"gibberish", and that Hofman has formulated your Model wrongly in his
PERL program.
Is that really true ???
Pls tell us which part of his PERL program is wrong.
I will strongly repeat again...Please calmly convince us, with what is
exactly wrong with Hofman's Counter-Example in
"http://www.teycom.pl/docs/Report_on_article_P_eq_NP.pdf".
A.L.
wrote:
>
>The work (both theoretical and experimental) of Sir Radoslaw is
>excellent, and deserves appreciation (in fact Sir Tim Chow of MIT has
>said it before I said it).
>
>Using common sense and confidence, Sir Radoslaw has managed to poke a
>hole in Diaby's "monstrously complex" model. I have never seen any
>paper with a model as huge and complex, as Diaby's model.
These are not scientific arguments, especially Mr. Chow's
affiliation with MIT doesn't guarantee that he must be automatically
right. Complexity of Mr. Diaby's model has nothing common with
potential correctness or not. I have seen more complex models, by
the way. "Common sense and confidence" also have a little scientific
power.
Discussion is drifting more and more towards non-merit style....
Mr. Deepak, maybe you could provide some scientific contributions
beyond manifesting that you support this or that side?...
A.L.
deepakc
The "event" of "backflows" are not occurring, thats why Hofman earlier
could not identify them.
However, some other "event" is happenning, which causes your Algorithm
to give a correct COMBINATION OF PATHS, where each SINGLE PATH IN THIS
COMBINATION is wrong.
We can conclude with 100% certainity that there is such an "event",
because otherwise your Algorithm would not produce wrong results for
the 32-node TSP in
"http://www.teycom.pl/docs/Report_on_article_P_eq_NP.pdf"
What exactly that "event" is, Hoffman does not know (and even we do not
know). And pls understand that it is not Hoffman's job to try to
describe this "event". His job is only to point out the fact that there
is such an "event". And Hoffman has successfully done that via his
paper.
Hofman's earlier raw guess was that this "event" was "backflows", that
was why he mentioned in this GoogleGroups that it was "backflows".
Now we know that this "event" is not "backflows", but something else.
I will repeat strongly that ..........We can conclude with 100%
certainity that there is such an "event", because otherwise your
Algorithm would not produce wrong results for the 32-node TSP in
"http://www.teycom.pl/docs/Report_on_article_P_eq_NP.pdf"
-Deepak
deepakc
deepakc
Here is my scientific argument: -
The "event" of "backflows" are not occurring, thats why we earlier
"http://www.teycom.pl/docs/Report_on_article_P_eq_NP.pdf".
-Deepak
A.L.
wrote:
>Ok here is my scientific contribution:-
>
>
>Dear Sir Diaby,
>
>The "event" of "backflows" are not occurring, thats why Hofman earlier
>could not identify them.
OK, Mr. Deepak... Here is a theorem from Yannakakis paper, quote:
Theorem 2. The TSP polytope cannot be
expressed by a polynomial size symmetric LP.
end quote.
Make The Humaninty service and prove that a) The above theorem is
not true, b) It somehow doesnt't apply to the case considered by Mr.
Diaby, c) Is irrelevant for all in this discussion.
The paper I have in mind is the following
EXPRESSING COMBINATORIAL OPTIMIZATION PROBLEMS
BY LINEAR PROGRAMS
(Extended Abstract)
Mihalis Yannakakis
AT&T Bell Laboratories
Murray Hill, NJ 07974
A.L.
deepakc
I will give it my best shot. Can you please immediately send me a PDF
copy of YANNAKAKIS paper, to my email address -
dee...@pmail.ntu.edu.sg
I will immediately get working on the proof. -Deepak
A.L.
wrote:
>The "event" of "backflows" are not occurring, thats why we earlier
>could not identify them.
[...]
>We can conclude with 100% certainity that there
>is such an "event", because otherwise your Algorithm would not produce
>wrong results for
[...]
>What exactly that "event" is, Hoffman does not know (and even we do not
>know). And pls understand that it is not Hoffman's job to try to
>describe this "event"
[..]
>Hofman's earlier raw guess was that this "event" was "backflows", that
>was why he mentioned in this GoogleGroups that it was "backflows". Now
>we know that this "event" is not "backflows", but something else.
>
[...]
>I will repeat strongly that ..........We can conclude with 100%
>certainity that there is such an "event", because otherwise your
>Algorithm would not produce wrong results for the 32-node TSP in
>"http://www.teycom.pl/docs/Report_on_article_P_eq_NP.pdf".
Is this science?...
A.L.
deepakc
Please Let me explain again.
The "event" that is happenning is not "backflows".
The "event" that is happenning is much more complicated, that we cannot
describe it.
But it is not our job to describe the "event", all our job is, is to
prove that there is such an "event" which causes a correct solution to
the COMBINATION OF PATHS, but a wrong solution to each SINGLE PATH IN
THAT COMBINATION.
deepakc
Let me add further, that the reason why the "event" is so complicated,
is perhaps because Diaby's model is so complicated.
But Hofman's paper has already shown that such an "event" exists, via
his 32-node TSP.
Radoslaw Hofman
Dear A.L.... if you know better arguments that others (including me) to
prove that Diaby is wrong why you do not share them with us and only
criticize me, Deepak and others. You pointed out that Yannakakis wrote what
he wrote, and I agree that my paper about "Why LP cannot solve NP-complete
problems" is just a reminder of his work - and do not claim to have America
discovered :).
Problem is that:
- Diaby was reading Yannakakis as well
- he came to conclusion that there is some way to use LP to express his IP
problem
- his work was accepted for three important conferences
So my point is that it is not that obvious that he is wrong. And corollary
from "The TSP polytope cannot be expressed by a polynomial size symmetric
LP" does not lead to direct conclusion that it is impossible to build
polynomial size non-symmetric model for interesting part of polytope and
find correct solution. At least Diaby and reviewers for mentioned
conferences didn't come up to such conclusion.
Most important thing in mine work is direct counter example. If you didn't
believe Diaby is right than it means nothing more for you but proof (maybe
not needed) that you were right. If someone didn't have your knowledge and
didn't come up to conclusion from Yannakakis work then showing counter
example for him is more then best proof that Diaby is wrong.
Cheers,
Radek Hofman
A.L.
wrote:
>Ok Mr. AL,
>
>I will give it my best shot. Can you please immediately send me a PDF
>copy of YANNAKAKIS paper, to my email address -
>dee...@pmail.ntu.edu.sg
>
>I will immediately get working on the proof. -Deepak
>
I don't have this paper on my laptop and will be able to send it you
when I will be back home, what will be about 10 hours from now.
In the meantime you can run full article title through Google
Scholar. You will get some links that will direct you to ACM Portal.
Normally, ACM Portal requires password, but this paper is free.
A.L.
mathisart
> Theorem 2. The TSP polytope cannot be
> expressed by a polynomial size symmetric LP.
symmetric problems are of the form:
max(c^T x | Ax <= b, x >= 0)
Diaby's formulation is:
min(Z_qap(W) ...
and so is worthy of more than cursory dismissal.
In general I agree with you, this has become a pub conversation in
terms of quality. Hoffman spits out z variables, Diaby assumes he's
looking for backtrack ... no one comes back to say what was really
meant, so all I see are a pile of viables. Hoffman's sketch proof is
minimal, his counterexample is vaporware (though it has the appearance
of soundness, I can't step in and say interpret his results into the z
dimension -- too much work and not enough reward).
But Deepak's contribution was at least to get Hoffman and Diaby to
"come to the table" around actual output and facts, rather than
relavent theory neither of them seem capable of expressing. If he
would only continue to dive them towords conversation around those
facts, I would have no issue with his non-technical approach and value
his contribution.
Patricia Shanahan
> Dear Sir Diaby,
>
> If you can convince us that you are correct, I assure you that we will
> nominate you for Nobel Prize.
> Please calmly convince us, with what is exactly wrong with Hofman's
> Counter-Example.
There is no Nobel Prize in mathematics or computer science.
However, the Clay Mathematics Institute has a fund of a million dollars
per problem for solutions to seven designated Millennium Problems. One
of them is P vs. NP.
The catch is "Before consideration, a proposed solution must be
published in a refereed mathematics publication of worldwide repute (or
such other form as the SAB shall determine qualifies), and it must also
have general acceptance in the mathematics community two years after."
http://www.claymath.org/millennium/Rules_etc/
I'm not sure the current publication venue qualifies as a "mathematics
publication of worldwide repute".
Also, Mr. Diaby is going to have to get much better at handling
questioning of his claimed proof before there will be any chance of it
achieving general acceptance in the mathematics community. If leading
mathematicians start taking his claim at all seriously, every line will
be scrutinized to make sure the reasoning is valid.
Patricia
A.L.
<rad...@teycom.pl> wrote:
>
Sorry, I must go to the airport and have little time:
>So my point is that it is not that obvious that he is wrong. And corollary
>from "The TSP polytope cannot be expressed by a polynomial size symmetric
>LP" does not lead to direct conclusion that it is impossible to build
>polynomial size non-symmetric model for interesting part of polytope and
>find correct solution. At least Diaby and reviewers for mentioned
>conferences didn't come up to such conclusion.
Acceptance of paper on a conference is NOT a proof of correctness,
especially such important conference as INFORMS National Conference
where there is no review process at all.
>
>
>Most important thing in mine work is direct counter example. If you didn't
>believe Diaby is right than it means nothing more for you but proof (maybe
>not needed) that you were right. If someone didn't have your knowledge and
>didn't come up to conclusion from Yannakakis work then showing counter
>example for him is more then best proof that Diaby is wrong.
No, I don't believe that Mr. Diaby's work is correct. And yes, this
is not scientific belief , based solely on my intuition and state of
the art. To the extent that I will not spend my time trying to find
counter arguments.
Yes, the way to disprove this is to find counter example. Yes, I
appreciate your effort to do this, and Mr. Deepak's effort too.
A.L.
P.S. Mr. Hofman, are you a student?...
Radoslaw Hofman
Uzytkownik "A.L." <alew...@fala2005.com> napisal w wiadomosci
news:5151l2l72i0d9ol71...@4ax.com...
> P.S. Mr. Hofman, are you a student?...
No, I was some time ago :-) - I am IT industry employee - computational
theory is nothing more then hobby of mine :)
Cheers,
Radek Hofman
A.L.
Then, I am afraid, you working in wrong place....
I am quite impressed by the depth of your knowledge, motivation and
such. In Poznan (Poznan University) there is very strong, worldwide
known team working in Operations Research (Prof. Weglarz and others,
http://www.cs.put.poznan.pl/staff/pjwE.html). Maybe you could
somehow cooperate with them?...
In the meantime: I got third edition of "Combinatorial Optimization:
Theory and Algorithms" by Bernhard Korte and Jens Vygen. Therefore,
second edition will go to The Exile what means the basement. If you
are interested, I can give you second edition as free gift, no
strings attached.
A.L.
Radoslaw Hofman
On Tue, 7 Nov 2006 15:26:19 +0100, "Radoslaw Hofman"
such. In Poznan (Poznan University) there is very strong, worldwide
known team working in Operations Research (Prof. Weglarz and others,
http://www.cs.put.poznan.pl/staff/pjwE.html). Maybe you could
somehow cooperate with them?...
They were my tutors and I cooperate with them - Poznan University of
Technology is my partner in business and for such theoretical thoughts. Even
today I was invited to seminar and presented mine "complexity
considerations".
In work I'm leader of Testing Centre - so to doubt in anything is mine
everyday business :-)) See: http://www.linkedin.com/in/radoslawhofman
In the meantime: I got third edition of "Combinatorial Optimization:
Theory and Algorithms" by Bernhard Korte and Jens Vygen. Therefore,
second edition will go to The Exile what means the basement. If you
are interested, I can give you second edition as free gift, no
strings attached.
Wow, of course I'm... How can I obtain such copy?
Thanks,
Radek Hofman
A.L.
<rad...@teycom.pl> wrote:
>
>Uzytkownik "A.L." <alew...@fala2005.com> napisal w wiadomosci
>
> In the meantime: I got third edition of "Combinatorial Optimization:
> Theory and Algorithms" by Bernhard Korte and Jens Vygen. Therefore,
> second edition will go to The Exile what means the basement. If you
> are interested, I can give you second edition as free gift, no
> strings attached.
>
>Wow, of course I'm... How can I obtain such copy?
OK, we will switch to e-mail....
A.L.
tc...@lsa.umich.edu
A.L. <alew...@fala2005.com> wrote:
>On Tue, 7 Nov 2006 14:53:54 +0100, "Radoslaw Hofman"
><rad...@teycom.pl> wrote:
>>So my point is that it is not that obvious that he is wrong. And corollary
>>from "The TSP polytope cannot be expressed by a polynomial size symmetric
>>LP" does not lead to direct conclusion that it is impossible to build
>>polynomial size non-symmetric model for interesting part of polytope and
>>find correct solution. At least Diaby and reviewers for mentioned
>>conferences didn't come up to such conclusion.
>
>Acceptance of paper on a conference is NOT a proof of correctness,
>especially such important conference as INFORMS National Conference
>where there is no review process at all.
You're missing the point, which is that simply citing Yannakakis's paper
doesn't work, due to the loophole embedded in the word "symmetric."
If you actually read Yannakakis's paper, you'll notice that he carefully
points out this loophole himself. Diaby is aware of this. When this
point came up the last time around (when David Moews posted his analysis
of Diaby's paper), Diaby kept insisting that this loophole explained
why his work was not inconsistent with that of Yannakakis. Now, Moews
showed that in fact you could use Yannakakis's result to refute Diaby,
but the derivation was not entirely trivial, and Diaby refused to accept
Moews's argument.
Therefore, Hofman has taken the further step of explicitly working out a
counterexample in this particular case.
I'm perplexed that you keep describing this discussion as unscientific,
and make comparisons to the Flat Earth, and so forth. Hofman has been
very clear in his responses to Diaby, modulo his slight goof about
"backflows" (which he quickly admitted to once it was pointed out),
and for a while at least, Diaby was following his logic too. I hope
Diaby sticks it out a little bit longer (despite his recent remark)
since it seems that he's almost at the point where he might see his
error.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
tc...@lsa.umich.edu
mathisart <artr...@gmail.com> wrote:
>In general I agree with you, this has become a pub conversation in
>terms of quality. Hoffman spits out z variables, Diaby assumes he's
>looking for backtrack ... no one comes back to say what was really
>meant, so all I see are a pile of viables. Hoffman's sketch proof is
>minimal, his counterexample is vaporware (though it has the appearance
>of soundness, I can't step in and say interpret his results into the z
>dimension -- too much work and not enough reward).
Vaporware? He's provided source code and an explicit counterexample that
you can download and run yourself. How much more concrete can you get?
If you find it too much work and not enough reward, that's fair enough.
But then I don't think you should accuse him of vaporware.
>But Deepak's contribution was at least to get Hoffman and Diaby to
>"come to the table" around actual output and facts, rather than
>relavent theory neither of them seem capable of expressing. If he
>would only continue to dive them towords conversation around those
>facts, I would have no issue with his non-technical approach and value
>his contribution.
Deepak's contribution has been valuable, no question. But I think
you're being unfair when you say that Hofman is incapable of expressing
his points. It's obvious that English isn't his native language, but
his argument is clear enough. It's only Diaby who is dismissing the
actual output and the facts with broad sweeps of the hand.
deepakc
Dear All,
I would like to post the following important notes/conclusions that I
have made during today's discussion, regarding Diaby's TSP Algorithm,
but which might not necessarily conclude the discussion in this thread:
1.) There does exist some "event", which makes Diaby's Algorithm
capable of generating a correct solution for a COMBINATION OF PATHS,
but where each SINGLE PATH IN THIS COMBINATION is wrong.
2.) The sufficient proof for the existance of such an "event" is the
counter-example described in Sir Radoslaw Hofman's paper in
"http://www.teycom.pl/docs/Report_on_article_P_eq_NP.pdf"
3.) The "event" that causes point 1. to occur is not "backflows".
4.) This "event" may too complex to describe (partly because Diaby's
model is huge, and because the possible "events" in huge model are even
more complex to describe).
5.) Due to the limited capacity of our Human Brain to describe very
complex stuff, it follows that we may not be ever able to describe the
"event"
6.) We need not care about how to describe this "event", because point
1. is sufficient for us to conclude that Diaby's Algorithm is capable
of generating absolutely wrong solutions for the TSP.
Thank you very much.
faithfully,
-Deepak Ponvel Chermakani
---------------
Chairman of MENSA Singapore Brain Modeling SIG
www.mensa.org.sg/sig
---------------
mathisart
> In article <1162907758....@i42g2000cwa.googlegroups.com>,
> mathisart <artr...@gmail.com> wrote:
> >In general I agree with you, this has become a pub conversation in
> >terms of quality. Hoffman spits out z variables, Diaby assumes he's
> >looking for backtrack ... no one comes back to say what was really
> >meant, so all I see are a pile of viables. Hoffman's sketch proof is
> >minimal, his counterexample is vaporware (though it has the appearance
> >of soundness, I can't step in and say interpret his results into the z
> >dimension -- too much work and not enough reward).
>
> Vaporware? He's provided source code and an explicit counterexample that
> you can download and run yourself. How much more concrete can you get?
>
> If you find it too much work and not enough reward, that's fair enough.
> But then I don't think you should accuse him of vaporware.
That's fair enough, and yes the main issue I have with Hofman's work is
I have too much "homework" to see it. :) Vaporware is something I
used immaturely, I must admit, out of frustration (as much with Diaby's
not working with Hofman's actual implementation, as Hofman's sometimes
difficult, generalization).
> >But Deepak's contribution was at least to get Hoffman and Diaby to
> >"come to the table" around actual output and facts, rather than
> >relavent theory neither of them seem capable of expressing. If he
> >would only continue to dive them towords conversation around those
> >facts, I would have no issue with his non-technical approach and value
> >his contribution.
>
> Deepak's contribution has been valuable, no question. But I think
> you're being unfair when you say that Hofman is incapable of expressing
> his points. It's obvious that English isn't his native language, but
> his argument is clear enough. It's only Diaby who is dismissing the
> actual output and the facts with broad sweeps of the hand.
It is not his english I object to! Hofman assumes his implementation
is correct. Diaby assumes his logic is sound. It's hard to make
anything clear, with so much assumption.
deepakc
thread.
Dear All,
I seem to have missed out a lot of history. So far I only knew about
Sir Radoslaw Hofman. Just today morning, I read the posting of Sir Tim
Chow, regarding Sir David Moews (about whom I did not know earlier).
I googled up Moew's postings, and found this
link:-http://www.archivum.info/comp.theory/2005-05/msg00154.html
If the above link does not work, then please read Moew's posting, which
I have pasted just below this email.
Here Mr. Moews has clearly proved how YANNAKAKIS result can be used to
directly refute Diaby's theorem. I am very sorry for my late discovery,
regarding Mr. Moews excellent result.
Unfortunately, I am unable to see the reply of Sir Diaby, to Moews's
posting, because the archive is too old I guess.
Does anyone know the correct email address of Mr. Moews. Could someone
please request Sir David Moews, to read our entire thread in
googleGroups comp.theory, and then give his expert opinion ???
-Deepak
--------------------------------------------------------
Re: P=NP: Linear Programming Formulation of the TSP
from [David Moews] [Permanent Link][Original]
Subject: Re: P=NP: Linear Programming Formulation of the TSP
From: dmoews@xxxxxxxxxxxxxxxxxxxxx (David Moews)
Date: 5 May 2005 01:53:51 GMT
Newsgroups: comp.theory
Organization: University of Connecticut IMS
Xref: biggoron.nerim.net comp.theory:12049
1. Pat Shanahan,
According to the 12-II-2005 revision of Diaby's paper, I believe
his proposed algorithm for solving the TSP is as follows:
-----
DEFINITION. A ``c.a.s.s. path'' is a choice, for each time in the
set {1, ..., n-1}, of a city in the set {2, ..., n},
such that each city is chosen exactly once.
DIABY TSP ALGORITHM.
INPUT. A number n of cities, and travel costs t_{ij} from
city i to city j, where i and j are in {1, ..., n}.
We assume that t_{ij} is nonnegative, and that it is
infinite if i = j.
OUTPUT. A sequence of numbers C_1, ..., C_n, where C_i is the
city visited at time i in the lowest-cost tour.
STEP 1. Using the t_{ij}'s, define the c_{isj}'s as on p. 6 of the
Diaby
paper.
STEP 2. Find the optimal solution of the linear programming problem
\overline{IP} given on p. 12.
STEP 3. We now look at the variables y_{isjisj}. For some (unique)
c.a.s.s.
path, it will be the case that for each i, s, and j,
y_{isjisj} is
1 if city i is chosen by the path at time s and city j is
chosen at
time s+1, and is 0 otherwise.
STEP 4. For i in {1, ..., n-1}, let C_i be the city chosen at time i
by the c.a.s.s. path determined in Step 3. Let C_n be 1.
-----
I hope that this clarifies the way in which the TSP solution is
recovered
from the LP solution.
2. Prof. Diaby,
Putting aside the typo and the question of the clarity of the
statement and
proof of Proposition 2, my main point is that the correctness of
your
revised algorithm is still in conflict with Yannakakis's result,
which,
assuming that your algorithm is as outlined above, implies that
there is
some input on which it fails. For the record, I will give the
proof below.
3. Tim,
The vagueness of Proposition 2 doesn't make it any more difficult
to
find an example where Diaby's algorithm clearly fails to solve the
TSP. In fact, by 2., there has to be some such example, and
Yannakakis's proof can be used to easily construct one.
Unfortunately,
the counterexample constructed will be rather large (59 cities.)
--
David Moews
dmoews@xxxxxxxxxxxxxxxxxxxxx
-----
PROOF OF 2.---
For each two-element subset {i, j} of {2, ..., n}, define a new
variable
x_{i,j} by
x_{i,j} := y_{i1ji1j} + ... + y_{i(n-2)ji(n-2)j}
+ y_{j1ij1i} + ... + y_{j(n-2)ij(n-2)i}.
[This definition should replace the definition used in
<cmote5$al6$1@xxxxxxxxxxxxxxxxxx>; that definition was incorrect.]
Look at the projection P of the feasible polytope of the LP problem
\overline{IP} onto the x_{i,j}'s. From (2.27), it follows that P
is bounded. Now, let Q be the complete graph with vertices {2,
..., n},
let H be the hypercube defined by the inequalities 0 <= x_{i,j} <=
1
(2 <= i < j <= n), and let V be the set of points { w_q | q a
Hamiltonian
path of Q }, where the value of x_{i,j} at w_q is 1 if the edge
{i,j} is
in q and 0 otherwise. If P is not contained in H, it must have
some
vertex v outside of H; this vertex is clearly not in V. Otherwise,
let P
be contained in H. For each v in V, there is some feasible
solution of
problem \overline{IP} given in Diaby's Proposition 1 which projects
onto
v, so v is in P. Each such v is a vertex of H and therefore must
also be
a vertex of P. Now, take n to be large enough so that the
constructions
in <cmote5$al6$1@xxxxxxxxxxxxxxxxxx> and Theorem 1 in Yannakakis
(J. Computer and System Sciences, 43, 441--466) can be carried out.
The reasoning in <cmote5$al6$1@xxxxxxxxxxxxxxxxxx> then
demonstrates
that P cannot equal the convex hull of V. Therefore, P must have
some
vertex which is not in V. We conclude in either case that P has
some
vertex v' which is not in V. Let K be a supporting hyperplane of P
through v', let K have the equation
\sum_{ {i,j} } k_{i,j} x_{i,j} = u,
and let P be contained in the set
S := {x_{i,j}: \sum_{ {i,j} } k_{i,j} x_{i,j} >= u}.
The equations (2.14) and (2.15) give
\sum_{i, j} y_{isjisj} = 1 for each s in {1,
..., n-2},
and since we assume (p. 5) that t_{ii} is infinite, we also have
c_{isi}
infinite, so we may as well assume that y_{isiisi} always equals 0.
Therefore, P is contained in the hyperplane
\sum_{ {i,j} } x_{i,j} = n-2.
It follows that, if for some D > 0, we increase each k_{i,j} by D
and
increase u by D(n-2), K will still be a supporting hyperplane of P
through v' such that P is contained in S. By doing this for some
suitable D, we may assume that each k_{i,j} is positive. Now set
t_{ij} := infinity, if 1 <= i = j <= n,
t_{ij} := k_{i,j}, if 2 <= i <= n,
2 <= j <= n,
and i does not
equal j,
and
t_{ij} := 0, if either
i = 1 and 2 <= j
<= n or
2 <= i <= n and j
= 1.
We now have
c_{isj} = k_{i,j}, if 2 <= i, j <= n,
1 <= s <= n-2,
and i does not
equal j,
c_{isj} = infinity, if 2 <= i = j <= n,
1 <= s <= n-2.
Assuming as before that y_{isiisi} equals 0, the objective function
of problem \overline{IP} is then equal to
\sum_{ {i,j} } k_{i,j} x_{i,j},
so the optimal solution of problem \overline{IP} will be at v'.
However,
if Step 3 of the Diaby algorithm succeeds, the y_{isjisj}'s must
correspond
to some c.a.s.s. path, so the x_{i,j}'s must be at the
corresponding
vertex in V. Since v' is not in V, we conclude that the Diaby
algorithm
does not succeed.
--
David Moews
moustap...@business.uconn.edu
OK, I am still getting emails... Hopefully, this will finally stop
them.
Consider this:
I say (see Proposition 4 on page 18 and the discussion just before it):
"Given a number, say 20, there exists even numbers, say 10 and 30,
such that 20 is the convex combination of those even numbers."
(Clearly, this is true since 20 = .5*10 + .5*30)
Hofman comes back and says:
"I found a counter-example to Diaby statement (above): I found odd
numbers such 20 is the convex combination of those numbers. In fact,
here it is: 20 = .5*21 + .5*19 !!!!"
I hope you get the absurdity?
To convince yourselves further, please, look at Figure 2.2. The graph
there contains 4 paths. Provided lambda(1,1,1) = lambda(1,2,1) = .5,
the solution shown is a convex combination of several pairs of paths
through that network, but only if path is defined in the conventional
graph theoretical sense. By the notion of "path in (y, z)"
introduced in this paper (page 14), is more complex than the
conventional graph theoretical sense.
As to Yannakakis: he (and other people before him) that address the
issue of the TSP polytope, here is some information that may be useful
to some of you:
1) References are given in my paper where you can see a precise
definition of what is meant by "TSP polytope."
2) Just because the problem being modeled is a TSP does not
automatically make the polytope associated with the model a "TSP
polytope."
3) A common practice in the OR (Operations Research) community is that
if the polytope you are working on is is a "hard one" (like the TSP
polytope), you try to see if you cannot express the same problem over
what we call a "friendlier" polytope. Just like you may want to use
"transforms" for your differential equations.
4) The polytope over which I am expressing the TSP optimization problem
in my paper is what we in the OR community call the "Assignment
Polytope." It is *very* different from the TSP polytope. So, anything
having to do with the TSP polytope does not apply to it.
I hope this will be enough ???!!!!
//MD
Radoslaw Hofman
Uzytkownik <moustap...@business.uconn.edu> napisal w wiadomosci
news:1162962966.4...@e3g2000cwe.googlegroups.com...
> OK, I am still getting emails... Hopefully, this will finally stop
> them.
==> that's bill you have to pay if you want to be known :-))
> Consider this:
>
> I say (see Proposition 4 on page 18 and the discussion just before it):
>
>
> "Given a number, say 20, there exists even numbers, say 10 and 30,
> such that 20 is the convex combination of those even numbers."
> (Clearly, this is true since 20 = .5*10 + .5*30)
>
> Hofman comes back and says:
>
> "I found a counter-example to Diaby statement (above): I found odd
> numbers such 20 is the convex combination of those numbers. In fact,
> here it is: 20 = .5*21 + .5*19 !!!!"
==> well, you don't understand *a bit* idea of how counter example is build.
I say that your algorithm is capable of producing WRONG result. It is not
problem with recognition of what was counted to get overall result. Problem
is that in counter example optimal TSP tour should be greater then 4000
(there are 4 mountain chains in mine example) while your algorithm produces
answer about 3100. How it is possible that you take this overall cost lower
then optimal TSP tour and answer problem question (which is "is there a tour
of overall cost X). It simply does not work.
Problem with your algorithm is such that you want to get sum of even numbers
but you cannot strictly express what even numbers are. Then you try to
convince other that you have created LP model capable of answering question
"is it possible that X is sum consisting ONLY of even numbers". You try to
prove that if result is even then every part of sum has to be even
x%*E1+x%*E2....=EVEN. My position is that if you combine some Real numbers
you can obtain EVEN result even if this numbers are not integers. Your proof
that EVERY FEASIBLE SOLUTION IS COMBINATION OF TSP TOURS is false in same
logic. To do more I am showing example where such combination gives result
which simply cannot correspond to any TSP tour because its "value" is to
low!
> I hope you get the absurdity?
==> It isn't very hard to prepare absurd example... it is harder to prove
that every LP solution consists ONLY of EVEN numbers
> To convince yourselves further, please, look at Figure 2.2. The graph
> there contains 4 paths. Provided lambda(1,1,1) = lambda(1,2,1) = .5,
> the solution shown is a convex combination of several pairs of paths
> through that network, but only if path is defined in the conventional
> graph theoretical sense. By the notion of "path in (y, z)"
> introduced in this paper (page 14), is more complex than the
> conventional graph theoretical sense.
==> sorry, I still don't see "strength" of this argument. I agree that some
of BLP feasible solutions (maybe all of them for small instances) correspond
to TSP tours. But I refuse to believe that all of such solutions correspond
to set of TSP tours and to do something with my belief I prepared exact
counter example which due to result value CANNOT be said to correspond to
TSP tours.
> 3) A common practice in the OR (Operations Research) community is that
> if the polytope you are working on is a "hard one" (like the TSP
> polytope), you try to see if you cannot express the same problem over
> what we call a "friendlier" polytope. Just like you may want to use
> "transforms" for your differential equations.
==> nice idea... but it is the same with expressing 3-D or 4-D objects using
2-D - how can you be sure that your "picture" isn't missing something
> 4) The polytope over which I am expressing the TSP optimization problem
> in my paper is what we in the OR community call the "Assignment
> Polytope." It is *very* different from the TSP polytope. So, anything
> having to do with the TSP polytope does not apply to it.
==> But it is still only "picture" of real object. Your function does not
react on target function shape, we can then prepare such target function
that for very complex polytopes your "assignment polytope" is
a) loosing important factors of TSP polytope in area where optimal solution
should "cut" polytope (if your "assignment polytope" has only n^9 vertexes)
b) your BLP model cannot express even this polytope because it still has
more then n^7 facets
> I hope this will be enough ???!!!!
==> enough for what? To convince everybody that even if you haven't used
your algorithm for n>10 it is capable of giving answers for infinitively
large n? Isn't it naive?
On first meeting with my Ph.D. promoter he said that before I will be good
enough to obtain such title I must learn to doubt in things, and find way to
prove or disprove them, but I cannot assume anything as true if there isn't
good enough proof for it (or it is an axiom - of course). Waren't you taught
same thoughts starting your Ph.D. studies?
Claim that "every feasible solution for BLP corresponds to valid TSP tours"
isn't an axiom, it isn't proved anywhere (including your paper, if you
consider "proof" as others are http://en.wikipedia.org/wiki/Proof_theory or
http://en.wikipedia.org/wiki/Mathematical_proof), and so it remains not
proved. Because of situation that you said "it is true" and there was no
evidence for it, I have prepared direct prove that BLP can produce feasible
solution with value lower than optimal TSP tour. Corollary of mine proof is
such: your claim that feasible BLP corresponds to (consists of set) valid
TSP tours cannot be proved to be true?
Clear enough? :)
Cheers,
Radek Hofman
moustap...@business.uconn.edu
well, you don't understand *a bit* idea of how counter example is
build.
> I say that your algorithm is capable of producing WRONG result. It is not
> problem with recognition of what was counted to get overall result. Problem
> is that in counter example optimal TSP tour should be greater then 4000
> (there are 4 mountain chains in mine example) while your algorithm produces
> answer about 3100. How it is possible that you take this overall cost lower
> then optimal TSP tour and answer problem question (which is "is there a tour
> of overall cost X). It simply does not work.
There is no algorithm in my paper. Whatever you "solution" you
constructed is entirely *yours*. Don't attribute it to me!
>
> Problem with your algorithm is such that you want to get sum of even numbers
> but you cannot strictly express what even numbers are. Then you try to
> convince other that you have created LP model capable of answering question
> "is it possible that X is sum consisting ONLY of even numbers". You try to
> prove that if result is even then every part of sum has to be even
> x%*E1+x%*E2....=EVEN. My position is that if you combine some Real numbers
> you can obtain EVEN result even if this numbers are not integers. Your proof
> that EVERY FEASIBLE SOLUTION IS COMBINATION OF TSP TOURS is false in same
> logic. To do more I am showing example where such combination gives result
> which simply cannot correspond to any TSP tour because its "value" is to
> low!
>
What you have been unable/unwilling get in my paper is the notion of
"paths in (y, z).
> > I hope you get the absurdity?==> It isn't very hard to prepare absurd example... it is harder to prove
> that every LP solution consists ONLY of EVEN numbers
There is no such suggestion in my paper.
>
> > To convince yourselves further, please, look at Figure 2.2. The graph
> > there contains 4 paths. Provided lambda(1,1,1) = lambda(1,2,1) = .5,
> > the solution shown is a convex combination of several pairs of paths
> > through that network, but only if path is defined in the conventional
> > graph theoretical sense. By the notion of "path in (y, z)"
> > introduced in this paper (page 14), is more complex than the
> > conventional graph theoretical sense.==> sorry, I still don't see "strength" of this argument. I agree that some
> of BLP feasible solutions (maybe all of them for small instances) correspond
> to TSP tours. But I refuse to believe that all of such solutions correspond
> to set of TSP tours and to do something with my belief I prepared exact
> counter example which due to result value CANNOT be said to correspond to
> TSP tours.
There are no "back flows"? Yet, there are no paths that are perferct
assignments?
You must be Houdini!!!
Hopefully you are able to see the utter absurdity of that!
>
> > 3) A common practice in the OR (Operations Research) community is that
> > if the polytope you are working on is a "hard one" (like the TSP
> > polytope), you try to see if you cannot express the same problem over
> > what we call a "friendlier" polytope. Just like you may want to use
> > "transforms" for your differential equations.==> nice idea... but it is the same with expressing 3-D or 4-D objects using
> 2-D - how can you be sure that your "picture" isn't missing something
>
> > 4) The polytope over which I am expressing the TSP optimization problem
> > in my paper is what we in the OR community call the "Assignment
> > Polytope." It is *very* different from the TSP polytope. So, anything
> > having to do with the TSP polytope does not apply to it.==> But it is still only "picture" of real object. Your function does not
> react on target function shape, we can then prepare such target function
> that for very complex polytopes your "assignment polytope" is
>
> a) loosing important factors of TSP polytope in area where optimal solution
> should "cut" polytope (if your "assignment polytope" has only n^9 vertexes)
>
> b) your BLP model cannot express even this polytope because it still has
> more then n^7 facets
>
> > I hope this will be enough ???!!!!==> enough for what? To convince everybody that even if you haven't used
> your algorithm for n>10 it is capable of giving answers for infinitively
> large n? Isn't it naive?
Before you talk about something you should educate yourself in it
first!
>
> On first meeting with my Ph.D. promoter he said that before I will be good
> enough to obtain such title I must learn to doubt in things, and find way to
> prove or disprove them, but I cannot assume anything as true if there isn't
> good enough proof for it (or it is an axiom - of course). Waren't you taught
> same thoughts starting your Ph.D. studies?
You have no idea of the depths of your limitations!!! But, let me tell
you, I have just been managing your feelings....
>
> Claim that "every feasible solution for BLP corresponds to valid TSP tours"
> isn't an axiom, it isn't proved anywhere (including your paper, if you
> consider "proof" as others arehttp://en.wikipedia.org/wiki/Proof_theoryorhttp://en.wikipedia.org/wiki/Mathematical_proof), and so it remains not
> proved. Because of situation that you said "it is true" and there was no
> evidence for it, I have prepared direct prove that BLP can produce feasible
> solution with value lower than optimal TSP tour. Corollary of mine proof is
> such: your claim that feasible BLP corresponds to (consists of set) valid
> TSP tours cannot be proved to be true?
I am sorry if the paper is beyond you. But everything is in there.
deepakc
We would like you to mathemetically prove the answers to Hofman's
QUESTION 1 & QUESTION 2 (see previous posts in this same thread).
We want a convincing answer, in terms of solid mathematical proofs (not
the 'I am comfortable with' kind of answers u earlier gave us).
Can you please do that ? It will be difficult, but if you are able to
give a solid mathematical proof, you are the clear winner, and we will
immediately accept your paper.
Thanks,
-Deepak
Radoslaw Hofman
> There is no algorithm in my paper. Whatever you "solution" you
> constructed is entirely *yours*. Don't attribute it to me!
Well... Look at definition of algorithm
http://en.wikipedia.org/wiki/Algorithm and your chapter 2.3 - how to build
BLP and get solution. It is algorithm (I believe you named in algorithm at
least in some posting) :)
> What you have been unable/unwilling get in my paper is the notion of
> "paths in (y, z).
So what? What you are unable to get is, that there can exist other objects
which are considered as "paths" by your BLP model, and they have nothing
common with "paths".
>> > I hope you get the absurdity?==> It isn't very hard to prepare absurd
>> > example... it is harder to prove
>> that every LP solution consists ONLY of EVEN numbers
>
> There is no such suggestion in my paper.
I was following your example... Logic of proof that feasible solution
consists only of valid TSP tours is with same strength :-))
> There are no "back flows"? Yet, there are no paths that are perferct
> assignments?
> You must be Houdini!!!
Maybe I am... :-))))) My surname starts with 'H' :-)))))
Don't be ridicioulus - you have all variables and can perform checking -
have you found any back-flow? Or other violated restriction?
> Hopefully you are able to see the utter absurdity of that!
I don't see it. You claim to be right because... you say so... no proves
given :). It is so called "proof by authority", but it isn't considered as
formal way of proving... If we discussed face to face you could also use
"proof by hands waking" :-)
>> > I hope this will be enough ???!!!!==> enough for what? To convince
>> > everybody that even if you haven't used
>> your algorithm for n>10 it is capable of giving answers for infinitively
>> large n? Isn't it naive?
>
> Before you talk about something you should educate yourself in it
> first!
What to reply... And you to? :-))
I have asked you about your background - in math and complexity theory.
Maybe you should get familiar with Large Numbers? Or definition of infinity?
Maybe (but not for sure) you would have seen difference between n=10 and
n-->infinity :-)))
> You have no idea of the depths of your limitations!!! But, let me tell
> you, I have just been managing your feelings....
Gosh... you have discovered one more of mine limitations... I don't get what
you meant :)
> I am sorry if the paper is beyond you. But everything is in there.
Hmmm... if we think about in such way:
- there are many abstract algebraic structures
- let us call one of them "Diaby's world"
- let us assume that there is set of axioms for "Diaby's world"
- let us assume that there is set of different operations for objects within
"Diaby's world"
- let us assume that in this set there is operation called "proof"
- let us assume that every thing in your paper relates to object and
operations defined for "Diaby's world"
Then you are of course right. But as far as I remember open question of P vs
NP was defined for Complexity Theory (derived form mathematics), and objects
with operations for them you mention in your paper only have common names to
those from Complexity Theory. You could also assume that in "Diaby's world"
there is axiom that there is P equal to NP, and do not bother with writing
anything.
Problem starts when you want to convince others that your paper does not
apply to "Diaby's world" but to mathematics. If so, then you have to use
operations and object defined for this theory (have you heard about
Gödel?)... And math's-world operation called "proof" in your paper for claim
that "every BLP solution consists of valid TSP tour" does not exist. If I
know what "proof" means, after showing mine counter example I may prove that
your claim is improvable :).
NOW SERIOUS: do you have any MERIT arguments or your only way is to show
that I'm dull? Maybe frighten me with your authority? Someone wrote that
arguments all of us are using are good, but for pub discussion. So if you
cannot point out where mine example is violating your model and cannot solve
instance I have presented using your model maybe you should face it - this
method isn't always correct.
Why it seems so absurd for you? Is it the first time in life when you are
not right? (ups. pub's argument again. ehh. what you give is what you get in
return, isn't it?) :-)))
Cheers,
Radek Hofman
deepakc
We would like you to do ANYONE of the following TWO things, if you want
your work to be accepted by everyone.
ONE:- give solid mathemetical proofs for the answers to Hofman's
QUESTION 1 & QUESTION 2 (see previous posts in this same thread)
TWO:- point out a flaw in Mr. Hofman's counter-example
We hope you will be able to do ANYONE of the above, hopefully within
the following days/weeks.
-Deepak
deepakc
Dear Sir David Moews,
We hope you will join this thread.
Pls note I have posted your Proof, that refutes Diaby's Theorem via
YANNAKAKIS result. You will have to search for my posting (just a few
posts before this).
We hope you will share your opinion with us, regarding this entire
thread.
Thanks,
-Deepak
mathisart
> > I say that your algorithm is capable of producing WRONG result. It is not
> > problem with recognition of what was counted to get overall result. Problem
> > is that in counter example optimal TSP tour should be greater then 4000
> > (there are 4 mountain chains in mine example) while your algorithm produces
> > answer about 3100. How it is possible that you take this overall cost lower
> > then optimal TSP tour and answer problem question (which is "is there a tour
> > of overall cost X). It simply does not work.
>
> There is no algorithm in my paper. Whatever you "solution" you
> constructed is entirely *yours*. Don't attribute it to me!
What did he misimplement? His code is readable and brief. rather than
doubting his "shortcut" of only looking at some parts of the table, you
seem to doubt his implementation of the restrictions:
> > Problem with your algorithm is such that you want to get sum of even numbers
> > but you cannot strictly express what even numbers are. Then you try to
> > convince other that you have created LP model capable of answering question
> > "is it possible that X is sum consisting ONLY of even numbers". You try to
> > prove that if result is even then every part of sum has to be even
> > x%*E1+x%*E2....=EVEN. My position is that if you combine some Real numbers
> > you can obtain EVEN result even if this numbers are not integers. Your proof
> > that EVERY FEASIBLE SOLUTION IS COMBINATION OF TSP TOURS is false in same
> > logic. To do more I am showing example where such combination gives result
> > which simply cannot correspond to any TSP tour because its "value" is to
> > low!
>
> What you have been unable/unwilling get in my paper is the notion of
> "paths in (y, z).
In particular, I would think you have strong motivation to show the
error.
-- You have a nice, tight description of a solution, but it is a mental
model. Hofman puts something in front of you that, to all appearances,
your model says shouldn't exist. How can you not take it seriously?
How can you only look for backflow in the state tables, ignoring the
result, Hofman's own reasoning of what is wrong (that backflow is
hidden in the structure), and the implementation? It seems like you
are hoping beyond hope, in what _should_ be, and not simply looking at
what is.
A.L.
wrote:
There was a long discussion in 2005 regarding this topic, on much
higher professional level than this one. I don't think that there is
much more to say than it was said in mentioned discussion, when all
questions/doubts have remained not answered.
You can find this thread by seaching Google Groups.
A.L.
tc...@lsa.umich.edu
<moustap...@business.uconn.edu> wrote:
>OK, I am now completely satisfied that neither of you has a clue (at
>best)... You are free to go on with your nonsense. Please, just don't
>clug up my email with it any more.
I agree fully with you about not clogging up email. This discussion is
better held on comp.theory.
However, I don't believe that your attitude here is justified, certainly
not towards Deepak Chermakani, who is clearly trying his best to give you
the benefit of the doubt and is trying to understand your argument. If
you feel that you are at an impasse with Hofman, at least try to answer
Chermakani's questions, which he has repeated several times.
deepakc
> not towards Deepak Chermakani, who is clearly trying his best to give you
> the benefit of the doubt and is trying to understand your argument. If
> you feel that you are at an impasse with Hofman, at least try to answer
> Chermakani's questions, which he has repeated several times.
> --
> Tim Chow tchow-at-alum-dot-mit-dot-edu
Yes, infact, I would really like Diaby to focus his energy on finding
out solid-mathematical proofs for both Questions 1 & Question 2, of
Hofman.
I just now read some more posts in GoogleGroups of 2005, and now I find
that these two Questions have been repeatedly asked (but worded
differently) to Diaby from around 2005, by lots of people like Bryan
Olson, David Moews, Pat Shanahan, etc.
You may refer:
http://groups.google.com/group/comp.theory/tree/browse_frm/month/2005-09/84182ebdf14f1bbb?rnum=11
It will be without doubt, tough for Diaby to generate proofs for these
two Questions, because his Model is huge. But then he is the one who
developed this huge Model, so it is his job to develop
solid-mathematical proofs (and not simple wishy-washy answers) for
these Questions.
Thanks,
-Deepak
moustap...@business.uconn.edu
> by lots of people like Bryan
> Olson, David Moews, Pat Shanahan, etc.
A rose by any other name....
Here are answers I have basically given you already. The paper is a
linear programming paper. I do not how to express these ideas in any
simplier terms. It is really as plain as possible for the context. If
any of those reading this thread does not understand this, then they
are definitely not qualified to attempt judge my paper (I don't mean
this in patronizing way, but I feel I need to be blunt enough).
My advice is if you don't understand, before you assume it is wrtong,
take it to someone who may be able to translate it to you in
face-to-face context. Talk to whoever has a reasonable amount of
*expertise* in mathematical programming."
Otherwise, you are asking me to explain things to you in say, Hebrew,
when we are in a context where everybody is supposed tyo know, say
English, and English is the only language I can speak.
FIRST SET OF RESPONSES I GAVE YOU ALREADY
Hofman's 2 Questions are:-
QUESTION ONE: - Is your Algorithm capable of pinpointing all (N!) TSP
tours, if every tour has equal length ??? The answer is obviously NO,
because in the overall picture, your Algorithm involves a Polynomial
number of variables. I know that Linear Programming guarantees to find
atleast one optimal tour, within Polynomial time, by walking across the
vertexes of your new Assignment Polytope that has Polynomial size.
However, then that leads to Question 2.
The issue is formally addressed by Proposition 1 of the paper: No TSP
tour is excluded from the feasible set of the IP formulation (see
Proposition 1 and its proof). The feasible set of the LP relaxation
includes that of the IP and must therefore include all the TSP tours.
QUESTION TWO: - Is it possible for your Algorithm to give the correct
solution for the CONVEX COMBINATION OF PATHS, but where EACH SINGLE
PATH IN THIS COMBINATION is a wrong solution ??? According to me, this
is possible because you have not explicitly proved this anywhere in
your paper. Yes, I will believe you only if you write a new proof in
your paper, stating that it is never possible for your Algorithm to
give the correct solution for the CONVEX COMBINATION OF PATHS, but
where EACH SINGLE PATH IN THIS COMBINATION is a wrong solution.
No. If you examine the positive components of any feasible solution you
must find that they have the structure described in Proposition 2 (That
is what the mathematics say -- And, I am quite comfortable with the
correctness). With such a structure each vertex of the polytope
described by the constraints of my model corresponds to a TSP tour
(Note I am saying "corresponds to", not *is*: the solution needs to be
properly "interpreted" because I am not dealing with *the* TSP
polytope). This is what is proven in either Proposition 3 or 4 (I don't
have the paper in front of me, but its the proposition about BFS's and
TSP tours). Each corner of the polytope corresponds to a TSP but has
several alternative algebraic representations in terms of what we call
in LP lingo, Basic Feasible Solutions. So, everything you are asking
for above, is already in the paper.
Finally, I want to make something very clear. I am subjecting myself to
all this for no other reason than out of my desire to be a "good
citizen" of whatever your scientific community is, and into which I was
"dragged" unwillingly. Otherwise, most of th opinions that have
expressed have absolutely no value for me: all these debates would be
trivial matterrs to beginners that have gonme through a few
fundamentals in my area of expertise (OR)...
I really have nothing more to contribute here on these issues apart
from what is below and what is the paper. "Everything" is *really* in
the paper...
SECOND SET OF RESPONSES I GAVE YOU ALREADY
OK, I am still getting emails... Hopefully, this will finally stop
them.
Consider this:
I say (see Proposition 4 on page 18 and the discussion just before it):
"Given a number, say 20, there exists even numbers, say 10 and 30,
such that 20 is the convex combination of those even numbers."
(Clearly, this is true since 20 = .5*10 + .5*30)
Hofman comes back and says:
"I found a counter-example to Diaby statement (above): I found odd
numbers such 20 is the convex combination of those numbers. In fact,
here it is: 20 = .5*21 + .5*19 !!!!"
I hope you get the absurdity?
To convince yourselves further, please, look at Figure 2.2. The graph
there contains 4 paths. Provided lambda(1,1,1) = lambda(1,2,1) = .5,
the solution shown is a convex combination of several pairs of paths
through that network, but only if path is defined in the conventional
graph theoretical sense. By the notion of "path in (y, z)"
introduced in this paper (page 14), is more complex than the
conventional graph theoretical sense.
As to Yannakakis: he (and other people before him) that address the
issue of the TSP polytope, here is some information that may be useful
to some of you:
1) References are given in my paper where you can see a precise
definition of what is meant by "TSP polytope."
2) Just because the problem being modeled is a TSP does not
automatically make the polytope associated with the model *the* "TSP
polytope" (there is only *one* "TSP Polytope")
3) A common practice in the OR (Operations Research) community is that
if the polytope you are working on is is a "hard one" (like *the*
TSP polytope), you try to see if you cannot express the same problem
over what we call a "friendlier" polytope. Just like you may want
to use "transforms" for your differential equations.
4) The polytope over which I am expressing the TSP optimization problem
in my modeling approach is the one we in the OR community call *the*
"Assignment Polytope."
The Assignment polytope has been studied as much, if not more than, the
TSP polytope, in the OR literatute.
The Assignment polytope is * very*, *very* different from *the* TSP
polytope.
My modeling consists of formulating the TSP optimization problem as a
math ptog. Problem over *the* assignment polytope expressed in higher
dimension.
So, the polytope of my model has nothing to do with *the* TSP polytope.
moustap...@business.uconn.edu
(except for typos, of course)
> by lots of people like Bryan
> Olson, David Moews, Pat Shanahan, etc.
A rose by any other name....
Here are answers I have basically given you already. The paper is a
linear programming paper. I do not how to express these ideas in any
simplier terms. It is really as plain as possible for the context. If
any of those reading this thread does not understand this, then they
are definitely not qualified to attempt judge my paper (I don't mean
this in patronizing way, but I feel I need to be blunt enough).
My advice is if you don't understand, before you assume it is wrong,
take it to someone who may be able to translate it to you in
face-to-face context. Talk to whoever has a reasonable amount of
*expertise* in mathematical programming.
Otherwise, you are asking me to explain things to you in say, Hebrew,
when we are in a context where everybody is supposed to know, say
English, and when English happens to be the only language I can speak.
Finally, I want to make something very clear. I am subjecting myself to
all this for no other reason than out of my desire to be a "good
citizen" of whatever your scientific community, since being unwillingly
"dragged" into it. Otherwise, the opinions that are being
expressed at this time have absolutely no value for me: all these
debates would be
trivial matterrs to beginners that have gone through a few
fundamentals in my area of expertise (OR)...
I really have nothing more to contribute here on these issues apart
from what is below and what is in the paper. ..And, "everything" is
*really* in
the paper...
FIRST SET OF RESPONSES I GAVE YOU ALREADY
Hofman's 2 Questions are:-
QUESTION ONE: - Is your Algorithm capable of pinpointing all (N!) TSP
tours, if every tour has equal length ??? The answer is obviously NO,
because in the overall picture, your Algorithm involves a Polynomial
number of variables. I know that Linear Programming guarantees to find
atleast one optimal tour, within Polynomial time, by walking across the
vertexes of your new Assignment Polytope that has Polynomial size.
However, then that leads to Question 2.
ANSWER: The issue is formally addressed by Proposition 1 of the paper:
No TSP
tour is excluded from the feasible set of the IP formulation (see
Proposition 1 and its proof). The feasible set of the LP relaxation
includes that of the IP and must therefore include all the TSP tours.
QUESTION TWO: - Is it possible for your Algorithm to give the correct
solution for the CONVEX COMBINATION OF PATHS, but where EACH SINGLE
PATH IN THIS COMBINATION is a wrong solution ??? According to me, this
is possible because you have not explicitly proved this anywhere in
your paper. Yes, I will believe you only if you write a new proof in
your paper, stating that it is never possible for your Algorithm to
give the correct solution for the CONVEX COMBINATION OF PATHS, but
where EACH SINGLE PATH IN THIS COMBINATION is a wrong solution.
ANSWER: No. If you examine the positive components of any feasible
solution you
must find that they have the structure described in Proposition 2 (That
is what the mathematics say -- And, I am quite comfortable with the
correctness). With such a structure each vertex of the polytope
described by the constraints of my model corresponds to a TSP tour
(Note I am saying "corresponds to", not *is*: the solution needs to be
properly "interpreted" because I am not dealing with *the* TSP
polytope). This is what is proven in either Proposition 3 or 4 (I don't
have the paper in front of me, but its the proposition about BFS's and
TSP tours). Each corner of the polytope corresponds to a TSP but has
several alternative algebraic representations in terms of what we call
in LP lingo, Basic Feasible Solutions. So, everything you are asking
for above, is already in the paper.
SECOND SET OF RESPONSES I GAVE YOU ALREADY
Radoslaw Hofman
> My previous post was sent inadvertantly... This is what I had intended
> (except for typos, of course)
> Here are answers I have basically given you already. The paper is a
> linear programming paper. I do not how to express these ideas in any
> simplier terms. It is really as plain as possible for the context. If
> any of those reading this thread does not understand this, then they
> are definitely not qualified to attempt judge my paper (I don't mean
> this in patronizing way, but I feel I need to be blunt enough).
We are not judgeing. You claim to have proved something. Then we are showing
something which if your proof was correct should not exist. But it does...
anyone can download source code or results and find them 100% compliant with
your BLP model and having nothing in common with TSP solution...
> My advice is if you don't understand, before you assume it is wrong,
> take it to someone who may be able to translate it to you in
> face-to-face context. Talk to whoever has a reasonable amount of
> *expertise* in mathematical programming.
Do you know anyone who has more expirience than you have (and that means all
of us since our knowledge due to your words is much worse) in LP who agrees
that your model is correct? I don't think so.
> Otherwise, you are asking me to explain things to you in say, Hebrew,
> when we are in a context where everybody is supposed to know, say
> English, and when English happens to be the only language I can speak.
Deepak asked you to use math language...
> Finally, I want to make something very clear. I am subjecting myself to
> all this for no other reason than out of my desire to be a "good
> citizen" of whatever your scientific community, since being unwillingly
> "dragged" into it. Otherwise, the opinions that are being
> expressed at this time have absolutely no value for me: all these
> debates would be
> trivial matterrs to beginners that have gone through a few
> fundamentals in my area of expertise (OR)...
>
> I really have nothing more to contribute here on these issues apart
> from what is below and what is in the paper. ..And, "everything" is
> *really* in
> the paper...
But there are many people pointing out that there is something missing.
There are possible explanations:
- all of us are much more incompetent then you are
- there are things you assume obvious and no other person does
We are asking to clarify...
> FIRST SET OF RESPONSES I GAVE YOU ALREADY
> Hofman's 2 Questions are:-
>
> QUESTION ONE: - Is your Algorithm capable of pinpointing all (N!) TSP
> tours, if every tour has equal length ??? The answer is obviously NO,
> because in the overall picture, your Algorithm involves a Polynomial
> number of variables. I know that Linear Programming guarantees to find
> atleast one optimal tour, within Polynomial time, by walking across the
> vertexes of your new Assignment Polytope that has Polynomial size.
> However, then that leads to Question 2.
> ANSWER: The issue is formally addressed by Proposition 1 of the paper:
> No TSP
> tour is excluded from the feasible set of the IP formulation (see
> Proposition 1 and its proof). The feasible set of the LP relaxation
> includes that of the IP and must therefore include all the TSP tours.
Remember that LP guarantees to find optimal solution for LP model not for
TSP tour. I can agree with your arguments:
forall t in TSP-solution exists b in BLP-feasible-solutions t subset b
But it does not prove or disprove to mine thought:
exists b in BLP-fesible-solutions forall t in TSP-tours
overallCost(b)<overallCost(t)
Answer to mine question does not contradicts with first sentence in your
word prooved in proposition 1. This is same difference between => and <=>.
We know that if we get any of TSP-solutions then we can show BLP feasible
solution including chosen TSP tour. But it does not imply in reverse
direction!
> QUESTION TWO: - Is it possible for your Algorithm to give the correct
> solution for the CONVEX COMBINATION OF PATHS, but where EACH SINGLE
> PATH IN THIS COMBINATION is a wrong solution ??? According to me, this
> is possible because you have not explicitly proved this anywhere in
> your paper. Yes, I will believe you only if you write a new proof in
> your paper, stating that it is never possible for your Algorithm to
> give the correct solution for the CONVEX COMBINATION OF PATHS, but
> where EACH SINGLE PATH IN THIS COMBINATION is a wrong solution.
>
> ANSWER: No. If you examine the positive components of any feasible
> solution you
> must find that they have the structure described in Proposition 2 (That
> is what the mathematics say -- And, I am quite comfortable with the
> correctness). With such a structure each vertex of the polytope
> described by the constraints of my model corresponds to a TSP tour
> (Note I am saying "corresponds to", not *is*: the solution needs to be
> properly "interpreted" because I am not dealing with *the* TSP
> polytope). This is what is proven in either Proposition 3 or 4 (I don't
> have the paper in front of me, but its the proposition about BFS's and
> TSP tours). Each corner of the polytope corresponds to a TSP but has
> several alternative algebraic representations in terms of what we call
> in LP lingo, Basic Feasible Solutions. So, everything you are asking
> for above, is already in the paper.
See my comment above. Your structure isn't strong enough to exclude all
possible objects which has nothing in common with TSP-tours. I give strict
example of such objects. There is no proof that this "structure" excludes
non TSP-tours.
I will answer second set of questions after while - I have already posted
them but I have new thoughts. I have to attend few meetings :).
Cheers,
Radek Hofman
Radosław Hofman
Użytkownik <moustap...@business.uconn.edu> napisał w wiadomości
news:1163034546....@m7g2000cwm.googlegroups.com...
> SECOND SET OF RESPONSES I GAVE YOU ALREADY
> I say (see Proposition 4 on page 18 and the discussion just before it):
>
> "Given a number, say 20, there exists even numbers, say 10 and 30,
> such that 20 is the convex combination of those even numbers."
> (Clearly, this is true since 20 = .5*10 + .5*30)
>
> Hofman comes back and says:
>
> "I found a counter-example to Diaby statement (above): I found odd
> numbers such 20 is the convex combination of those numbers. In fact,
> here it is: 20 = .5*21 + .5*19 !!!!"
>
> I hope you get the absurdity?
I have responded that problem is that you claim to have model with
restrictions on what is counted to sum. It isn't very hard to prepare absurd
example... it is harder to prove
that every BLP solution consists ONLY of TSP-tours
> To convince yourselves further, please, look at Figure 2.2. The graph
> there contains 4 paths. Provided lambda(1,1,1) = lambda(1,2,1) = .5,
> the solution shown is a convex combination of several pairs of paths
> through that network, but only if path is defined in the conventional
> graph theoretical sense. By the notion of "path in (y, z)"
> introduced in this paper (page 14), is more complex than the
> conventional graph theoretical sense.
I completlee agree that every TSP correspond to some BLP, but not in other
direction. Figure 2.2 is example for BLP for two TSP. In mine paper fig 13
shows BLP with no corresponding TSP.
> 3) A common practice in the OR (Operations Research) community is
> that
> if the polytope you are working on is is a "hard one" (like *the*
> TSP polytope), you try to see if you cannot express the same problem
> over what we call a "friendlier" polytope. Just like you may want
> to use "transforms" for your differential equations.
==> nice idea... but it is the same with expressing 3-D or 4-D objects using
2-D - how can you be sure that your "picture" isn't missing something
> 4) The polytope over which I am expressing the TSP optimization
> problem
> in my modeling approach is the one we in the OR community call *the*
> "Assignment Polytope."
> The Assignment polytope has been studied as much, if not more than, the
> TSP polytope, in the OR literatute.
> The Assignment polytope is * very*, *very* different from *the* TSP
> polytope.
But it is still only "picture" of real object. Your function does not
react on target function shape, we can then prepare such target function
that for very complex polytopes your "assignment polytope" is
a) loosing important factors of TSP polytope in area where optimal solution
should "cut" polytope (if your "assignment polytope" has only n^9 vertexes)
b) your BLP model cannot express even this polytope because it still has
more then n^7 facets
> My modeling consists of formulating the TSP optimization problem as a
> math ptog. Problem over *the* assignment polytope expressed in higher
> dimension.
You claim to have proved that BLP can represent TSP - I can agree with that
(TSP => BLP). But what you didn't prove is <=> relation. Or we may say other
direction BLP => TSP.
Cheers,
Radek Hofman
kin...@freemail.it
moustap...@business.uconn.edu wrote:
CUT
> Here are answers I have basically given you already. The paper is a
> linear programming paper. I do not how to express these ideas in any
> simplier terms. It is really as plain as possible for the context. If
> any of those reading this thread does not understand this, then they
> are definitely not qualified to attempt judge my paper (I don't mean
> this in patronizing way, but I feel I need to be blunt enough).
>
> My advice is if you don't understand, before you assume it is wrong,
> take it to someone who may be able to translate it to you in
> face-to-face context. Talk to whoever has a reasonable amount of
> *expertise* in mathematical programming.
>
> Otherwise, you are asking me to explain things to you in say, Hebrew,
> when we are in a context where everybody is supposed to know, say
> English, and when English happens to be the only language I can speak.
>
> Finally, I want to make something very clear. I am subjecting myself to
>
> all this for no other reason than out of my desire to be a "good
> citizen" of whatever your scientific community, since being unwillingly
>
> "dragged" into it. Otherwise, the opinions that are being
> expressed at this time have absolutely no value for me: all these
> debates would be
> trivial matterrs to beginners that have gone through a few
> fundamentals in my area of expertise (OR)...
Why then don't you start a discussion about your paper in the group
sci.op-research?
Why don't you submit your paper to a more convenient journal?
deepakc
> when we are in a context where everybody is supposed to know, say
> English, and when English happens to be the only language I can speak.
Dear Dr. Diaby,
All we are asking you to do is, to prepare solid mathematical proofs
(using basic mathamatical language) for QUESTION 1 & QUESTION 2. These
2 questions have been asked to you by lots of people, since 2005,
though they may have been worded differently.
How much time will it take you...3 weeks, 4 weeks ??
But once you do that, you will win immediate acceptance from the full
world.
So I hope you will immediately get going with preparation of those
solid mathematical proofs.
-Deepak
A.L.
>
>moustap...@business.uconn.edu wrote:
>
>
>> trivial matterrs to beginners that have gone through a few
>> fundamentals in my area of expertise (OR)...
>
>Why then don't you start a discussion about your paper in the group
>sci.op-research?
>
OR group is more "pragmatic" than comp.theory, i.e. more oriented
towards pracice (as the whole OR as discipline).
>Why don't you submit your paper to a more convenient journal?
Legitimate question. Why not to publish in reputable journal where
review process is strict and serious?...
A.L.
A.L.
<rad...@teycom.pl> wrote:
>
>
>You claim to have proved that BLP can represent TSP - I can agree with that
>(TSP => BLP). But what you didn't prove is <=> relation. Or we may say other
>direction BLP => TSP.
>
I believe that proving BLP=>TSP is the key issue. Otherwise, we are
playing with apples and oranges...
A.L.
moustap...@business.uconn.edu
> >> trivial matterrs to beginners that have gone through a few
> >> fundamentals in my area of expertise (OR)...
> >
> >Why then don't you start a discussion about your paper in the group
> >sci.op-research?
My papers have been available online, and anyone in any community is
free to comment on it. I have not seen on sci.op-research, and I do not
feel the need to sollicit any.
> >
>
> OR group is more "pragmatic" than comp.theory, i.e. more oriented
> towards pracice (as the whole OR as discipline).
>
May be. But, I believe the theory part of OR is as deep as in any other
sub-field of mathematics. A big difference I have seen so far is in the
general culture: in the OR community, people would typically refrain
from making judgments on anything unless they are confident of their
mastery of the topic in question... Even, across sub-specializations.
That is reason for my earlier reactions to comments from this people in
this group: Some of the comments looked malicious because of extent of
"clueless babble" couple with absolute "deafness" in relation to basic
concepts! ...Just like what this current thread has turned into.
> >Why don't you submit your paper to a more convenient journal?
>
I did not submitted to any comp theory journal, nor did I introduce my
work in this discussion group.
> Legitimate question. Why not to publish in reputable journal where
> review process is strict and serious?...
The review process is still going on.
Radoslaw Hofman
>> >Why don't you submit your paper to a more convenient journal?
>>
>
> I did not submitted to any comp theory journal, nor did I introduce my
> work in this discussion group.
But you did:
From:moustapha.di...@business.uconn.edu
Date:Wt. 15 Feb 2005 21:27
E-mail: moustapha.di...@business.uconn.edu
Grups: comp.theory
Dear Fellows of the Community:
Some weeks ago, in the process of extending my LP formulation of the
TSP to other combinatorial problems, I found that the model needed some
additional constraints. I have revised the model and paper accordingly.
I would like to invite you, if I may, to take a look at the revised
model and paper at: http://www.business.uconn.edu/users/mdiaby/TSPLP.
Any comments would be highly appreciated. Regards.//MD.
See:
http://groups.google.com/group/comp.theory/browse_frm/thread/a51336bf4dd7bc48
Well then - If you don't want to then I shall ask that group what do they
think about your method, and how they find mine counter-example...
Best regards,
Radek Hofman
moustap...@business.uconn.edu
Again, just naively jumping before thinking... I was not introducing
the paper. The paper had already been introduced.
A.L.
wrote:
>
>
>May be. But, I believe the theory part of OR is as deep as in any other
>sub-field of mathematics. A big difference I have seen so far is in the
>general culture: in the OR community, people would typically refrain
>from making judgments on anything unless they are confident of their
>mastery of the topic in question...
OR community is not different than any other community
>
>> >Why don't you submit your paper to a more convenient journal?
>>
>
>I did not submitted to any comp theory journal, nor did I introduce my
>work in this discussion group.
If you don't submit your paper to reputable journal, then your paper
most likely will stay ignored. Bit you DID introduce your paper in
this group. Mr. Hofman's posting saved me time finding the
reference.
A.L.
Patricia Shanahan
And if he really does have a P=NP proof, not submitting it to "a
refereed mathematics publication of worldwide repute" amounts to
throwing away a million dollars. Hardly a demonstration of confidence in
the correctness of the proof.
Patricia
moustap...@business.uconn.edu
> If you don't submit your paper to reputable journal, then your paper
> most likely will stay ignored. Bit you DID introduce your paper in
> this group. Mr. Hofman's posting saved me time finding the
> reference.
>
No, I did not. After I had been "dragged" into the group, I tried to be
a "good citizen" of it, not being aware then of the culture. That is
all...
A.L.
wrote:
Frankly speaking, I don't understand your remark about "culture"....
A.L.
deepakc
Diaby, and for all of you in this discussion
Dear Everyone,
Please let us focus on the most important issue here, and not make this
discussion too personal.
I must confess that I still havent fully understood Diaby's Model, but
if he wants to convince the scientific community regarding his work, he
must prepare the mathematical proofs for QUESTION 1 & QUESTION 2,
because these 2 Questions have been asked to him by many people since
2005, though they may have been worded differently.
I have read earlier Google threads, and I do not think there is any
other Question, that people seem to be asking regarding his TSP
Algorithm. I will stress that these are the only 2 Questions that
people seem to be repeating again and again, in various forms.
Either of 2 CASES will happen, while Diaby starts preparing the proofs:
CASE 1:
If he finds that the proofs answer QUESTION 1 & QUESTION 2, he
automatically prove three things:
1.) He is 100% right, and deserves Clay Prize
2.) Yannakakis result and Mr. David Moews result, somehow do not apply
to his Model, based on Diaby's argument in the Google threads
3.) Mr. Hofman somehow made a mistake while implementing his
Counter-Example
CASE 2:
If he finds that the proofs contradict QUESTION 1 & QUESTION 2, he is
100% wrong, and that the results of Hofman, Moews, and Yannakakis, all
apply to his Model.
I would also appreciate if someone else as well, in the community, who
has exceptional brilliance, to take on the responsbility, of generating
the proofs for QUESTION 1 & QUESTION 2.
That way, we will be able to reach CASE 1, or CASE 2, much faster.
Thank you very much.
-Deepak Ponvel Chermakani
--------------------------
IEEE Member,
Chairman of Brain Modeling & Intelligent Systems SIG of MENSA
Singapore,
http://www.mensa.org.sg/sig
--------------------------
deepakc
> I believe that proving BLP=>TSP is the key issue. Otherwise, we are
> playing with apples and oranges...
> A.L.
Yes AL, this is covered within QUESTION 1.
So the focus of energy of the scientific community, and Diaby, should
be on mathematically proving QUESTION 1 & QUESTION 2.
deepakc
that people have been repeatedly asking him since 2005:
QUESTION ONE: - For a TSP where every tour has equal length, Is Diaby's
Algorithm capable of pinpointing all (N!) TSP tours ???
QUESTION TWO: - For a Generic TSP, Is it possible for Diaby's Algorithm
deepakc
I believe this could be a possible clue for a proof for QUESTION-1. The
answer is yes, Diaby's Algorithm is capable of pinpointing all (N!)
tours. This is a very meta-level proof, but it needs to be converted
into a more mathematical proof.
The meta-level proof is in the following 4 points (and pls correct me
if I am wrong):
1. If you carefully think, you find out that the formulation of the
Assignment Polytope, from the TSP Polytope, can occur in an exponential
number of ways.
2. Lets denote the one and only one TSP polytope as P(TSP), and the
possible Assignment Polytopes as P(APi), where i varies from 1 to N!.
So we have P(TSP)=>P(AP1), P(TSP)=>P(AP2), P(TSP)=>P(AP3),
......P(TSP)=>P(APN!).
3. For each different Assignment Polytope, we are capable of obtaining
a BFS (Basic Feasible Solution). So P(APi)=>BFSi, where i varies from 1
to N!.
4. Even if a single optimal TSP tour can be obtained from one BFS, it
follows that an exponential number of optimal TSP tours can be obtained
from N! BFS. In other words, BFSi=>Tour(i), where i varies from 1 to N!
Hence proved.
As regards QUESTION-2, I really have no clue as to where to start. And
I believe that QUESTION-2 is the hardest part.
Let me know what you think.
-Deepak
Radoslaw Hofman
Uzytkownik "deepakc" <dee...@pmail.ntu.edu.sg> napisal w wiadomosci
news:1163160807.5...@k70g2000cwa.googlegroups.com...
> Dear All,
>
> I believe this could be a possible clue for a proof for QUESTION-1. The
> answer is yes, Diaby's Algorithm is capable of pinpointing all (N!)
> tours. This is a very meta-level proof, but it needs to be converted
> into a more mathematical proof.
>
> The meta-level proof is in the following 4 points (and pls correct me
> if I am wrong):
>
> 1. If you carefully think, you find out that the formulation of the
> Assignment Polytope, from the TSP Polytope, can occur in an exponential
> number of ways.
>
Hi,
Yes it is, and I have had no doubt about it. Mine original question (sorry
for not precising it in your posts) was: is this model capable of pointing
any SET of tours.
Answer is NO - there are O(2^2^n) possible sets, and model is capable of
pointing out O(c^n^9) different objects (c is some constant - may be big -
it corresponds to different values which can be assigned to variables).
My previous posting about it:
> Uzytkownik "Radoslaw Hofman" <rad...@teycom.pl> napisal w wiadomosci
> news:1161946587.1...@k70g2000cwa.googlegroups.com...
> Hi,
> You prove for integer linear programming that feasible solution is ONE
> TSP tour, and it is obvious. But after changing to non-integer version
> you omit this problem. You write in "proof" for proposition 3:
> "Hence, there is a one-to-one correspondence between paths in (y, z)
> from (1, .) to (n-2, .) and c.a.s.s. paths of Graph G (and therefore,
> TSP tours)." And where is proof that this correspondence is one to
> one? Where is proof that NON-TSP paths cannot be combined together
> forming groups feasible in model?
> This thing is not true if you are expressing not single solution but
> set of solutions! This is crucial difference between integer and
> non-integer version of problem: integer version expresses ONE solution
> at time. If there are many possible solutions than still it holds only
> ONE. Non-integer version expresses SET OF SOLUTIONS. And therefore it
> needs different expression precision. And assumption that "integer
> version refers to TSP tour then non-integer version refer to set of TSP
> tours" is more then naïve.
> For n=10 there would be 100!/4=X/4*10^24=[BIG NUMBER]*10^24
> optimal solutions (in fact it is 2.7*10^157)
> while your model is capable to store no more then 10^18 different
> solutions. If then in your model you cannot recognize EVERY possible
> solution why are you so sure, that there are no NON-TSP paths combined
> together?
Answer to question of pointing single solution is simple - if IP model does
it, then because BLP model can have assigned 0/1 values as well it can point
out any SINGLE solution. Problem is with sets of solutions which simply
cannot be covered.
I fully agree that this is of less importance then question about proving
that BLP feasible solution cannot consist of non TSP-tours. In fact if this
had been proved than without answering to first question method would have
to be correct.
Fortunately (for those who believe in P!=NP) my example shows such BLP
feasible solution which has better overall cost then any of TSP solutions.
Best regards,
Radek Hofman
Radosław Hofman
Użytkownik "Radoslaw Hofman" <rad...@teycom.pl> napisał w wiadomości
news:ej1shl$9qs$1...@sunflower.man.poznan.pl...
>> For n=10 there would be 100!/4=X/4*10^24=[BIG NUMBER]*10^24
it should be "for n=100" - rest is OK :-)
Cheers
Radek Hofman
deepakc
After reading your post, I conclude that Diaby therefore now needs to
answer only QUESTION-2.
Pls read what I have written below.
Radoslaw Hofman wrote:
> Hi,
>
> Yes it is, and I have had no doubt about it. Mine original question (sorry
> for not precising it in your posts) was: is this model capable of pointing
> any SET of tours.
>
> Answer is NO - there are O(2^2^n) possible sets, and model is capable of
> pointing out O(c^n^9) different objects (c is some constant - may be big -
> it corresponds to different values which can be assigned to variables).
>
> Answer to question of pointing single solution is simple - if IP model does
> it, then because BLP model can have assigned 0/1 values as well it can point
> out any SINGLE solution. Problem is with sets of solutions which simply
> cannot be covered.
>
> I fully agree that this is of less importance then question about proving
> that BLP feasible solution cannot consist of non TSP-tours. In fact if this
> had been proved than without answering to first question method would have
> to be correct.
Ok, Diaby's Algorithm is as follows.
He formulates the TSP polytope into Assignment polytope, where each
vertex of the Assignment polytope is a CONVEX COMBINATION of the
vertexes of the TSP polytope. So while the TSP polytope has an
exponential number of vertexes, the Assignment polytope has only a
polynomial number of vertexes.
But then Diaby does this.....He relaxes ILP to LP.
So it follows that, within Polynomial time, Diaby's Algorithm is able
to identify an optimal vertex for the Assignment Polytope, such that
this vertex may not be the CONVEX COMBINATION of vertexes of the TSP
Polytope.....but may be points lying outside the TSP Polytope, which
can happen because of the relaxation from ILP to LP.
What the above paragraph means is that Diaby's Algorithm is capable of
obtaining non-TSP tours, which are wrong FINAL solutions, even though
their CONVEX COMBINATION is a Basic Feasible Solution of the LP.
I hope you agree with what I have said above.
In other words, Diaby only needs to prove QUESTION-2, which
is......Prove that for any Generic TSP, is it possible for Diaby's
Algorithm to generate a correct solution for the CONVEX COMBINATION OF
PATHS, where each PATH IN THIS COMBINATION is an invalid TSP path.
-Deepak
deepakc
Dear Mr. Hofman,
After reading your post, I conclude that Diaby therefore now needs to
answer only QUESTION-2.
Ok, Diaby's Algorithm is as follows.
deepakc
> For n=10 there would be 100!/4=X/4*10^24=[BIG NUMBER]*10^24
> it should be "for n=100" - rest is OK :-)
>
> Cheers
> Radek Hofman
Dear Mr. Hofman,
Please carefully read my post number "105", and that should answer your
above Question.
According to me, the correctness of Diaby's Algorithm has absolutely
nothing to do with size of the TSP. Diaby's Algorithm can fail, whether
it has 4 cities or 40 cities or 400 cities, and the reason for that is
because of the relaxation from ILP to LP.
So according to me, the only flaw with Diaby's Algorithm is QUESTION-2,
which is: - Prove that it is possible for Diaby's Algorithm to generate
a correct solution for the CONVEX COMBINATION OF PATHS, where each PATH
IN THIS COMBINATION is an invalid TSP path.
Diaby needs to, or someone in the scientific community needs to,
prove/disprove that using a solid mathematical proof.
-Deepak
kin...@freemail.it
deepakc ha scritto:
> Rados³aw Hofman wrote:
> > For n=10 there would be 100!/4=X/4*10^24=[BIG NUMBER]*10^24
> > it should be "for n=100" - rest is OK :-)
> >
> > Cheers
> > Radek Hofman
>
>
> Dear Mr. Hofman,
>
> Please carefully read my post number "105", and that should answer your
> above Question.
>
> According to me, the correctness of Diaby's Algorithm has absolutely
> nothing to do with size of the TSP. Diaby's Algorithm can fail, whether
> it has 4 cities or 40 cities or 400 cities, and the reason for that is
> because of the relaxation from ILP to LP.
>
> So according to me, the only flaw with Diaby's Algorithm is QUESTION-2,
> which is: - Prove that it is possible for Diaby's Algorithm to generate
> a correct solution for the CONVEX COMBINATION OF PATHS, where each PATH
> IN THIS COMBINATION is an invalid TSP path.
If what you say is correct, maybe it is more simple to show a counter
example with a lower number of cities than that found by Mr. Hofman.
That would allow the Diaby's algorithm to run... :)
deepakc
Hmmm...that will be possible, in my opinion. We could try and find a
counter-example, say with 6 cities, or 8 cities or 10 cities or 12
cities. But we have to do a lot of "playing around" with the inter-city
costs, before such a counter-example for Diaby's Algorithm is found.
In fact, I would like to modify my above phrase from "Diaby's Algorithm
is absolutely independent of TSP size" to "the probability of finding a
counter-example increases with TSP size". And the reason is because the
overall number of constraints in Diaby's Model exceeds the number of
possible TSP tours, when N=6,8,10, or 12.
But I will stress that IT IS DEFINITELY POSSIBLE, for us to find a
counter-example for Diaby's Algorithm, when the N=6, 8, 10, etc. This
is because of the ILP to LP relaxation. But as I said, we have to a lot
of playing around with inter-city costs, and some very good computers &
programs could help us do that.
-Deepak
deepakc
The statement of the final Task is: "Prove that for a Generic TSP, it
is possible for Diaby's Algorithm to generate an optimal solution for
the CONVEX COMBINATION OF PATHS, where each PATH IN THIS COMBINATION is
incorrect (i.e. either an invalid TSP path, or a non-optimal TSP
path)."
The above Task needs to be proved/disproved, either mathematically, or
via a counter-example (with maybe as low as 6 cities).
I personally share the opinion of Hofman, Bryan Olson, Pat Shanahan,
Tim Chow, AL, David Moews, etc...... that Diaby's Algorithm is capable
of giving incorrect TSP paths.
But let us be fair to Dr. Diaby, and see what is the final outcome.
Patricia Shanahan
...
> I personally share the opinion of Hofman, Bryan Olson, Pat Shanahan,
> Tim Chow, AL, David Moews, etc...... that Diaby's Algorithm is capable
> of giving incorrect TSP paths.
I have not actually expressed that opinion. My opinion on the matter has
two parts:
1. Proof that the result must correspond to a valid TSP path is essential.
2. I could not find that proof in the version of his paper that I read.
I have not had time to look into the claimed counter-example.
Patricia
deepakc
Ok Patricia.
deepakc
6 cities (execution time of which shud be completed within
minutes)....I would like to advise you, to try with large variations in
the inter-city distances.
eg. with 4 cities having 6 edges...try with edge1=100000, edge2=1,
edge3=10000000000, edge4=55, and so on.
These large variations might just defeat the constraints, even though
number of contraints is greater than number of tours.
Also important....DO NOT USE DECIMAL values (like 10.00456), because we
do not want any rounding-off errors to occur in your computer.
deepakc
further to my above posting, let me add that it will be an even better
idea to use some groups of edges with small variations, and some groups
edges with large variations. That way we could cheat the constraints to
make Diaby's Algo give an (invalid/non-optimal) TSP tour.
eg. edge1=1, edge2=3, edge3=100000, edge4=100000005, edge5=5888855,
edge6=556, edge7=557, edge8=558, and so on
deepakc
deepakc
find out counter-example.
Just take a look at the 8-city TSPs, used in Diaby's paper. You find
that the inter-city costs vary from only 1 to 250. But the number of
constraints generated when N=8, is certainly more than 250. That was
perhaps why Diaby was always getting results lying on the TSP Polytope,
not outside it. U see what I mean.
So my advise is that while choosing the inter-city costs, try to use a
combination of those with LARGE variation, and those with SMALL
variation, which might just force the result to come out of the TSP
Polytope (i.e. become an invalid tour). The SMALL variation makes the
variables think in one way and the LARGE variation makes the variables
think in another way, and then BOOM !!!, the final result might just
come out of the TSP Polytope.
All that is "meta" thinking, but I hope you're getting the picture.
So please use maybe 4 city, 5 city, or 6 city TSPs (so that too much of
your time is not lost), and try out with such inter-city costs,
examples of which I have already posted in my above post.
Hope we are able to get an interesting result, in the next few days.
Radoslaw Hofman
I have missed part of discussion but I will get back to it and reply. If you
want to find counter example then I advise you to follow way I was going
through - first think of model with only x_isj. If you are able to state all
restrictions for x's and find counter example for them then you will get
idea (see fig 2 in my paper).
Counter example for y_isj,upv is combination of solutions which each was
counter-example for x's... putting them together creates counter-example.
Same with z's.
I'm sceptic that you will be able to find algorithm with lower number of
cities. Try to think not only about Diaby's restrictions but all possible.
Mine counter example is good for Diaby's BLP model but not for any model for
z variables - one may build better one and then we would have required 52
cities (remember that Moews predicted 59 as required theoretical number of
cities).
Best regards,
Radek Hofman
Radoslaw Hofman
Hi,
I do agree :-). Me remark about possible number of solution was only to show
that difference between IP and LP is such that IP gives ONE solution (there
are O(n!) solutions), and LP returns set of solutions (there are O(2^n!)
sets of solutions). Intuitively such change (after relaxation of integer
requirement) should then be conected with changing "expression abilites" of
algorith,
I agree (and I wrote it prevoiusly) that it isn't critical - method could
have been correct with this... But it is not.
Best regards,
Radek Hofman
Radosław Hofman
Hi,
See my coments below:
Użytkownik "deepakc" <dee...@pmail.ntu.edu.sg> napisał w wiadomości
news:1163174545.3...@m73g2000cwd.googlegroups.com...
>Please carefully read my post number "105", and that should answer your
>above Question.
Sorry, I don;t see which post do you mean - could you paste some text?
> According to me, the correctness of Diaby's Algorithm has absolutely
> nothing to do with size of the TSP. Diaby's Algorithm can fail, whether
> it has 4 cities or 40 cities or 400 cities, and the reason for that is
> because of the relaxation from ILP to LP.
I don't agree - it works perfectly for small n. If n is less then 10 than
properly implemented it should give only correct solutions.
> So according to me, the only flaw with Diaby's Algorithm is QUESTION-2,
> which is: - Prove that it is possible for Diaby's Algorithm to generate
> a correct solution for the CONVEX COMBINATION OF PATHS, where each PATH
> IN THIS COMBINATION is an invalid TSP path.
> Diaby needs to, or someone in the scientific community needs to,
> prove/disprove that using a solid mathematical proof.
> -Deepak
Agree. Puting it in formula. Diaby has to prove that:
forall b in BLP-feasible-solutions exists T subset TSP-tours
overallCost(b)=combination(overallCost(T))
In my opinion my counter example makes it impossible becouse I have shown
that:
exists b in BLP-feasible-solutions forall t in TSP-tours
overallCost(b)<overallCost(t)
For memory of my "first question" i shall put it also in formula. I wanted
to show that:
forall T subset TSP-solutions forall S subset TSP-solutions exists b in
BLP-feasible-solutions exists c in BLP-feasible-solutions
overallCost(b)=combination(overallCost(T)) and
overallCost(c)=combination(overallCost(S)) and T!=S and
overallCost(b)=overallCost(c)
This means that relation between BLP-feasible solutions and sets of
TSP-tours is not one-to-one - there are many sets with same BLP solution
expressing them.
And as I mentioned - this is not criticsl - it is to show complexity of
problem.
Best regards,
Radek Hofman
Radoslaw Hofman
Uzytkownik <kin...@freemail.it> napisal w wiadomosci
news:1163175513.4...@e3g2000cwe.googlegroups.com...
> If what you say is correct, maybe it is more simple to show a counter
> example with a lower number of cities than that found by Mr. Hofman.
> That would allow the Diaby's algorithm to run... :)
But it is possible to run it with 32 nodes... you anly have to omitt
variables which we know are equal to zero. Because we know value of EVERY
variable it is possible to identify equation containing only zero-variables
and we can omitt generating of such equation. Then number of non-zero
variables is not so large and there are less then 1 million of equations...
I can calculate it on my laptop :).
If Diaby had shown his source code then I could have implemented such
"cut-offs" (only for variables equal to zero and equations containing only
zeros) making it work for my counter-example.
Best regards,
Radek Hofman
Radoslaw Hofman
king...@freemail.it wrote:
> Hmmm...that will be possible, in my opinion. We could try and find a
> counter-example, say with 6 cities, or 8 cities or 10 cities or 12
> cities. But we have to do a lot of "playing around" with the inter-city
> costs, before such a counter-example for Diaby's Algorithm is found.
> In fact, I would like to modify my above phrase from "Diaby's Algorithm
> is absolutely independent of TSP size" to "the probability of finding a
> counter-example increases with TSP size". And the reason is because the
> overall number of constraints in Diaby's Model exceeds the number of
> possible TSP tours, when N=6,8,10, or 12.
> But I will stress that IT IS DEFINITELY POSSIBLE, for us to find a
> counter-example for Diaby's Algorithm, when the N=6, 8, 10, etc. This
> is because of the ILP to LP relaxation. But as I said, we have to a lot
> of playing around with inter-city costs, and some very good computers &
> programs could help us do that.
Maybe it is possible to create such combination for small instances - my
goal was to to show that it has lower overall cost... It took me 32
cities... But if Diaby would have be more precise with his model (BLP would
have contained equation 2.13) then it would have been to weak - I would have
used 52 cities (remember that Moews predicted theoretical number of 59 as
"killing" for algorithm).
Best regards,
Radek Hofman