Path: news.mathworks.com!newsfeed-00.mathworks.com!newsfeed2.dallas1.level3.net!news.level3.com!postnews.google.com!d55g2000hsg.googlegroups.com!not-for-mail
From:  Randy Poe <poespam-trap@yahoo.com>
Newsgroups: comp.soft-sys.matlab
Subject: Re: Logical Rules
Date: Thu, 13 Sep 2007 13:03:30 -0700
Organization: http://groups.google.com
Lines: 64
Message-ID: <1189713810.808697.309070@d55g2000hsg.googlegroups.com>
References: <fcbpn6$eo0$1@fred.mathworks.com>
NNTP-Posting-Host: 192.35.37.20
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
X-Trace: posting.google.com 1189713813 25785 127.0.0.1 (13 Sep 2007 20:03:33 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: Thu, 13 Sep 2007 20:03:33 +0000 (UTC)
In-Reply-To: <1189709820.546157.183460@57g2000hsv.googlegroups.com>
User-Agent: G2/1.0
X-HTTP-UserAgent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.8.1.4) Gecko/20070515 Firefox/2.0.0.4,gzip(gfe),gzip(gfe)
X-HTTP-Via: 1.1 squid.atl.lmco.com:3128 (squid/2.5.STABLE14)
Complaints-To: groups-abuse@google.com
Injection-Info: d55g2000hsg.googlegroups.com; posting-host=192.35.37.20;
Xref: news.mathworks.com comp.soft-sys.matlab:428441



On Sep 13, 2:57 pm, "J.N." <joao.nat...@gmail.com> wrote:
> On Sep 13, 12:49 pm, "Christopher Mouton" <mouton.no.s...@caltech.edu>
> wrote:
>
>
>
> > I am trying to see if Matlab has a toolbox for something
> > like this, or where I might look for ideas on how to
> > efficiently solve the following
>
> > A{1}=[1,2]
> > A{2}=[2,3]
> > A{3}=[1,3]
> > A{4}=[1,2,3,4]
>
> > This reads:
>
> > Position 1 can be 1 or 2
> > Position 2 can be 2 or 3
> > Position 3 can be 1 or 3
> > Position 4 can be 1, 2, 3 or 4
>
> > Given that each number can only be used once, we know that
> > Position 4 must be 4.
>
> > So my question is, how could I perform such logic in a
> > general way? Any ideas where I should look?
>
> > Thanks so much.
>
> This is called an Assignment Problem:http://en.wikipedia.org/wiki/Assignment_problem
>

Hmm. There are some problems on that page, mainly the
misuse of the term "Linear Program" which normally refers
to problems in which the variables can be any (positive)
real, not restricted to integers.

> You are essentially trying to assign a set of entities {1,2,...,n} to
> a set of slots {A1,A2,...,An}, with constraints that state that a slot
> Ai is able to accept only a subset of the entities.
>
> One way to model this is to create a n x n logical variable L (with
> slots as rows and entities as columns) such that L(i,j) = true iff
> entity j can be assigned to slot Ai.

Yes, the Wiki page describes the setup as an LP with these
n^2 variables. At n=256, that's not an unwieldy problem, but
you can see that it doesn't take much for such a problem to
get too large to fit in memory.

If you relax the requirement that the L(i,j) be integers, then
you do actually have a standard linear program and you can
use fast LP solving algorithms to solve it (this is called an
"LP relaxation"). The Optimization Toolbox includes one called
LINPROG.

Then you have to decide what to do with fractional values,
but usually some rounding scheme works and often
gives you a pretty good solution, though only in
special cases is that solution guaranteed optimal.

                  - Randy