0
$\begingroup$

Thanks in advance for the help.

Throughout optimization and heuristic search literature there are several classical problems including, but not limited to, traveling salesman, 8 queens, knapsack, etc. Consider the following optimization problem that I have given below.

Let $X$ be a discrete solution (specifically a set of elements) and $f(X)$ an evaluation function that I would like to optimize. $X$ may have any number of elements as long as $\sum_{x \in X}x = P$ where $P \in N^+$ and $\forall x \in X, x \in N^+$.

I'm interested in using a heuristic to solve this specific problem and would like to read up about how problems of this type have been solved in literature. This problem seems to be relatively simple and therefore I would assume that it can be classified as a specific case of a much more general, classical and well studied problem such as the traveling salesman problem. Is this the case, and if so, what would the problem be? If not, is anyone aware of work that has been done on problems of this type or similar? (It is somewhat similar in someways to the knapsack problem but I'm hoping for something much similar or a classical problem that the problem I have given reduces to).

edit: I should also add that the order of the elements $x$ within the set $X$ impacts the value of $f(X)$. There are no constraints, however, on this ordering. One solution might be 2,1,2,3; another 2,1,3,2; and finally another 4,4

$\endgroup$
  • $\begingroup$ HXSP1947 : Depending on $f(X)$ it could be Integer Programming, Quadratic Programming $\dots$ If $P$ is small then discrete constraints can be expressed as $(x_k - 1)\dots(x_k-P) = 0$ and Lagrange Multipliers used with Grobner Basis. $\endgroup$ – arthur Aug 22 '16 at 5:27
  • $\begingroup$ HXSP1947 : Greedy algorithm followed by k-opt (iteratively swap k elements to improve the cost), Genetic Algorithms $\dots$ $\endgroup$ – arthur Aug 22 '16 at 5:36
  • $\begingroup$ @arthur I'm specifically interested in some kind of heuristic rather than an exact answer ($f(X)$ is just too complicated). Genetic algorithms is definitely something that I've been thinking about and is at the top of the things that I'm considering. However, I was hoping for a paper or two that tackle these kinds of problems so that not only can I have a better insight in selecting the algorithm, but also some insight in how to tune it (ie the mutation function to use, etc) $\endgroup$ – HXSP1947 Aug 22 '16 at 8:34
  • $\begingroup$ HXSP1947 : De Jong's test functions www2.denizyuret.com/pub/aitr1569/node19.html were used as a test set for genetic algorithms and other methods. Performance depends on the terrain i.e. $f(X)$ properties. $\endgroup$ – arthur Aug 22 '16 at 10:05
  • $\begingroup$ HXSP1947 : Global Optimization of MINLP (Mixed Integer Nonlinear Programming) by Evolutionary Algorithms midaco-solver.com/data/pub/MIDACO_APMonitor.pdf $\endgroup$ – arthur Aug 22 '16 at 15:10
0
$\begingroup$

If the properties of the function $f(X)$ is unknown (ie, any relations between its value is unknown), the only way - complete listing of all possible combinations of elements.

If the function increases with any new element adding then some optimization methods became available. In particular, if function increases, moreover for large items - to a greater extent, it becomes possible "greedy" brute force methods, with which to carry on sorting in descending order. That case can be considered as variant of knapsnack problem.

$\endgroup$
0
$\begingroup$

If your problem is very similar to a finding a solution to the knapsack problem, you might try using a backtracking algorithm. They tend to work "pretty fast" (i.e. still exponential, but much faster than a simple brute force search). Backtracking tends to work well when you need to find an exact answer and there is an easy way to determine whether or not a possible solution tree can be abandoned. Backtracking also has the benefit of finding all the possible solutions.

Greedy algorithms only really work for things like the Travelling Salesman problem, where you are trying to minimize or maximize a value, and even then they are only good starting points, as they do not actually find the best solution. A greedy algorithm with a backtracking algorithm would set you up pretty well.

Tabu searches appear to work well when you are trying to get within a range of values, like the knapsack problem adjusted so that instead of adding up to an exact number, you have to add up to any number within a range. Tabu searches also have the problems of not necessarily finding all possible solutions and occasionally getting stuck inside a loop.

I don't know a lot about VNS, but it seems to be generally applicable to a lot of situations.

From what I can gather, I would suggest either using backtracking or VNS.

$\endgroup$

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.