Maximize $(h_1i_1+h_2i_2…h_ni_n)*(p_1i_1+p_2i_2…p_ni_n)$ subject to $c_1i_1+c_2i_2…c_ni_n le B $
$begingroup$
As in the title, the problem is as follows:
Given a set ({$h_1, h_2...h_n$},{$p_1, p_2...p_n$},{$c_1, c_2...c_n$}, {$B$})
where: $ n ≤ 30000 $,
$1≤c_k≤10000$,
$0≤h_k≤1$,
$0≤p_k≤1$,
$1≤B≤100000$.
begin{array}{ll}
text{maximize} & (h_1i_1+h_2i_2...h_ni_n)*(p_1i_1+p_2i_2...p_ni_n)\
text{subject to}& c_1i_1+c_2i_2...c_ni_n le B \
end{array}
I saw it in an ICPC practice set, and I been trying to figure what algorithm/method I need to solve it. It seems to be related to linear programming or convex optimization. I want learn more about the subject, so what I'm looking for the most the most its if someone can identify what type of problem this is and point me to some tutorial or lecture.
Note that input is very large. So the algorithm has to be $O(n)$ or $O(nlog(n))$ and that $i_k$ is a real number and $B, c_k$ are integers.
optimization computer-science
asked Dec 22 '18 at 3:29
YumarioYumario
63
$endgroup$
add a comment |
$begingroup$
As in the title, the problem is as follows:
Given a set ({$h_1, h_2...h_n$},{$p_1, p_2...p_n$},{$c_1, c_2...c_n$}, {$B$})
where: $ n ≤ 30000 $,
$1≤c_k≤10000$,
$0≤h_k≤1$,
$0≤p_k≤1$,
$1≤B≤100000$.
begin{array}{ll}
text{maximize} & (h_1i_1+h_2i_2...h_ni_n)*(p_1i_1+p_2i_2...p_ni_n)\
text{subject to}& c_1i_1+c_2i_2...c_ni_n le B \
end{array}
I saw it in an ICPC practice set, and I been trying to figure what algorithm/method I need to solve it. It seems to be related to linear programming or convex optimization. I want learn more about the subject, so what I'm looking for the most the most its if someone can identify what type of problem this is and point me to some tutorial or lecture.
Note that input is very large. So the algorithm has to be $O(n)$ or $O(nlog(n))$ and that $i_k$ is a real number and $B, c_k$ are integers.
optimization computer-science
asked Dec 22 '18 at 3:29
YumarioYumario
63
$endgroup$
$begingroup$
did you appreciate my answer?
$endgroup$
– LinAlg
Dec 27 '18 at 23:46
$begingroup$
@LinAlg appreciate your effort on the answer, thank you. But honestly I can hardly understand the document, the math is too advanced (I'm computer science). I'll take a look at it again once I finish my math minor in 1-2 years, otherwise I'll ask one of my professor once the semester starts, or maybe you know some other resource.
$endgroup$
– Yumario
Dec 29 '18 at 3:24
$begingroup$
@LinAlg Note that this was not an easy problem problem it was problem 'J' 'Mobilization' here and only two teams manage to solve it.
$endgroup$
– Yumario
Dec 29 '18 at 3:37
$begingroup$
I have updated my answer to conform it to your background.
$endgroup$
– LinAlg
Dec 29 '18 at 13:44
add a comment |
$begingroup$
As in the title, the problem is as follows:
Given a set ({$h_1, h_2...h_n$},{$p_1, p_2...p_n$},{$c_1, c_2...c_n$}, {$B$})
where: $ n ≤ 30000 $,
$1≤c_k≤10000$,
$0≤h_k≤1$,
$0≤p_k≤1$,
$1≤B≤100000$.
begin{array}{ll}
text{maximize} & (h_1i_1+h_2i_2...h_ni_n)*(p_1i_1+p_2i_2...p_ni_n)\
text{subject to}& c_1i_1+c_2i_2...c_ni_n le B \
end{array}
I saw it in an ICPC practice set, and I been trying to figure what algorithm/method I need to solve it. It seems to be related to linear programming or convex optimization. I want learn more about the subject, so what I'm looking for the most the most its if someone can identify what type of problem this is and point me to some tutorial or lecture.
Note that input is very large. So the algorithm has to be $O(n)$ or $O(nlog(n))$ and that $i_k$ is a real number and $B, c_k$ are integers.
optimization computer-science
asked Dec 22 '18 at 3:29
YumarioYumario
63
$endgroup$
As in the title, the problem is as follows:
Given a set ({$h_1, h_2...h_n$},{$p_1, p_2...p_n$},{$c_1, c_2...c_n$}, {$B$})
where: $ n ≤ 30000 $,
$1≤c_k≤10000$,
$0≤h_k≤1$,
$0≤p_k≤1$,
$1≤B≤100000$.
begin{array}{ll}
text{maximize} & (h_1i_1+h_2i_2...h_ni_n)*(p_1i_1+p_2i_2...p_ni_n)\
text{subject to}& c_1i_1+c_2i_2...c_ni_n le B \
end{array}
I saw it in an ICPC practice set, and I been trying to figure what algorithm/method I need to solve it. It seems to be related to linear programming or convex optimization. I want learn more about the subject, so what I'm looking for the most the most its if someone can identify what type of problem this is and point me to some tutorial or lecture.
Note that input is very large. So the algorithm has to be $O(n)$ or $O(nlog(n))$ and that $i_k$ is a real number and $B, c_k$ are integers.
optimization computer-science
optimization computer-science
asked Dec 22 '18 at 3:29
YumarioYumario
63
asked Dec 22 '18 at 3:29
YumarioYumario
63
edited Dec 22 '18 at 3:39
Yumario
asked Dec 22 '18 at 3:29
YumarioYumario
63
asked Dec 22 '18 at 3:29
YumarioYumario
63
asked Dec 22 '18 at 3:29
YumarioYumario
63
63
$begingroup$
did you appreciate my answer?
$endgroup$
– LinAlg
Dec 27 '18 at 23:46
$begingroup$
@LinAlg appreciate your effort on the answer, thank you. But honestly I can hardly understand the document, the math is too advanced (I'm computer science). I'll take a look at it again once I finish my math minor in 1-2 years, otherwise I'll ask one of my professor once the semester starts, or maybe you know some other resource.
$endgroup$
– Yumario
Dec 29 '18 at 3:24
$begingroup$
@LinAlg Note that this was not an easy problem problem it was problem 'J' 'Mobilization' here and only two teams manage to solve it.
$endgroup$
– Yumario
Dec 29 '18 at 3:37
$begingroup$
I have updated my answer to conform it to your background.
$endgroup$
– LinAlg
Dec 29 '18 at 13:44
add a comment |
$begingroup$
did you appreciate my answer?
$endgroup$
– LinAlg
Dec 27 '18 at 23:46
$begingroup$
@LinAlg appreciate your effort on the answer, thank you. But honestly I can hardly understand the document, the math is too advanced (I'm computer science). I'll take a look at it again once I finish my math minor in 1-2 years, otherwise I'll ask one of my professor once the semester starts, or maybe you know some other resource.
$endgroup$
– Yumario
Dec 29 '18 at 3:24
$begingroup$
@LinAlg Note that this was not an easy problem problem it was problem 'J' 'Mobilization' here and only two teams manage to solve it.
$endgroup$
– Yumario
Dec 29 '18 at 3:37
$begingroup$
I have updated my answer to conform it to your background.
$endgroup$
– LinAlg
Dec 29 '18 at 13:44
$begingroup$
did you appreciate my answer?
$endgroup$
– LinAlg
Dec 27 '18 at 23:46
$begingroup$
did you appreciate my answer?
$endgroup$
– LinAlg
Dec 27 '18 at 23:46
$begingroup$
@LinAlg appreciate your effort on the answer, thank you. But honestly I can hardly understand the document, the math is too advanced (I'm computer science). I'll take a look at it again once I finish my math minor in 1-2 years, otherwise I'll ask one of my professor once the semester starts, or maybe you know some other resource.
$endgroup$
– Yumario
Dec 29 '18 at 3:24
$begingroup$
@LinAlg appreciate your effort on the answer, thank you. But honestly I can hardly understand the document, the math is too advanced (I'm computer science). I'll take a look at it again once I finish my math minor in 1-2 years, otherwise I'll ask one of my professor once the semester starts, or maybe you know some other resource.
$endgroup$
– Yumario
Dec 29 '18 at 3:24
$begingroup$
@LinAlg Note that this was not an easy problem problem it was problem 'J' 'Mobilization' here and only two teams manage to solve it.
$endgroup$
– Yumario
Dec 29 '18 at 3:37
$begingroup$
@LinAlg Note that this was not an easy problem problem it was problem 'J' 'Mobilization' here and only two teams manage to solve it.
$endgroup$
– Yumario
Dec 29 '18 at 3:37
$begingroup$
I have updated my answer to conform it to your background.
$endgroup$
– LinAlg
Dec 29 '18 at 13:44
$begingroup$
I have updated my answer to conform it to your background.
$endgroup$
– LinAlg
Dec 29 '18 at 13:44
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The problem can be summarized as $max{ x^TQx : a^Tx leq b}$, where $Q$ is not necessarily negative semidefinite. An optimization problem with a quadratic objective and just one linear constraint is easy, since it satisfies strong duality. That can be proven via the S-lemma.
For more information, see these lecture notes or Appendix B.1 of the (free) book Convex Optimization by Boyd and Vandenberghe.
upd As a computer scientist you may be interested in multi-objective swarm optimization (or variants thereof). Your objectives are maximizing $h_1i_1+h_2i_2...h_ni_n$ and $p_1i_1+p_2i_2...p_ni_n$. Among the Pareto optimal solutions, you multiply both quantities and select the solution with the highest outcome.
answered Dec 22 '18 at 13:41
LinAlgLinAlg
10.1k1521
$endgroup$
add a comment |
Your Answer
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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%2f3049092%2fmaximize-h-1i-1h-2i-2-h-ni-np-1i-1p-2i-2-p-ni-n-subject-to-c-1i-1%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The problem can be summarized as $max{ x^TQx : a^Tx leq b}$, where $Q$ is not necessarily negative semidefinite. An optimization problem with a quadratic objective and just one linear constraint is easy, since it satisfies strong duality. That can be proven via the S-lemma.
For more information, see these lecture notes or Appendix B.1 of the (free) book Convex Optimization by Boyd and Vandenberghe.
upd As a computer scientist you may be interested in multi-objective swarm optimization (or variants thereof). Your objectives are maximizing $h_1i_1+h_2i_2...h_ni_n$ and $p_1i_1+p_2i_2...p_ni_n$. Among the Pareto optimal solutions, you multiply both quantities and select the solution with the highest outcome.
answered Dec 22 '18 at 13:41
LinAlgLinAlg
10.1k1521
$endgroup$
add a comment |
$begingroup$
The problem can be summarized as $max{ x^TQx : a^Tx leq b}$, where $Q$ is not necessarily negative semidefinite. An optimization problem with a quadratic objective and just one linear constraint is easy, since it satisfies strong duality. That can be proven via the S-lemma.
For more information, see these lecture notes or Appendix B.1 of the (free) book Convex Optimization by Boyd and Vandenberghe.
upd As a computer scientist you may be interested in multi-objective swarm optimization (or variants thereof). Your objectives are maximizing $h_1i_1+h_2i_2...h_ni_n$ and $p_1i_1+p_2i_2...p_ni_n$. Among the Pareto optimal solutions, you multiply both quantities and select the solution with the highest outcome.
answered Dec 22 '18 at 13:41
LinAlgLinAlg
10.1k1521
$endgroup$
add a comment |
$begingroup$
The problem can be summarized as $max{ x^TQx : a^Tx leq b}$, where $Q$ is not necessarily negative semidefinite. An optimization problem with a quadratic objective and just one linear constraint is easy, since it satisfies strong duality. That can be proven via the S-lemma.
For more information, see these lecture notes or Appendix B.1 of the (free) book Convex Optimization by Boyd and Vandenberghe.
upd As a computer scientist you may be interested in multi-objective swarm optimization (or variants thereof). Your objectives are maximizing $h_1i_1+h_2i_2...h_ni_n$ and $p_1i_1+p_2i_2...p_ni_n$. Among the Pareto optimal solutions, you multiply both quantities and select the solution with the highest outcome.
answered Dec 22 '18 at 13:41
LinAlgLinAlg
10.1k1521
$endgroup$
The problem can be summarized as $max{ x^TQx : a^Tx leq b}$, where $Q$ is not necessarily negative semidefinite. An optimization problem with a quadratic objective and just one linear constraint is easy, since it satisfies strong duality. That can be proven via the S-lemma.
For more information, see these lecture notes or Appendix B.1 of the (free) book Convex Optimization by Boyd and Vandenberghe.
upd As a computer scientist you may be interested in multi-objective swarm optimization (or variants thereof). Your objectives are maximizing $h_1i_1+h_2i_2...h_ni_n$ and $p_1i_1+p_2i_2...p_ni_n$. Among the Pareto optimal solutions, you multiply both quantities and select the solution with the highest outcome.
answered Dec 22 '18 at 13:41
LinAlgLinAlg
10.1k1521
edited Dec 29 '18 at 13:43
answered Dec 22 '18 at 13:41
LinAlgLinAlg
10.1k1521
answered Dec 22 '18 at 13:41
LinAlgLinAlg
10.1k1521
answered Dec 22 '18 at 13:41
LinAlgLinAlg
10.1k1521
10.1k1521
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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%2f3049092%2fmaximize-h-1i-1h-2i-2-h-ni-np-1i-1p-2i-2-p-ni-n-subject-to-c-1i-1%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
$begingroup$
did you appreciate my answer?
$endgroup$
– LinAlg
Dec 27 '18 at 23:46
$begingroup$
@LinAlg appreciate your effort on the answer, thank you. But honestly I can hardly understand the document, the math is too advanced (I'm computer science). I'll take a look at it again once I finish my math minor in 1-2 years, otherwise I'll ask one of my professor once the semester starts, or maybe you know some other resource.
$endgroup$
– Yumario
Dec 29 '18 at 3:24
$begingroup$
@LinAlg Note that this was not an easy problem problem it was problem 'J' 'Mobilization' here and only two teams manage to solve it.
$endgroup$
– Yumario
Dec 29 '18 at 3:37
$begingroup$
I have updated my answer to conform it to your background.
$endgroup$
– LinAlg
Dec 29 '18 at 13:44