Minimizing a function with discrete variables

Hi,

How can I minimize the sum f(x1,x2) = x1+x2 where both x1 and x2 are discrete and can only assume values from a set of pre-defined values?

Thank you for the help

Answer 1

[Cam Salzberger]

Hello Koel,

If your set of possible values is sufficiently small, and you're only dealing with a few variables, it probably is easiest to just meshgrid or ndgrid the values, compute the function on all possible combinations, and find the global minimum.

If your function takes a long time to compute, there are too many possible values, or you're dealing with too many variables to make that feasible, probably best to look into integer programming. If your set of possible values are just integer values, you're home free with intlinprog.

If not, your function becomes essentially non-linear, as the function will use the integers to index into the set of possible values. You could try out some global optimization algorithms if you have access to that. Or you could check out some File Exchange offerings like this one. I can't speak for the quality or effectiveness of File Exchange submissions though.

-Cam

[Koel Sinha]

Thank you for your response. I have checked the Mixed Integer Linear solvers. The values that these variables can take are not integers, but they are defined such that they can assume only a set of predefined discrete values (as in not a range of values).

The number of variables that I am dealing with is not huge but their possible values increase exponentially.

I would like to understand that if in my given question (f(x1,x2) = x1+x2) if x1 can take values [a1,a2,a3,a4,a5] and x2 can take values [b1,b2,b3,b4,b5] and these values are rational numbers, what could I use to compute the minimum of the sum under the assumption that the number of values that I am dealing with is not small.

Thank you.

[Alan Weiss]

Oh, I thought that you were given a set of [x1,x2] values. If you are given values for x1 and x2 separately, then because your f is monotone in both arguments, you just need to minimize x1 and x2 separately.

solution = min(a) + min(b)

where a and b are the arrays of x1 and x2 values separately.

But this is so simple that I think I am still missing something.

Alan Weiss

MATLAB mathematical toolbox documentation