Mixing
How to formulate this optimization problem mathematically?
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
Suppose we have a discrete function $f(x,y,z),g_1(x,y),g_2(y,z)$ in which $x,y,zin 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?
optimization mathematical-modeling discrete-optimization operations-research
edited Jul 27 at 20:45
Rodrigo de Azevedo
12.6k41751
asked Jul 24 at 8:32
maple
8282922
add a comment |Â
up vote
2
down vote
favorite
Suppose we have a discrete function $f(x,y,z),g_1(x,y),g_2(y,z)$ in which $x,y,zin 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?
optimization mathematical-modeling discrete-optimization operations-research
edited Jul 27 at 20:45
Rodrigo de Azevedo
12.6k41751
asked Jul 24 at 8:32
maple
8282922
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
Suppose we have a discrete function $f(x,y,z),g_1(x,y),g_2(y,z)$ in which $x,y,zin 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?
optimization mathematical-modeling discrete-optimization operations-research
edited Jul 27 at 20:45
Rodrigo de Azevedo
12.6k41751
asked Jul 24 at 8:32
maple
8282922
Suppose we have a discrete function $f(x,y,z),g_1(x,y),g_2(y,z)$ in which $x,y,zin 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?
optimization mathematical-modeling discrete-optimization operations-research
edited Jul 27 at 20:45
Rodrigo de Azevedo
12.6k41751
asked Jul 24 at 8:32
maple
8282922
edited Jul 27 at 20:45
Rodrigo de Azevedo
12.6k41751
edited Jul 27 at 20:45
Rodrigo de Azevedo
12.6k41751
edited Jul 27 at 20:45
Rodrigo de Azevedo
12.6k41751
12.6k41751
asked Jul 24 at 8:32
maple
8282922
asked Jul 24 at 8:32
maple
8282922
asked Jul 24 at 8:32
maple
8282922
8282922
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
0
down vote
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^3logN)$ 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^3logN)$ approach.
answered Jul 27 at 21:28
prubin
1,22125
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
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^3logN)$ 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^3logN)$ approach.
answered Jul 27 at 21:28
prubin
1,22125
add a comment |Â
up vote
0
down vote
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^3logN)$ 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^3logN)$ approach.
answered Jul 27 at 21:28
prubin
1,22125
add a comment |Â
up vote
0
down vote
up vote
0
down vote
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^3logN)$ 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^3logN)$ approach.
answered Jul 27 at 21:28
prubin
1,22125
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^3logN)$ 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^3logN)$ approach.
answered Jul 27 at 21:28
prubin
1,22125
answered Jul 27 at 21:28
prubin
1,22125
answered Jul 27 at 21:28
prubin
1,22125
answered Jul 27 at 21:28
prubin
1,22125
1,22125
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2861113%2fhow-to-formulate-this-optimization-problem-mathematically%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password