Services & ResourcesWolfram ForumsMathGroup Archive

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

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>