0
$\begingroup$

Say I have a very large, arbitrary number of variables, each of which I can assign to be type A, B, or C.

The types come with expenses: Type A's are the least expensive, and C's are the most expensive, but their expense varies from variable to variable.
For example {A, C, C} may actually be more expensive than {C, A, A} if that first variable happens to be worth more, but we won't know how much the total cost is until we assign the types and run the program.

Also we don't want to go below a certain given total expense (can't make all A's), but get as close as possible to it.

I am trying to minimize the total expense while staying above the threshold. The search space (permutations of variable types) is too large to try all combinations.

Someone recommended sampling via Monte Carlo method earlier.
How can the Monte Carlo method, or Markov-Chain Monte Carlo, be applied to such a problem to find the optimal combination of parameters?
Could a genetic algorithm be used effectively?

Improve this question
$\endgroup$
5
  • $\begingroup$ Simulated annealing does not seem to offer you any good advice at all. You should look at another similar concept Monte Carlo which is applicable. $\endgroup$
    – InformedA
    Sep 15, 2014 at 6:38
  • $\begingroup$ @ginsunuva I edited your question to make it more clear as I understand it. Please verify, that this is indeed what you want to ask. $\endgroup$
    – FrankW
    Sep 17, 2014 at 10:07
  • 2
    $\begingroup$ As long as their is no structure in the relationship between item, type and expense (you don't say anything about that!) there may be no better approach than enumerating all solutions (for an exact solution) or a random search (which may find a "good" solution faster). $\endgroup$
    – Raphael ♦
    Sep 17, 2014 at 10:18
  • $\begingroup$ Does the expense of assigning type A to variable 1 depend on the types assigned to the other variables? $\endgroup$
    – FrankW
    Sep 17, 2014 at 10:22
  • $\begingroup$ It could. These are all variables in a program with different precisions. If one variable interacts with another, it probably would. Adding precision A to precision B would be the same as both being B. But we don't know how each variable interacts with one another (it'd be great if we did.) $\endgroup$
    – ginsunuva
    Sep 17, 2014 at 10:50

1 Answer 1

Reset to default
-1
$\begingroup$

You normally need to know what heuristic function you have.

Usually, when you use simulated annealing, you don't find a maximum score (or combination that gives the maximum score). What you do is trying to get a score that is better than the current score that you have.

Note that, I find it very strange when you say you want to use simulated annealing for discrete optimization problem like the one you mention. When your problem is discreet, how do you do differential? Thus, how do you know which direction you should proceed with gradient ascent/descent?

There are cases in which a seemingly discreet optimization problem is actually a continuous one in which you can use a customized and modified gradient ascent/descent with an optional simulated annealing. I will refrain from comment further in this particular case.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Is there some confusion? There is nothing wrong with using simulated annealing with a discrete search space. It does not involve gradient ascent/descent. See en.wikipedia.org/wiki/Simulated_annealing. $\endgroup$
    – D.W. ♦
    Oct 17, 2014 at 12:48
  • $\begingroup$ @D.W. from what I learned in machine learning and neural network intro, Simulated annealing is used to walk to better state in a continuous surface without being stuck in a local optima. When the space is discrete, it is not called simulated annealing. I know conceptually they are the same, because you can still get a heuristic function or whatever improvisional measure to create a function that gives you an approximated score for each neighboring state. $\endgroup$
    – InformedA
    Oct 17, 2014 at 19:30
  • $\begingroup$ The wiki page you gave is very strange, simulated annealing is about going in opposite direction to the direction suggested by gradient ascend/descend. This means you need to have a before hand guidance (first order derivative is what it is). I can't believe it now means you simply have a guidance function, and you follow it. It has nothing to do with going in opposite direction now. Very strange. $\endgroup$
    – InformedA
    Oct 17, 2014 at 19:44
  • $\begingroup$ The guidance (heuristic/derivative) is not perfect, so annealing means you don't always follow it. You give a probability of going in other direction. This other direction can be another heuristic, path memory, etc.. other than the guidance function. In the simplest case, the other direction is chosen randomly. But anyway, since you have way more reputations than I do, I will refrain from speaking further and let you answer this problem. $\endgroup$
    – InformedA
    Oct 18, 2014 at 3:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.