Services & Resources / Wolfram Forums / MathGroup Archive

MathGroup Archive 2004

[Date Index] [Thread Index] [Author Index]

Search the Archive

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

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/
  • Prev by Date: Re: Eigensystem: different solution in V5.0 and V4.1 ??
  • Next by Date: Re: Re: Uniform design
  • Previous by thread: Re: Re: Re: optimally picking one element from each list
  • Next by thread: Re: Re: Re: Re: optimally picking one element from each list