Extended counter-example for extended M.Diaby Linear Model
in [Theory]
|
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: Radoslaw Hofman on 5 Jun 2008 10:04 Uzytkownik <moustapha.diaby(a)business.uconn.edu> napisal w wiadomosci news:54eeeaf4-f944-41ff-a768-d2d9286e59f2(a)a70g2000hsh.googlegroups.com... On Jun 5, 8:15 am, "Radoslaw Hofman" <rad...(a)teycom.pl> wrote: > 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. => this is only SUM, so if values are correct then there is no restriction for "return". You cannot have return on x level because of y construction, but there is no restriction for y because you have turned z off... Anyway - it works (check my previous CE - there were returns as well and no constraint was able to prevent it even for z variables. Difference between your previous and current model is all about sum in subgraph, and I do show how to prepare instance for this requirement also. I have proved previously that all other constraints can be easily fulfilled, so why do you get back to it claiming that is impossible... Restrictions you have mentioned were present in model previously so this is not an argument that they can help with such a flow. > => That was past - now I am pretty confident that valid CE may be > constructed. > OK, I am waiting for it. => you have it in this paper... Maybe you will show solution for this smaller example? Best regards, Radek Hofman
From: moustapha.diaby on 5 Jun 2008 10:25 On Jun 5, 10:04 am, "Radoslaw Hofman" <rad...(a)teycom.pl> wrote: > Uzytkownik <moustapha.di...(a)business.uconn.edu> napisal w wiadomoscinews:54eeeaf4-f944-41ff-a768-d2d9286e59f2(a)a70g2000hsh.googlegroups.com... > On Jun 5, 8:15 am, "Radoslaw Hofman" <rad...(a)teycom.pl> wrote: > > > 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. > > => this is only SUM, so if values are correct then there is no restriction > for "return". You cannot have return on x level because of y construction, > but there is no restriction for y because you have turned z off... Anyway - > it works (check my previous CE - there were returns as well and no > constraint was able to prevent it even for z variables. Difference between > your previous and current model is all about sum in subgraph, and I do show > how to prepare instance for this requirement also. > No, it is not only "sum." There is labeling of the flows too. If you look at the constraints I have just stated. > I have proved previously that all other constraints can be easily fulfilled, > so why do you get back to it claiming that is impossible... Restrictions you > have mentioned were present in model previously so this is not an argument > that they can help with such a flow. The flow propagation constraints in the relaxation on which you based your previous "counter-example" on were different. That is one of the reasons, why the principle of that "counter-example" cannot be applied to my published n^9 model. It is the same case for the discussion we are having. > > > => That was past - now I am pretty confident that valid CE may be > > constructed. > > OK, I am waiting for it. > > => you have it in this paper... Maybe you will show solution for this > smaller example? > You are the one making the claim. I have provided the eqns that must be satisfied. Now, it is up to you to put up the exact values for the y-variables in your example, so that the claim can be verified.
From: Radosław Hofman on 11 Jun 2008 03:03 Hi, Just letting you know that calculations are still in progress for "small CE". I have implemented database based Gauss-Jordan elimination to reduce number of equations and variables and it is running... Maybe somebody could put it to an super-computer? Requirements: PERL+DBI+DBD::mysql, MySQL, 10 GB of hdd space. Best regards, Radek Hofman
From: moustapha.diaby on 11 Jun 2008 12:12 On Jun 11, 3:03 am, Rados³aw Hofman <rad...(a)teycom.pl> wrote: > Hi, > > Just letting you know that calculations are still in progress for "small > CE". I have implemented database based Gauss-Jordan elimination to reduce > number of equations and variables and it is running... > > Maybe somebody could put it to an super-computer? Requirements: > PERL+DBI+DBD::mysql, MySQL, 10 GB of hdd space. > > Best regards, > > Radek Hofman In the spirit of fairness, and looking back, there is some merit to the reduction you suggested for the special-case TSP you are considering, as it has made me realize that my n^8 model (and therefore, my n^9 model) can be simplified further: The projection of my n^8 (or n^9) model onto the y-variable space actually yields a correct model also. I think that perhaps, I should have communicated this more clearly. With that said however, I think you are trying to make much more out of this than can be done (as you did before). I have taken some time to put the simplified model (and proof sketches) on paper, and to do a VBA implementation. I will do a post as soon as I am able, in the hope that that will be helpful in "cutting thru the chase." Best, //MD
From: moustapha.diaby on 11 Jun 2008 14:13
On Jun 11, 12:12 pm, moustapha.di...(a)business.uconn.edu wrote: > On Jun 11, 3:03 am, Rados³aw Hofman <rad...(a)teycom.pl> wrote: > > > Hi, > > > Just letting you know that calculations are still in progress for "small > > CE". I have implemented database based Gauss-Jordan elimination to reduce > > number of equations and variables and it is running... > > > Maybe somebody could put it to an super-computer? Requirements: > > PERL+DBI+DBD::mysql, MySQL, 10 GB of hdd space. > > > Best regards, > > > Radek Hofman > > In the spirit of fairness, and looking back, there is some merit to > the reduction you suggested for the special-case TSP you are > considering, as it has made me realize that my n^8 model (and > therefore, my n^9 model) can be simplified further: The projection of > my n^8 (or n^9) model onto the y-variable space actually yields a > correct model also. > > I think that perhaps, I should have communicated this more clearly. > > With that said however, I think you are trying to make much more out > of this than can be done (as you did before). > > I have taken some time to put the simplified model (and proof > sketches) on paper, and to do a VBA implementation. I will do a post > as soon as I am able, in the hope that that will be helpful in > "cutting thru the chase." > > Best, > > //MD A statement of the simplified (n^6) model is available at: http://www.business.uconn.edu/users/mdiaby/n6tsplp/n6tsplp-smry.pdf The VBA implementation is available at: http://www.business.uconn.edu/users/mdiaby/n6tsplp/n6tsplp(0).xlsm //MD |