Re: My LP Formulation of the TSP: Conclusions

On Mar 31, 4:05 am, "Radoslaw Hofman" <rad...@xxxxxxxxx> wrote:
Uzytkownik <moustapha.di...@xxxxxxxxxxxxxxxxxx> napisal w wiadomoscinews: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

If you have done it, why aren't you sure?


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


Oh, please, you don't have to worry about convincing me!


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,

Someone has suggested in this forum that you went to a better school
than I. What did you go to that school for? Could it simply be that
every time your "nakedness" is about to fully unmasked, you adeptly
revert to the innocent, humble "Ph.D. student"?

- maybe you do
not want to get inside sense of my objections...

I have continuously done so. Even in this thread.
Problem is that you are clueless about a lot of the basics as amply
demonstrated in this thread itself.

So, as I have suggested before, let's all just use a "put up" or "shut
up" approach from now on.

//MD

.

Relevant Pages