6
$\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$
1
  • $\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, 2013 at 7:44

3 Answers 3

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$
0
$\begingroup$

Simulated annealing is an excellent method for problems where we can't make use of the mathematical structure of either the objective function or the constraints and where we are generally happy with a good enough solution. The basic algorithm is:

  1. from an initially random solution, find a nearby solution at random.
  2. if the new solution is better than accept it, otherwise accept it with a probility that decreases over time
  3. repeat

I've put together a JavaScript implementation for this program at my JS Fiddle. Using some random data it takes about 5 seconds to find the optimal solution to this problem.

$\endgroup$
2
  • 1
    $\begingroup$ How do you know the solution is optimal? $\endgroup$
    – Tassle
    Oct 21, 2020 at 10:04
  • $\begingroup$ In general you don't, but this problem is small enough that I ran the optimization a few hundred times so I'm fairly confident with the result :) $\endgroup$
    – Harry Ray
    Oct 22, 2020 at 14:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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