5
$\begingroup$

Consider we have a finite set $S$ with $n$ distinct elements. We want to find a subset $\{a_1, a_2, \dotsc, a_k\}\subseteq S$ ($k\ll n$) such that a function $f(a_1,a_2,\dotsc,a_k)$ is maximized. Consider $f$ to be a symmetric function that takes $k$ arguments.


More specifically, we are given $n = 120$ items, each item being associated with three positive numbers $(A_i, B_i,C_i)$, and we want to choose $k=12$ items within this set such that

$$ \frac{\sum_{k=1}^{12} A_{i_k} \times \left\lceil\frac{\sum_{k=1}^{12} B_{i_k}}{10000}\right\rceil}{\sum_{k=1}^{12} C_{i_k}} $$

is maximal.


If we solve it by exhaustive search it requires $\binom{120}{12} \approx 10^{16}$ operations. Is there faster method to this problem? Approximate solution is also fine.

$\endgroup$
  • $\begingroup$ It seems to me that you want to solve a non-linear program with particularly simple constraints, so literature on that may help. $\endgroup$ – Raphael Aug 7 '13 at 7:44
3
$\begingroup$

Here are some crazy ideas, with absolutely no guarantee that they'll find a good solution -- but ideas you could try.


One possible heuristic approach might be to use quadratic programming combined with randomized rounding and some more heuristics.

In particular, introduce variables $x_i$ (for $i=1,2,120$); the idea is that $x_i=1$ means that $i$ is one of the 12 items you select, and $x_i=0$. Now we have linear constraints $0 \le x_i \le 1$ and $x_1+x_2+\dots+x_{120} = 12$. We could fix some constant $U$, introduce the constraint $\sum_i C_i x_i \le U$, and maximize the quadratic function $(\sum_i A_i x_i) \times (\sum_i B_i x_i)$. Now the values of $x_i$ you get back won't necessarily be 0 or 1 (they'll probably be fractions), but you could use randomized rounding to convert it to a 0/1-solution. Now sweep over a range of possible values of $U$ (increasing each time by a multiplicative factor of, say, 1.1 times the previous value), and keep the best solution you find.

This might work, or it might not, but it's something you could try.


You could also try formulating this as a semidefinite programming problem or quadratic programming with quadratic constraints (with each $x_i$ representing whether you take item $i$ or not), then apply randomized rounding to account for the fact that the $x_i$'s should all be 0 or 1. In particular, if you work on the decision problem (does there exist a solution whether the objective function exceeds $r$?), then you can phrase everything using quadratic constraints -- the requirement that $(\sum_i A_i) (\sum_i B_i)/(\sum_i C_i) \ge r$ is equivalent to $(\sum_i A_i) (\sum_i B_i) - r (\sum_i C_i)$, which is a quadratic function in the $x_i$'s. You might be able to express this as a semidefinite programming problem.


Another heuristic might be to try splitting this into sub-problems and then trying to merge, using a divide-and-conquer style approach.

Randomly partition the 120 items into two sets of 60, namely sets $L,R$ such that $|L|=|R|=60$ and $L\cup R=\{1,2,\dots,120\}$. Enumerate all $60 \choose 6$ ways to choose 6 items from $L$, and compute the value of $(\sum A_i) (\sum B_i)/(\sum C_i)$ for each such subset of 6 items. This gives you a list of ${60 \choose 6} \approx 2^{26}$ different 6-subsets, and a $U$-value for each. Sort that list by decreasing value. Do the same for $R$.

Now try to combine these two lists. For instance, you could throw away all but the top 5% of each of the two lists, then try all ways of pairing up one subset of 6 items from the first list with one subset of 6 items from the second subset; compute the value of your objective function for each such subset of 12 items, and keep track of the best you've seen so far.

Repeat many times with many different ways of partitioning the 120 items into two sets of 60.

Again, I have no clue whether it will work well or not. There's no reason to believe it will necessarily give the best solution.

$\endgroup$
0
$\begingroup$

Could try a genetic algorithm.

  1. Create a population of $N$ random subsets
  2. Calculate $f(A)$ for each subset and rank population.
  3. Keep top 20% of population, create 20% totally random. With remaining population crossover and mutate from top 20% to generate new subsets.
  4. Repeat

This can guarantee you one or more good solutions but not the best solution.

$\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.