Prev: 2000 solution manuals, solution manual, Student Study Guide solutions
Next: Example for a non-rec.enum. language whose complement isn't rec.enum., too.
From: moustapha.diaby on 4 Jun 2008 16:54
On Jun 4, 1:04 pm, Rados³aw Hofman <rad...(a)saso.org.pl> wrote:
> Hello,
>
> Thanks for your questions. Below sou May find my answers. I have
> addend smaller example (exactly the same idea) to paper avaliable on
> my webpage (http://www.teycom.pl/docs/Report_on_article_The_Travelling_Salesman_P...
> ), so please use it for ilustration of my answers (pages 6-8).
>
> But please remember that this smaller example is to present ides.
> Maybe it is possible to use it as final CE (I have started
> calculations but they require much time).
>
> This smaller example consists of 27 nodes (24 in "Group"). Optimal TSP
> tour (there are 480 optimal solutions) is 132 (one example: 1->2->3-
>
> >24->23->17->15->12->11->5->4->6->7->9->8->26->25->22->20->14->13->10-
> >16->18->19->21->27). Linear model gives value 34.75.
>
> I have added also tables presenting nested flow. For example for
> y_3,15,14,*,*,*. In "smaller example" there are only 4 types of arcs
> (horizontal, vertical, internal horizontal to vertical and internal
> horizontal to horizontal) - you may find example fulfilling equations
> 6, 7, 8 and 11. Fulfillment of sum on every stage requirement (9, 10)
> is to be done by symmetric use of algorithms generating sub-graphs -
> at every stage we use exactly the same patterns so it is only matter
> of using proper values, not problem of being impossible.
>
> I have not time to create assignments fulfilling rest of restrictions,
> and I am not sure if it is possible for this smaller instance, but I
> am sure you will be able to get the idea, and see that it is possible.
> What is left is to prepare such arrangements that for sum of arcs in
> nested graphs it will return values desired at upper level - this is
> not a problem in general, but requires analysis and some time (maybe
> somebody else is interested in doing it).
>
> 1. Draw out your extended graph with all the nodes clearly labeled
> (however way is convenient);
> => I have added it for "Smaller example". Expansion of larger one
> follows the same idea - I hope that this is understandable.
> 2. Indicate what arcs are "external arcs" (may be, use different
> color, or make them bold);
> => I have made thicker lines on picture - "internal" are only there
> when node was replaced to three nodes, and it refers to flow between
> them
> 3. Give the arc costs for the extended graph in a table (including all
> the "big cost") (typical way: rows are beginning nodes of arcs;
> columns are end nodes; No need to have entries for cells that do not
> correspond to arcs));
> => OK, added for "small example", but I have left "big costs" to empty
> - in my calculations I assign 100 for those costs
> 4. Give details of one example of "optimal TSP tour" (You could
> highlight on the graph, or just give the sequence of cities: Ex: 1 ==>
> 2 ==> ... ==> x);
> => as above
> 5. Clearly indicate what paths are used at the first step of your
> procedure to send 1/48 units of flow to each of the nodes in "Group."
> => I am not sure what do you expect me to answer. In my flow each flow
> at stage 2 is:
> - starts from node no 2
> - ends in "Group"
> - carries 1/48 (1/24 in "small example") of total flow
> Refering to variables I have:
> y_2,2,3,2,2,3=1/48; y_2,2,4,2,2,4=1/48; y_2,2,5,2,2,5=1/48; ...
> y_2,2,50,2,2,50=1/48;
>
> Please do not hesitate to write if you will have further questions. I
> may not be able to answer immediately but after a while I will.
>
> Best regards,
>
> Radek Hofman



I thank you for the information. I have quickly skimmed thru it and
have a couple of remarks:

1. In figure 3, the costs on the arcs in the "dummy cycle" have costs
= 0; in the illustrative example they are 2's. So, I am not sure the
TSP over the extended graph is not the same as the original TSP in the
example;

2. The flow patterns you have in Tables 2-5 (for ex: the sequence of
cities 1-2-19-18-16-15-12-15... would not be permissible if you write
the constraints of my model in terms of the y-variables only, (Flow
still does not "return" to a previously visited level).

Best.

//MD


From: Rados�aw Hofman on 5 Jun 2008 03:48
>1. In figure 3, the costs on the arcs in the "dummy cycle" have costs
>= 0; in the illustrative example they are 2's. So, I am not sure the
>TSP over the extended graph is not the same as the original TSP in the
>example;

You are right - 0 is a concept, but in fact I use 2 and 1 (1 for replacement
of node with 2 arcs) to distinguish arcs (for easiness of writing algorithm
:-) ). It does not change idea since optimal TSP is greater then 100 - it
does not matter if LP returns 32, 37, or even 99 - it is to low value to be
correct.

