Suppose we have a discrete function $f(x,y,z),g_1(x,y),g_2(y,z)$ in which $x,y,z\in \{1,...N\}$. I want to find several $\{(x_1,y_1,z_1),...,(x_K,y_K,z_K)\}$ triples such that $g_1(x_i,y_i)$ ranks in top-$M_1$ of $g_1$, $g_2(y_i,z_i)$ ranks in top-$M_2$ of $g_2$ and $f(x_i,y_i,z_i)$ ranks top-$M$ in all combinations of $(x_j,y_j,z_j)$ that fulfill the constrain of $g_1$ and $g_2$.

I have two questions:

  1. Is there any optimization models to describe such or similar problem?
  2. How can I solve this more efficiently in numerical without too much computation?

You can solve this with an integer program, but I think (not sure) it would require enumerating all $N^3$ tuples of values $(x,y,z)$ and then introducing binary variables for each pair of tuples, which gets you $O(N^6)$ binary variables. I suspect the most efficient solution might be to generate the tuples ($O(N^3)$ time), sort the values of $f$, $g_1$ and $g_2$ ($O(N^3\log{N})$ each), find the set of tuples satisfying each cutoff ($O(N^3)$) and intersect those sets to get the tuples satisfying all three cutoffs ($O(N^3)$). All told, this is an $O(N^3\log{N})$ approach.


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.