Re: My LP Formulation of the TSP: Conclusions



Uzytkownik <moustapha.diaby@xxxxxxxxxxxxxxxxxx> napisal w wiadomosci
news:1175296170.102187.189010@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

On Mar 30, 3:59 pm, t...@xxxxxxxxxxxxx wrote:
I am waiting to see Hofman's counter-examples (or yours for that
matter) for my model in the IMECS proceedings (since he says his
"construction" scheme did not depend on the removal of the "visit"
constraints from that model) and for my final model I just made
public.

I thought that if you want to prove something then you should follow one of
well known proof patterns: you could prove by contradiction that your BLP
model is correct (assuming that there exists some solution - lets name it
HofCE - and that leads to contradiction in MATH formulas), or you may build
constructive proof showing WHY your model is correct.



I have written some time ago that couple of years ago I was building models
for NP-complete problems by myself. I have also prepared something similar
(not to say exactly the same) model to yours. It was complicated even for me
as inventor, so I had such idea "let's publish it, because no one ever will
be able to provide counter example". It was just an naïve thought - I have
decided to first remove all doubts, and prove to myself that it is correct.
While trying to prove it I have discovered factors showing that it is
impossible to have such model correctly solving large instances (I was
running experiments for N=1000, not N=10 like you. my models were perfect
even for N=100 that is why I needed to check for larger instances).



And.. I am not "science worker", not "academic teacher". But I could have
presented above attitude.



My objection to your model (see previous posts) mainly consider such
approach - let's forget that we know phenomenon known as "assignment
polytope" and let us discuss factors of YOUR polytope and WHY it is
impossible to obtain not correct solutions using this model. Remember that
YOU are writing that it is assignment polytope, but you do not prove that
BLP is EQUIVALENT to such object (having no additional properties).



In my opinion if we took symmetric polytope (this one which was proved by
Yanakakkis to be incorrect) and remove it's symmetry (if there are two
symmetric variables then we leave one of them and add condition that the
other one is invalid) then we will obtain EXACTLY your model. If you do not
add anything to model, only remove it's direct symmetry then expectation
that it is correct is rather naive.



Getting back to Counter Example - I do have idea how to prepare CE showing
that 2.13 does not introduce any new quality, but as I have written before

- CE may be to large to compute

- I want to show it on your source codes, because you do not consider mine
as worth reading



In original paper there is consideration how this CE should look like, and
we can trivialize it to condition shown in my CE paper on page 14: This
solution can be "defeated" by additional restriction (corresponding to 2.25
from old version of article, 2.13 from new version)... You consider z's only
for first stage so if we refer to way mine CE are built, it is exactly
equivalent to condition for y's (sum of flow through every arc has to
"reach" every node with same value). But as I have written - I could try to
show it, but on your codes (and now I am quite busy with my job and PhD
thesis, so I expect to have time during summer holidays - if your article
appeared in some journal to that moment that is even better for me - mine CE
will be also published in same journal :) ).



I am a bit bored with answering same arguments all over again - maybe you do
not want to get inside sense of my objections... Please - take some time,
and provide us with some proofs, scientific arguments and so on, so we could
use our knowledge to consider your position (now it is enough to be able to
quarrel and weave hands).



Radek Hofman


.

Relevant Pages

  • Re: My LP Formulation of the TSP: Conclusions
    ... constraints from that model) and for my final model I just made ... While trying to prove it I have discovered factors showing that it is ... polytope" and let us discuss factors of YOUR polytope and WHY it is ... Yanakakkis to be incorrect) and remove it's symmetry (if there are two ...
    (comp.theory)
  • Re: Bring Math Arguments against this FERMAT LAST THEOREM PROOF
    ... Ok, but the objection is very simple, so it needs to be addressed. ... multiple of 3, so if you want all the variables X,Y,Z to be not ... The reason we need 2 subcases, even though they appear to be nearly ... assume X<=Y, then that symmetry would also be broken, and then you ...
    (sci.math)