>2. The flow patterns you have in Tables 2-5 (for ex: the sequence of
>cities 1-2-19-18-16-15-12-15... would not be permissible if you write
>the constraints of my model in terms of the y-variables only, (Flow
>still does not "return" to a previously visited level).

In these tables there are variables for example z_1,1,2,3,15,4,*,*,*

If you put this "returns" in z variable there is no constraint for return.
To have such constraint you would need next level, but it would be shifting
of problem to deeper level. I assume that because you are using only z_1,1,2
that y_i,s,j,k,r,t=z_1,1,2,i,s,j,k,r,t. If you have a check this "return"
issue you will discover that in fact restrictions for y variables for
"returning" are removed:

y_11,15,12,12,16,15 => y_11,15,12,15,17,16 =>
y_11,15,12,16,18,18 => y_11,15,12,18,19,16 (return in this step)

then the only way of restricting such flow is z_11,15,12,16,18,18,*,*,* -
but there are not such z's.

Of course as I have written before - you can get z's back... but the problem
will shift into lower level - there will be no possibility to prevent
"returns" in this flow:

z_11,15,12,12,16,15,15,17,16 => z_11,15,12,12,16,15,16,18,17 =>
z_11,15,12,12,16,15,17,19,20 => z_11,15,12,12,16,15,20,20,17 (return in this
step)

This is still the same problem which exists in LP model for x variables. If
you add y's then you shift this problem to lower level. After adding z level
where problem exists is decreasing.



From my point of view - the most important question was: is TSP such a
problem then using LP you would have idea that optimal TSP are organized in
linear facets of TSP polytope (in other words - is it possible to find CE
for y's). This was very difficult and many times I thought that it is
impossible... But, finally I know how to show that it is possible. Problem
with next dimensions is much easier - we have target function on x level, so
if we know how to get instance for y then we can use the same idea to get
instance for z and next dimensions.



Best regards,



Radek Hofman




From: moustapha.diaby on 5 Jun 2008 07:47
On Jun 5, 3:48 am, "Rados³aw Hofman" <rad...(a)teycom.pl> wrote:
> >1. In figure 3, the costs on the arcs in the "dummy cycle" have costs
> >= 0; in the illustrative example they are 2's. So, I am not sure the
> >TSP over the extended graph is not the same as the original TSP in the
> >example;
>
> You are right - 0 is a concept, but in fact I use 2 and 1 (1 for replacement
> of node with 2 arcs) to distinguish arcs (for easiness of writing algorithm
> :-) ). It does not change idea since optimal TSP is greater then 100 - it
> does not matter if LP returns 32, 37, or even 99 - it is to low value to be
> correct.
>

*******OK.

> >2. The flow patterns you have in Tables 2-5 (for ex: the sequence of
> >cities 1-2-19-18-16-15-12-15... would not be permissible if you write
> >the constraints of my model in terms of the y-variables only, (Flow
> >still does not "return" to a previously visited level).
>
> In these tables there are variables for example z_1,1,2,3,15,4,*,*,*
>
> If you put this "returns" in z variable there is no constraint for return.
> To have such constraint you would need next level, but it would be shifting
> of problem to deeper level. I assume that because you are using only z_1,1,2
> that y_i,s,j,k,r,t=z_1,1,2,i,s,j,k,r,t. If you have a check this "return"
> issue you will discover that in fact restrictions for y variables for
> "returning" are removed:
>

******* This is incorrect.

> From my point of view - the most important question was: is TSP such a
> problem then using LP you would have idea that optimal TSP are organized in
> linear facets of TSP polytope (in other words - is it possible to find CE
> for y's). This was very difficult and many times I thought that it is
> impossible... But, finally I know how to show that it is possible.

******** I too believe that the TSP polytope cannot be described with
a number of linear constraints bounded by a polynomial function of the
number of cities. What I do in my work however, is to express the TSP
as an optimization problem over a reformulation of the Assignment
Polytope. So, I don't deal with the TSP polytope at all.

In the previous versions I was using O(n^9) variables. The current
version is a simplified one with O(n^8) variables. It has now come to
my attention that it may actually be possible to simplify further.
But, at any rate, I feel pretty confident that a valid counter-example
cannot be constructed the way you are proceeding.

Best,

//MD




From: Radoslaw Hofman on 5 Jun 2008 08:15

Uzytkownik <moustapha.diaby(a)business.uconn.edu> napisal w wiadomosci
news:b9070633-1c36-4834-a18e-40ac372f3dc1(a)m3g2000hsc.googlegroups.com...
> >2. The flow patterns you have in Tables 2-5 (for ex: the sequence of
> >cities 1-2-19-18-16-15-12-15... would not be permissible if you write
> >the constraints of my model in terms of the y-variables only, (Flow
> >still does not "return" to a previously visited level).
>
> In these tables there are variables for example z_1,1,2,3,15,4,*,*,*
>
> If you put this "returns" in z variable there is no constraint for
return.
> To have such constraint you would need next level, but it would be
shifting
> of problem to deeper level. I assume that because you are using only
z_1,1,2
> that y_i,s,j,k,r,t=z_1,1,2,i,s,j,k,r,t. If you have a check this "return"
> issue you will discover that in fact restrictions for y variables for
> "returning" are removed:

******* This is incorrect.

What is incorrect in above? Which restriction will prevent such "returns"?

> From my point of view - the most important question was: is TSP such a
> problem then using LP you would have idea that optimal TSP are organized
> in
> linear facets of TSP polytope (in other words - is it possible to find CE
> for y's). This was very difficult and many times I thought that it is
> impossible... But, finally I know how to show that it is possible.

******** I too believe that the TSP polytope cannot be described with
a number of linear constraints bounded by a polynomial function of the
number of cities. What I do in my work however, is to express the TSP
as an optimization problem over a reformulation of the Assignment
Polytope. So, I don't deal with the TSP polytope at all.

=> That was past - now I am pretty confident that valid CE may be
constructed.

Best regards,

Radek Hofman


From: moustapha.diaby on 5 Jun 2008 09:53
On Jun 5, 8:15 am, "Radoslaw Hofman" <rad...(a)teycom.pl> wrote:
> Uzytkownik <moustapha.di...(a)business.uconn.edu> napisal w wiadomoscinews:b9070633-1c36-4834-a18e-40ac372f3dc1(a)m3g2000hsc.googlegroups.com...
>  > >2. The flow patterns you have in Tables 2-5 (for ex: the sequence of
>  > >cities 1-2-19-18-16-15-12-15... would not be permissible if you write
>  > >the constraints of my model in terms of the y-variables only, (Flow
>  > >still does not "return" to a previously visited level).
>  >
>  > In these tables there are variables for example z_1,1,2,3,15,4,*,*,*
>  >
>  > If you put this "returns" in z variable there is no constraint for
> return.
>  > To have such constraint you would need next level, but it would be
> shifting
>  > of problem to deeper level. I assume that because you are using only
> z_1,1,2
>  > that y_i,s,j,k,r,t=z_1,1,2,i,s,j,k,r,t. If you have a check this "return"
>  > issue you will discover that in fact restrictions for y variables for
>  > "returning" are removed:
>
> ******* This is incorrect.
>
> What is incorrect in above? Which restriction will prevent such "returns"?

The y-variable versions of the flow propagation constraints, i.e.:

(A) sum_v {y(v,s-1,t irj)} - sum_v {y(tsv irj)} r,s Stages indices:
r >= 3, 1<s<r; i,j,t city indices
(B) sum_v {y(irj v,s-1,t)} - sum_v {y(irj tsv)} r,s Stages indices:
r <= n-3, s>r+2; i,j,t city indices

in combination with the other constraints.

>
> > From my point of view - the most important question was: is TSP such a
> > problem then using LP you would have idea that optimal TSP are organized
> > in
> > linear facets of TSP polytope (in other words - is it possible to find CE
> > for y's). This was very difficult and many times I thought that it is
> > impossible... But, finally I know how to show that it is possible.
>
> ******** I too believe that the TSP polytope cannot be described with
> a number of linear constraints bounded by a polynomial function of the
> number of cities.  What I do in my work however, is to express the TSP
> as an optimization problem over a reformulation of the Assignment
> Polytope. So, I don't deal with the TSP polytope at all.
>
> => That was past - now I am pretty confident that valid CE may be
> constructed.
>

OK, I am waiting for it.

//MD
 |  Next  |  Last
Pages: 1 2 3 4
Prev: 2000 solution manuals, solution manual, Student Study Guide solutions
Next: Example for a non-rec.enum. language whose complement isn't rec.enum., too.