Mixing
Is it possible to turn this into a (standard) integer convex knapsack problem?
up vote
0
down vote
favorite
I have found a solution algorithm for integer knapsack problems of the following form:
$maxlimits_{x_j in [l_j,u_j]} sum_{j=1}^n f_j(x_j)$
such that $sum_{j=1}^n g_j(x_j) leq b$
Where $l_j<u_j$ and $f_j$ are concave and $g_j$ are convex on $[l_j,u_j]$, and both $f_j$ and $g_j$ are monotonically increasing on $[l_j,u_j]$.
I have a problem of the following form and im trying to write it in the above form but im not sure its possible:
$minlimits_{x_j in [l_j,u_j]} sum_{j=1}^n x_j c_j$
such that $sum_{j=1}^n frac{1}{x_j^{p-1}}d_j leq b$
Where $pin (1,2]$ and $c_j, d_j$ are known positive constants.
I could turn the $min x_jc_j$ into a $max f_j$ by defining $f_j(x_j) = -c_jx_j$ and it would be concave but the problem is the monotonicity. I cant introduce a subsitution $y_j=-x_j$ because thats not defined for the $g_j$. Is there maybe another approach?
convex-optimization nonlinear-optimization discrete-optimization
edited yesterday
LinAlg
7,5491520
asked yesterday
StefanWK
727
|
show 3 more comments
up vote
0
down vote
favorite
I have found a solution algorithm for integer knapsack problems of the following form:
$maxlimits_{x_j in [l_j,u_j]} sum_{j=1}^n f_j(x_j)$
such that $sum_{j=1}^n g_j(x_j) leq b$
Where $l_j<u_j$ and $f_j$ are concave and $g_j$ are convex on $[l_j,u_j]$, and both $f_j$ and $g_j$ are monotonically increasing on $[l_j,u_j]$.
I have a problem of the following form and im trying to write it in the above form but im not sure its possible:
$minlimits_{x_j in [l_j,u_j]} sum_{j=1}^n x_j c_j$
such that $sum_{j=1}^n frac{1}{x_j^{p-1}}d_j leq b$
Where $pin (1,2]$ and $c_j, d_j$ are known positive constants.
I could turn the $min x_jc_j$ into a $max f_j$ by defining $f_j(x_j) = -c_jx_j$ and it would be concave but the problem is the monotonicity. I cant introduce a subsitution $y_j=-x_j$ because thats not defined for the $g_j$. Is there maybe another approach?
convex-optimization nonlinear-optimization discrete-optimization
edited yesterday
LinAlg
7,5491520
asked yesterday
StefanWK
727
I do not see why the substitution causes a problem for $g$.
– LinAlg
yesterday
it seems like i made some errors posing the question I corrected them, sorry. The $x_i$ have to be integer and $g_j$ are decreasing if $x_j$ is increasing, that should be the other way around in the "standard" form
– StefanWK
yesterday
did I rephrase the problem correctly?
– LinAlg
yesterday
1
After the substitution $y_j = -x_j$, $g(x) = d_j / (-y_j)^{p-1}$ satisfies the conditions, right? Assuming $l_j >0$.
– LinAlg
yesterday
1
yes, that is correct
– LinAlg
23 hours ago
|
show 3 more comments
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I have found a solution algorithm for integer knapsack problems of the following form:
$maxlimits_{x_j in [l_j,u_j]} sum_{j=1}^n f_j(x_j)$
such that $sum_{j=1}^n g_j(x_j) leq b$
Where $l_j<u_j$ and $f_j$ are concave and $g_j$ are convex on $[l_j,u_j]$, and both $f_j$ and $g_j$ are monotonically increasing on $[l_j,u_j]$.
I have a problem of the following form and im trying to write it in the above form but im not sure its possible:
$minlimits_{x_j in [l_j,u_j]} sum_{j=1}^n x_j c_j$
such that $sum_{j=1}^n frac{1}{x_j^{p-1}}d_j leq b$
Where $pin (1,2]$ and $c_j, d_j$ are known positive constants.
I could turn the $min x_jc_j$ into a $max f_j$ by defining $f_j(x_j) = -c_jx_j$ and it would be concave but the problem is the monotonicity. I cant introduce a subsitution $y_j=-x_j$ because thats not defined for the $g_j$. Is there maybe another approach?
convex-optimization nonlinear-optimization discrete-optimization
edited yesterday
LinAlg
7,5491520
asked yesterday
StefanWK
727
I have found a solution algorithm for integer knapsack problems of the following form:
$maxlimits_{x_j in [l_j,u_j]} sum_{j=1}^n f_j(x_j)$
such that $sum_{j=1}^n g_j(x_j) leq b$
Where $l_j<u_j$ and $f_j$ are concave and $g_j$ are convex on $[l_j,u_j]$, and both $f_j$ and $g_j$ are monotonically increasing on $[l_j,u_j]$.
I have a problem of the following form and im trying to write it in the above form but im not sure its possible:
$minlimits_{x_j in [l_j,u_j]} sum_{j=1}^n x_j c_j$
such that $sum_{j=1}^n frac{1}{x_j^{p-1}}d_j leq b$
Where $pin (1,2]$ and $c_j, d_j$ are known positive constants.
I could turn the $min x_jc_j$ into a $max f_j$ by defining $f_j(x_j) = -c_jx_j$ and it would be concave but the problem is the monotonicity. I cant introduce a subsitution $y_j=-x_j$ because thats not defined for the $g_j$. Is there maybe another approach?
convex-optimization nonlinear-optimization discrete-optimization
convex-optimization nonlinear-optimization discrete-optimization
edited yesterday
LinAlg
7,5491520
asked yesterday
StefanWK
727
edited yesterday
LinAlg
7,5491520
asked yesterday
StefanWK
727
edited yesterday
LinAlg
7,5491520
edited yesterday
LinAlg
7,5491520
edited yesterday
LinAlg
7,5491520
7,5491520
asked yesterday
StefanWK
727
asked yesterday
StefanWK
727
asked yesterday
StefanWK
727
727
I do not see why the substitution causes a problem for $g$.
– LinAlg
yesterday
it seems like i made some errors posing the question I corrected them, sorry. The $x_i$ have to be integer and $g_j$ are decreasing if $x_j$ is increasing, that should be the other way around in the "standard" form
– StefanWK
yesterday
did I rephrase the problem correctly?
– LinAlg
yesterday
1
After the substitution $y_j = -x_j$, $g(x) = d_j / (-y_j)^{p-1}$ satisfies the conditions, right? Assuming $l_j >0$.
– LinAlg
yesterday
1
yes, that is correct
– LinAlg
23 hours ago
|
show 3 more comments
I do not see why the substitution causes a problem for $g$.
– LinAlg
yesterday
it seems like i made some errors posing the question I corrected them, sorry. The $x_i$ have to be integer and $g_j$ are decreasing if $x_j$ is increasing, that should be the other way around in the "standard" form
– StefanWK
yesterday
did I rephrase the problem correctly?
– LinAlg
yesterday
1
After the substitution $y_j = -x_j$, $g(x) = d_j / (-y_j)^{p-1}$ satisfies the conditions, right? Assuming $l_j >0$.
– LinAlg
yesterday
1
yes, that is correct
– LinAlg
23 hours ago
I do not see why the substitution causes a problem for $g$.
– LinAlg
yesterday
I do not see why the substitution causes a problem for $g$.
– LinAlg
yesterday
it seems like i made some errors posing the question I corrected them, sorry. The $x_i$ have to be integer and $g_j$ are decreasing if $x_j$ is increasing, that should be the other way around in the "standard" form
– StefanWK
yesterday
it seems like i made some errors posing the question I corrected them, sorry. The $x_i$ have to be integer and $g_j$ are decreasing if $x_j$ is increasing, that should be the other way around in the "standard" form
– StefanWK
yesterday
did I rephrase the problem correctly?
– LinAlg
yesterday
did I rephrase the problem correctly?
– LinAlg
yesterday
1
1
After the substitution $y_j = -x_j$, $g(x) = d_j / (-y_j)^{p-1}$ satisfies the conditions, right? Assuming $l_j >0$.
– LinAlg
yesterday
After the substitution $y_j = -x_j$, $g(x) = d_j / (-y_j)^{p-1}$ satisfies the conditions, right? Assuming $l_j >0$.
– LinAlg
yesterday
1
1
yes, that is correct
– LinAlg
23 hours ago
yes, that is correct
– LinAlg
23 hours ago
|
show 3 more comments
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3004893%2fis-it-possible-to-turn-this-into-a-standard-integer-convex-knapsack-problem%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
I do not see why the substitution causes a problem for $g$.
– LinAlg
yesterday
it seems like i made some errors posing the question I corrected them, sorry. The $x_i$ have to be integer and $g_j$ are decreasing if $x_j$ is increasing, that should be the other way around in the "standard" form
– StefanWK
yesterday
did I rephrase the problem correctly?
– LinAlg
yesterday
1
After the substitution $y_j = -x_j$, $g(x) = d_j / (-y_j)^{p-1}$ satisfies the conditions, right? Assuming $l_j >0$.
– LinAlg
yesterday
1
yes, that is correct
– LinAlg
23 hours ago