Re: Re: Re: Re: optimally picking one element from each list

*To*: mathgroup at smc.vnet.net*Subject*: [mg48383] Re: [mg48333] Re: [mg48324] Re: [mg48308] Re: [mg48297] optimally picking one element from each list*From*: DrBob <drbob at bigfoot.com>*Date*: Wed, 26 May 2004 02:41:45 -0400 (EDT)*References*: <200405220704.DAA08848@smc.vnet.net> <200405231015.GAA21155@smc.vnet.net> <200405240445.AAA08868@smc.vnet.net> <200405251116.HAA03559@smc.vnet.net> <40B3773D.4090501@wolfram.com>*Sender*: owner-wri-mathgroup at wolfram.com

My second solution may or may not be equivalent to what you're proposing -- you lost me in the details -- but the thought process behind it seems more straightforward, at least. I drew the problem as a network, named the nodes and arcs, and set up the LP tableau from that, using rules that paid attention to the names I'd chosen. Because it comes from a shortest-path network problem, it's guaranteed to be unimodular, hence basic solutions are integer. It doesn't begin as a quadratic problem, so things are a little less complicated. In the optimalSplit routine, I left all that transparent, rather than optimizing the setup process, which might obscure the thought process. I'm thinking of writing a threshold shortest-path code like the one I wrote in Fortran for my dissertation, years ago. That would simplify the setup, as I'd eliminate the tableau and input the arcs directly. It might speed up the solution, as well, although LinearProgramming is certainly fast already. Bobby On Tue, 25 May 2004 11:41:33 -0500, Daniel Lichtblau <danl at wolfram.com> wrote: > DrBob wrote: >> Oops, more testing shows that's not quite right! I'm working on a solution, using LinearProgramming. >> >> Bobby > > > I doubt I'll have time to code this, but a linear programming solution > can be fashioned roughly as follows. > > Say the lists are > > { {a[1,1],...,a[1,k[1]]}, > {a[2,1],...,a[2,k[2]]}, > ..., > {a[m,1],...,a[m,k[m]]} } > > To start we define corresponding variables x[1,1],...,x[m,km]. We have > constraints x[i,j]>=0 for all {i,j} in appropriate ranges, and moreover > > x[1,1]+...+x[1,k[1]]==1 > ... > x[m,1]+...+x[m,k[m]]==1 > > Now define constants v[i,j,s,t] = 1 - KroneckerDelta[a[i,j]-a[s,t]] > > Then we wish to minimize > > Sum[v[s-1,j,s,t] * x[i,j] * x[s,t], {s,2,m}] > > subject to all the constraints. > > > Note that > > (1) I have not proved that this gives a correct result for 0-1 values of > the variables (but it does). > > (2) It's a quadratic programming problem. > > To reformulate as a linear problem, first define new variables > > y[i,j,s,t] == x[i,j]*x[s,t] > > Now we must modify constraints. But notice that we still have > > 0<=y[i,j,s,t]<=1 > > and moreover by multiplying consecutive pairs of the original constraint > equations we have, for example, > > (x[i,1]+...+x[i,k1])*(x[i+1,1]+...+x[i+1,k[i+1]]) == 1 > > When expanded and rewritten in terms of the new variables this will give > necessary conditions on the y[i,j,s,t]. But we also have to insist that > if y[i,j,s,t] == 1, then some y[s,t,u,v] also is 1 (roughly, in looking > at consecutive pairs, once we pick x[s,t] as the right neighbor of some > x[i,j], it must also be the left neighbor of some x[u,v]). > > This extra condition may be enforced by adding constraints of the form > > (x[2,1]+...+x[1,k[1]])*x[2,1] == (x[3,1]+...+x[3,k[3]])*x[2,1] > ... > (x[2,1]+...+x[1,k[1]])*x[2,k[2]] == (x[3,1]+...+x[3,k[3]])*x[2,k[2]] > ... > (x[m-2,1]+...+x[m-2,k[m-2]])*x[m-1,1] == (x[m,1]+...+x[m,k[m]])*x[m-1,1] > ... > (x[m-2,1]+...+x[m-2,k[m-2]])*x[m-1,k[m-1]] == > (x[m,1]+...+x[m,k[m]])*x[m-1,k[m-1]] > > Of course these get rewritten in terms of the new variables y[i,j,s,t]. > > > This may correspond to what you are doing, I'm not sure. In any case, > I'd think Carl Woll's longest intersections method would be faster on > problems of any size. But his is in some sense less general, insofar as > modification of the objective might make it more difficult or impossible > to extend his method in situations where a linear programming method > would still be viable. > > > Daniel > > > -- Using M2, Opera's revolutionary e-mail client: http://www.opera.com/m2/

**References**:**optimally picking one element from each list***From:*Daniel Reeves <dreeves@umich.edu>

**Re: optimally picking one element from each list***From:*Andrzej Kozlowski <akoz@mimuw.edu.pl>

**Re: Re: optimally picking one element from each list***From:*DrBob <drbob@bigfoot.com>

**Re: Re: Re: optimally picking one element from each list***From:*DrBob <drbob@bigfoot.com>