Re: Best way to maximize over a discrete space?
- To: mathgroup at smc.vnet.net
- Subject: [mg57194] Re: [mg57164] Best way to maximize over a discrete space?
- From: Chris Chiasson <chris.chiasson at gmail.com>
- Date: Fri, 20 May 2005 04:43:34 -0400 (EDT)
- References: <200505190709.DAA13158@smc.vnet.net>
- Reply-to: Chris Chiasson <chris.chiasson at gmail.com>
- Sender: owner-wri-mathgroup at wolfram.com
Reduce[(y==-3||y==0||y==2)&&(x==y||x\[Equal]y^Rationalize@2)&&y>=0,x]
By inspection, the requested result is x=4 for y=2. If you have a
larger problem, you should use the same command and then look at the
FullForm of the output, this will give you the clues you need to
extract the maximum result.
On 5/19/05, bhorling <bhorling at yahoo.com> wrote:
> I have question about how to best use Mathematica's optimization
> feature. In a given problem, I have a particular variable I am trying
> to maximize, a set of variables that must be assigned values, a set of
> equations that relate these and other variables, and a set of
> constraints that place bounds on them. I have been using Mathematica's
> Maxmize[] function to solve this, but on harder problems it is taking
> quite a bit of time to complete. For example, Mathematica took three
> hours on a recent test, while a Java-based exhaustive search of the
> variable assignment space took just 50 seconds.
>
> The issue at hand is that the domain for each variable is discrete,
> which is what lets me perform a complete search in my alternate
> solution. I have not found a way to effectively relate this to the
> Maximize function, and I think that might be a source of significant
> delay. I am quite new at using Mathematica, so if anyone has any
> suggestion on how this could be more effectively encoded, I'd love to
> hear it.
>
> For example, here's a simple problem:
>
> x in <y, y^2>
> y in <-3, 0, 2>
> utility = x
> y >= 0
>
> Where utility is the characteristic to be maxmized, x and y are
> variables with associated domains, and there is a single constraint. I
> have an automated process that converts this to something Mathematica
> can interpret. It fills two lists with the variables and constraints
> and then passes those to the Maximize function along with the symbol to
> be maxmized. Is is the domains of the variables that I feel are not
> being effectively used. I currently model them as disjunctions over
> the complete domain. Here is the output of the conversion:
>
> Clear["Global`*"]
> variables = {}
> constraints = {}
>
> AppendTo[variables, x]
> AppendTo[constraints, (x == y) || (x == (y^Rationalize[2.0]))]
> AppendTo[variables, y]
> AppendTo[constraints, (y == (-Rationalize[3.0]) || y ==
> (Rationalize[0.0]) || y == (Rationalize[2.0]))]
> utility = (x)
> AppendTo[constraints, (y >= (Rationalize[0.0]))]
>
> Maximize[utility, constraints, variables]
>
> The Rationalize[] all over the place is there to make the output
> assignments more useful to later processing.
>
> I have experimented with encoding the domains with a function (I forget
> the name right now) that returned true if the indicated value was in a
> corresponding list, but it did not work as I intended (Maxmize seems to
> only work with simple relational constraints). Any suggestions would
> be appreciated, thanks.
>
>
--
Chris Chiasson
http://chrischiasson.com/
1 (810) 265-3161
- References:
- Best way to maximize over a discrete space?
- From: "bhorling" <bhorling@yahoo.com>
- Best way to maximize over a discrete space?