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:
- Is there any optimization models to describe such or similar problem?
- 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.