Best way to maximize over a discrete space?

*To*: mathgroup at smc.vnet.net*Subject*: [mg57164] Best way to maximize over a discrete space?*From*: "bhorling" <bhorling at yahoo.com>*Date*: Thu, 19 May 2005 03:09:04 -0400 (EDT)*Sender*: owner-wri-mathgroup at wolfram.com

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.

**Follow-Ups**:**Re: Best way to maximize over a discrete space?***From:*Chris Chiasson <chris.chiasson@gmail.com>