Mixing
Multiple Choice Knapsack Problem (MCKP) where one class requires more than one item
$begingroup$
I have the following problem of which I am attempting to find a near optimal solution:
I have one knapsack which can hold a maximum weight. I must select exactly one distinct item from a number of classes, except for the last class in which I must select exactly three distinct items.
Each item has both a weight and a profit as an attribute.The goal is to maximize profit while not exceeding the maximum weight of the knapsack. There are a number of papers which suggest algorithms if exactly one item is chosen from each class (MCKP), but I have not found any which speak about a class which requires more than one to be selected.
The immediate solution that comes to mind is to treat the special class as the others by transforming it into a single selection of a combination of three items. For example, if the class which requires three items to be chosen has a total of ten items, the total number of permutations is 720.
This solution would transform the problem back into MCKP, but quickly becomes too resource intensive as the number of items in the special class increase. For example, 100 items in the special class would have 970,200 possible permutations.
So my question is: Is there a better way in which to conceptualize this problem? Has any research addressed this problem specifically?
combinatorics algorithms linear-programming extremal-combinatorics
asked Apr 29 '13 at 3:00
Jester87Jester87
1113
$endgroup$
add a comment |
$begingroup$
I have the following problem of which I am attempting to find a near optimal solution:
I have one knapsack which can hold a maximum weight. I must select exactly one distinct item from a number of classes, except for the last class in which I must select exactly three distinct items.
Each item has both a weight and a profit as an attribute.The goal is to maximize profit while not exceeding the maximum weight of the knapsack. There are a number of papers which suggest algorithms if exactly one item is chosen from each class (MCKP), but I have not found any which speak about a class which requires more than one to be selected.
The immediate solution that comes to mind is to treat the special class as the others by transforming it into a single selection of a combination of three items. For example, if the class which requires three items to be chosen has a total of ten items, the total number of permutations is 720.
This solution would transform the problem back into MCKP, but quickly becomes too resource intensive as the number of items in the special class increase. For example, 100 items in the special class would have 970,200 possible permutations.
So my question is: Is there a better way in which to conceptualize this problem? Has any research addressed this problem specifically?
combinatorics algorithms linear-programming extremal-combinatorics
asked Apr 29 '13 at 3:00
Jester87Jester87
1113
$endgroup$
$begingroup$
So, for example, if you were to "clone" your last class into three identical classes, would your problem reduce to MMKP? I.e., if your classes are $C_1, C_2, dots, C_n$, take $C_n$ and clone it into $C_{n1}, C_{n2}, C_{n3}$. Now solve MMKP on $C_1, dots, C_{n1}, C_{n2}, C_{n3}$.
$endgroup$
– baudolino
Apr 29 '13 at 3:32
$begingroup$
I thought of that, but since the items are distinct they can't be chosen twice. Also, I am under the impression that the clones would disrupt how an algorithm choses an item for each class unless it is picking in a linear fashion.
$endgroup$
– Jester87
Apr 29 '13 at 4:56
$begingroup$
Well, yes, but that should be fixable with a little book-keeping inside the algorithm. It wouldn't matter whether you try something as simple as a greedy selection or more involved, like a dynamic programming approach. I am assuming you don't want to feed this problem into a generic solver, since it's easy to model it as an integer program.
$endgroup$
– baudolino
Apr 29 '13 at 19:02
$begingroup$
Yeah that shouldn't be too hard now that I think about it. Alternatively, I think I could actually add a separate constraint for the special class where the sum of the binary variables is equal to three instead of one.
$endgroup$
– Jester87
Apr 30 '13 at 4:07
add a comment |
$begingroup$
I have the following problem of which I am attempting to find a near optimal solution:
I have one knapsack which can hold a maximum weight. I must select exactly one distinct item from a number of classes, except for the last class in which I must select exactly three distinct items.
Each item has both a weight and a profit as an attribute.The goal is to maximize profit while not exceeding the maximum weight of the knapsack. There are a number of papers which suggest algorithms if exactly one item is chosen from each class (MCKP), but I have not found any which speak about a class which requires more than one to be selected.
The immediate solution that comes to mind is to treat the special class as the others by transforming it into a single selection of a combination of three items. For example, if the class which requires three items to be chosen has a total of ten items, the total number of permutations is 720.
This solution would transform the problem back into MCKP, but quickly becomes too resource intensive as the number of items in the special class increase. For example, 100 items in the special class would have 970,200 possible permutations.
So my question is: Is there a better way in which to conceptualize this problem? Has any research addressed this problem specifically?
combinatorics algorithms linear-programming extremal-combinatorics
asked Apr 29 '13 at 3:00
Jester87Jester87
1113
$endgroup$
I have the following problem of which I am attempting to find a near optimal solution:
I have one knapsack which can hold a maximum weight. I must select exactly one distinct item from a number of classes, except for the last class in which I must select exactly three distinct items.
Each item has both a weight and a profit as an attribute.The goal is to maximize profit while not exceeding the maximum weight of the knapsack. There are a number of papers which suggest algorithms if exactly one item is chosen from each class (MCKP), but I have not found any which speak about a class which requires more than one to be selected.
The immediate solution that comes to mind is to treat the special class as the others by transforming it into a single selection of a combination of three items. For example, if the class which requires three items to be chosen has a total of ten items, the total number of permutations is 720.
This solution would transform the problem back into MCKP, but quickly becomes too resource intensive as the number of items in the special class increase. For example, 100 items in the special class would have 970,200 possible permutations.
So my question is: Is there a better way in which to conceptualize this problem? Has any research addressed this problem specifically?
combinatorics algorithms linear-programming extremal-combinatorics
combinatorics algorithms linear-programming extremal-combinatorics
asked Apr 29 '13 at 3:00
Jester87Jester87
1113
asked Apr 29 '13 at 3:00
Jester87Jester87
1113
edited Apr 29 '13 at 4:57
Jester87
asked Apr 29 '13 at 3:00
Jester87Jester87
1113
asked Apr 29 '13 at 3:00
Jester87Jester87
1113
asked Apr 29 '13 at 3:00
Jester87Jester87
1113
1113
$begingroup$
So, for example, if you were to "clone" your last class into three identical classes, would your problem reduce to MMKP? I.e., if your classes are $C_1, C_2, dots, C_n$, take $C_n$ and clone it into $C_{n1}, C_{n2}, C_{n3}$. Now solve MMKP on $C_1, dots, C_{n1}, C_{n2}, C_{n3}$.
$endgroup$
– baudolino
Apr 29 '13 at 3:32
$begingroup$
I thought of that, but since the items are distinct they can't be chosen twice. Also, I am under the impression that the clones would disrupt how an algorithm choses an item for each class unless it is picking in a linear fashion.
$endgroup$
– Jester87
Apr 29 '13 at 4:56
$begingroup$
Well, yes, but that should be fixable with a little book-keeping inside the algorithm. It wouldn't matter whether you try something as simple as a greedy selection or more involved, like a dynamic programming approach. I am assuming you don't want to feed this problem into a generic solver, since it's easy to model it as an integer program.
$endgroup$
– baudolino
Apr 29 '13 at 19:02
$begingroup$
Yeah that shouldn't be too hard now that I think about it. Alternatively, I think I could actually add a separate constraint for the special class where the sum of the binary variables is equal to three instead of one.
$endgroup$
– Jester87
Apr 30 '13 at 4:07
add a comment |
$begingroup$
So, for example, if you were to "clone" your last class into three identical classes, would your problem reduce to MMKP? I.e., if your classes are $C_1, C_2, dots, C_n$, take $C_n$ and clone it into $C_{n1}, C_{n2}, C_{n3}$. Now solve MMKP on $C_1, dots, C_{n1}, C_{n2}, C_{n3}$.
$endgroup$
– baudolino
Apr 29 '13 at 3:32
$begingroup$
I thought of that, but since the items are distinct they can't be chosen twice. Also, I am under the impression that the clones would disrupt how an algorithm choses an item for each class unless it is picking in a linear fashion.
$endgroup$
– Jester87
Apr 29 '13 at 4:56
$begingroup$
Well, yes, but that should be fixable with a little book-keeping inside the algorithm. It wouldn't matter whether you try something as simple as a greedy selection or more involved, like a dynamic programming approach. I am assuming you don't want to feed this problem into a generic solver, since it's easy to model it as an integer program.
$endgroup$
– baudolino
Apr 29 '13 at 19:02
$begingroup$
Yeah that shouldn't be too hard now that I think about it. Alternatively, I think I could actually add a separate constraint for the special class where the sum of the binary variables is equal to three instead of one.
$endgroup$
– Jester87
Apr 30 '13 at 4:07
$begingroup$
So, for example, if you were to "clone" your last class into three identical classes, would your problem reduce to MMKP? I.e., if your classes are $C_1, C_2, dots, C_n$, take $C_n$ and clone it into $C_{n1}, C_{n2}, C_{n3}$. Now solve MMKP on $C_1, dots, C_{n1}, C_{n2}, C_{n3}$.
$endgroup$
– baudolino
Apr 29 '13 at 3:32
$begingroup$
So, for example, if you were to "clone" your last class into three identical classes, would your problem reduce to MMKP? I.e., if your classes are $C_1, C_2, dots, C_n$, take $C_n$ and clone it into $C_{n1}, C_{n2}, C_{n3}$. Now solve MMKP on $C_1, dots, C_{n1}, C_{n2}, C_{n3}$.
$endgroup$
– baudolino
Apr 29 '13 at 3:32
$begingroup$
I thought of that, but since the items are distinct they can't be chosen twice. Also, I am under the impression that the clones would disrupt how an algorithm choses an item for each class unless it is picking in a linear fashion.
$endgroup$
– Jester87
Apr 29 '13 at 4:56
$begingroup$
I thought of that, but since the items are distinct they can't be chosen twice. Also, I am under the impression that the clones would disrupt how an algorithm choses an item for each class unless it is picking in a linear fashion.
$endgroup$
– Jester87
Apr 29 '13 at 4:56
$begingroup$
Well, yes, but that should be fixable with a little book-keeping inside the algorithm. It wouldn't matter whether you try something as simple as a greedy selection or more involved, like a dynamic programming approach. I am assuming you don't want to feed this problem into a generic solver, since it's easy to model it as an integer program.
$endgroup$
– baudolino
Apr 29 '13 at 19:02
$begingroup$
Well, yes, but that should be fixable with a little book-keeping inside the algorithm. It wouldn't matter whether you try something as simple as a greedy selection or more involved, like a dynamic programming approach. I am assuming you don't want to feed this problem into a generic solver, since it's easy to model it as an integer program.
$endgroup$
– baudolino
Apr 29 '13 at 19:02
$begingroup$
Yeah that shouldn't be too hard now that I think about it. Alternatively, I think I could actually add a separate constraint for the special class where the sum of the binary variables is equal to three instead of one.
$endgroup$
– Jester87
Apr 30 '13 at 4:07
$begingroup$
Yeah that shouldn't be too hard now that I think about it. Alternatively, I think I could actually add a separate constraint for the special class where the sum of the binary variables is equal to three instead of one.
$endgroup$
– Jester87
Apr 30 '13 at 4:07
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
I think this should work:
Maximize: $$sum _{j=1}^{N}sum _{j=1}^{left | G_{i} right |}p_{ij}x_{ij}$$
Subject to: $$
begin{align}
sum _{i=1}^{n}sum _{j=1}^{left | G_{i} right |}w_{ij}x_{ij} &leq c \
sum _{j=1}^{left | G_{i} right |}x_{ij} &= 1 \
sum _{j=1}^{left | G_{s} right |}x_{sj} &= 3 \
x_{ij} in {0,1}
end{align}
$$
Notation:
N the number of items
n the number of groups
c the capacity of a single knapsack
G = {$G_{1},...,G_{n}$} the set of groups
${left | G_{i} right |}$ the number of items in group $G_{i}$
${left | G_{s} right |}$ the number of items in group $G_{s}$ (special group)
$p_{ij}$ the profit of item j of group $G_{i}$
$w_{ij}$ the weight of item j of group $G_{i}$
edited May 1 '13 at 15:30
baudolino
1,540814
answered Apr 30 '13 at 5:01
Jester87Jester87
1113
$endgroup$
$begingroup$
This looks ok. Notice that you can also generalize this such that you can address exactly $k$ items (rather than 3) across the last $m$ classes (rather than the last one).
$endgroup$
– baudolino
May 1 '13 at 15:26
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
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%2f375851%2fmultiple-choice-knapsack-problem-mckp-where-one-class-requires-more-than-one-i%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$
I think this should work:
Maximize: $$sum _{j=1}^{N}sum _{j=1}^{left | G_{i} right |}p_{ij}x_{ij}$$
Subject to: $$
begin{align}
sum _{i=1}^{n}sum _{j=1}^{left | G_{i} right |}w_{ij}x_{ij} &leq c \
sum _{j=1}^{left | G_{i} right |}x_{ij} &= 1 \
sum _{j=1}^{left | G_{s} right |}x_{sj} &= 3 \
x_{ij} in {0,1}
end{align}
$$
Notation:
N the number of items
n the number of groups
c the capacity of a single knapsack
G = {$G_{1},...,G_{n}$} the set of groups
${left | G_{i} right |}$ the number of items in group $G_{i}$
${left | G_{s} right |}$ the number of items in group $G_{s}$ (special group)
$p_{ij}$ the profit of item j of group $G_{i}$
$w_{ij}$ the weight of item j of group $G_{i}$
edited May 1 '13 at 15:30
baudolino
1,540814
answered Apr 30 '13 at 5:01
Jester87Jester87
1113
$endgroup$
$begingroup$
This looks ok. Notice that you can also generalize this such that you can address exactly $k$ items (rather than 3) across the last $m$ classes (rather than the last one).
$endgroup$
– baudolino
May 1 '13 at 15:26
add a comment |
$begingroup$
I think this should work:
Maximize: $$sum _{j=1}^{N}sum _{j=1}^{left | G_{i} right |}p_{ij}x_{ij}$$
Subject to: $$
begin{align}
sum _{i=1}^{n}sum _{j=1}^{left | G_{i} right |}w_{ij}x_{ij} &leq c \
sum _{j=1}^{left | G_{i} right |}x_{ij} &= 1 \
sum _{j=1}^{left | G_{s} right |}x_{sj} &= 3 \
x_{ij} in {0,1}
end{align}
$$
Notation:
N the number of items
n the number of groups
c the capacity of a single knapsack
G = {$G_{1},...,G_{n}$} the set of groups
${left | G_{i} right |}$ the number of items in group $G_{i}$
${left | G_{s} right |}$ the number of items in group $G_{s}$ (special group)
$p_{ij}$ the profit of item j of group $G_{i}$
$w_{ij}$ the weight of item j of group $G_{i}$
edited May 1 '13 at 15:30
baudolino
1,540814
answered Apr 30 '13 at 5:01
Jester87Jester87
1113
$endgroup$
$begingroup$
This looks ok. Notice that you can also generalize this such that you can address exactly $k$ items (rather than 3) across the last $m$ classes (rather than the last one).
$endgroup$
– baudolino
May 1 '13 at 15:26
add a comment |
$begingroup$
I think this should work:
Maximize: $$sum _{j=1}^{N}sum _{j=1}^{left | G_{i} right |}p_{ij}x_{ij}$$
Subject to: $$
begin{align}
sum _{i=1}^{n}sum _{j=1}^{left | G_{i} right |}w_{ij}x_{ij} &leq c \
sum _{j=1}^{left | G_{i} right |}x_{ij} &= 1 \
sum _{j=1}^{left | G_{s} right |}x_{sj} &= 3 \
x_{ij} in {0,1}
end{align}
$$
Notation:
N the number of items
n the number of groups
c the capacity of a single knapsack
G = {$G_{1},...,G_{n}$} the set of groups
${left | G_{i} right |}$ the number of items in group $G_{i}$
${left | G_{s} right |}$ the number of items in group $G_{s}$ (special group)
$p_{ij}$ the profit of item j of group $G_{i}$
$w_{ij}$ the weight of item j of group $G_{i}$
edited May 1 '13 at 15:30
baudolino
1,540814
answered Apr 30 '13 at 5:01
Jester87Jester87
1113
$endgroup$
I think this should work:
Maximize: $$sum _{j=1}^{N}sum _{j=1}^{left | G_{i} right |}p_{ij}x_{ij}$$
Subject to: $$
begin{align}
sum _{i=1}^{n}sum _{j=1}^{left | G_{i} right |}w_{ij}x_{ij} &leq c \
sum _{j=1}^{left | G_{i} right |}x_{ij} &= 1 \
sum _{j=1}^{left | G_{s} right |}x_{sj} &= 3 \
x_{ij} in {0,1}
end{align}
$$
Notation:
N the number of items
n the number of groups
c the capacity of a single knapsack
G = {$G_{1},...,G_{n}$} the set of groups
${left | G_{i} right |}$ the number of items in group $G_{i}$
${left | G_{s} right |}$ the number of items in group $G_{s}$ (special group)
$p_{ij}$ the profit of item j of group $G_{i}$
$w_{ij}$ the weight of item j of group $G_{i}$
edited May 1 '13 at 15:30
baudolino
1,540814
answered Apr 30 '13 at 5:01
Jester87Jester87
1113
edited May 1 '13 at 15:30
baudolino
1,540814
edited May 1 '13 at 15:30
baudolino
1,540814
edited May 1 '13 at 15:30
baudolino
1,540814
1,540814
answered Apr 30 '13 at 5:01
Jester87Jester87
1113
answered Apr 30 '13 at 5:01
Jester87Jester87
1113
answered Apr 30 '13 at 5:01
Jester87Jester87
1113
1113
$begingroup$
This looks ok. Notice that you can also generalize this such that you can address exactly $k$ items (rather than 3) across the last $m$ classes (rather than the last one).
$endgroup$
– baudolino
May 1 '13 at 15:26
add a comment |
$begingroup$
This looks ok. Notice that you can also generalize this such that you can address exactly $k$ items (rather than 3) across the last $m$ classes (rather than the last one).
$endgroup$
– baudolino
May 1 '13 at 15:26
$begingroup$
This looks ok. Notice that you can also generalize this such that you can address exactly $k$ items (rather than 3) across the last $m$ classes (rather than the last one).
$endgroup$
– baudolino
May 1 '13 at 15:26
$begingroup$
This looks ok. Notice that you can also generalize this such that you can address exactly $k$ items (rather than 3) across the last $m$ classes (rather than the last one).
$endgroup$
– baudolino
May 1 '13 at 15:26
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%2f375851%2fmultiple-choice-knapsack-problem-mckp-where-one-class-requires-more-than-one-i%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$
So, for example, if you were to "clone" your last class into three identical classes, would your problem reduce to MMKP? I.e., if your classes are $C_1, C_2, dots, C_n$, take $C_n$ and clone it into $C_{n1}, C_{n2}, C_{n3}$. Now solve MMKP on $C_1, dots, C_{n1}, C_{n2}, C_{n3}$.
$endgroup$
– baudolino
Apr 29 '13 at 3:32
$begingroup$
I thought of that, but since the items are distinct they can't be chosen twice. Also, I am under the impression that the clones would disrupt how an algorithm choses an item for each class unless it is picking in a linear fashion.
$endgroup$
– Jester87
Apr 29 '13 at 4:56
$begingroup$
Well, yes, but that should be fixable with a little book-keeping inside the algorithm. It wouldn't matter whether you try something as simple as a greedy selection or more involved, like a dynamic programming approach. I am assuming you don't want to feed this problem into a generic solver, since it's easy to model it as an integer program.
$endgroup$
– baudolino
Apr 29 '13 at 19:02
$begingroup$
Yeah that shouldn't be too hard now that I think about it. Alternatively, I think I could actually add a separate constraint for the special class where the sum of the binary variables is equal to three instead of one.
$endgroup$
– Jester87
Apr 30 '13 at 4:07