🚀 go-pugleaf

reeds@alice.att.com (Jim Reeds) writes:



>jmr@cs.anu.edu.au (Mike Robson) writes:

>>[...]
>>I'll go back to trying to decide if the current Gismondi and Swart
>>linear programming formulation has the required property (that every
>>solution covers a permutation). If that claim is true, then I think
>>my approach is a good way to try and prove it.

>This is rather more than G&S themselves state.  If every point in the
>feasible region covers a permutation, then the extreme points of the
>feasible region are exactly the permutations, and hence every point in
>the feasible region is expressible as a convex combination of permutations.

I should have been more precise. I think they are claiming that every
solution has covers the s and t variables of a permutation (not the u).
I think that gets round your argument; if not things look bad.

>But all G&S claim is that any solution is expresible as an affine
>combination of permutations, with AT MOST ONE NEGATIVE COEFFICIENT.

Where did they claim that?

>(I would like to see a real proof that any solution is expressible
>as an affine combination of permutations, regardless of sign.  Equivalently,
>I'd like to know the dimension of the affine hull of the G&S feasible
>region.)

They claim to have a complete proof based on the dimensions of the spaces
involved but I haven't seen any details.
I have an idea of how to construct a proof by taking an arbitrary
solution and systematically zeroing out all u variables except those
of the identity permutation vector. This can be done by subtracting
carefully chosen permutations, possibly preceded by adding other
permutations which don't involve any u variables except the ones
which you haven't got round to yet.
>Jim

Mike.