Skip to main content
added 1085 characters in body
Source Link
kglr
  • 400.5k
  • 18
  • 488
  • 929

Add the constraints (1) item 3 and item 4 should be selected and (2)Constraints that specify lower bounds on item 3 and 4 total shouldcounts can be between 2 and 5:handled easily by changing the arguments. For example,

lb = {0, 0, 1, 1, 0}; (* items 3 and 4 should be included in the knapsack*knapsack *) 

lb + KnapsackSolve[Transpose@{V, P, ub - lb}, W - P.lb]

{3, 14, 5, 1, 0}

which is the same as LP solution under the same constraints:

LinearProgramming[-V, {P}, {{W, -1}}, Thread[{lb, ub}], Integers]

{3, 14, 5, 1, 0}

Similarly, to add an additional constraint that requires having exactly 1 unit of item 2 in the solution we make the lower and upper bounds for that item 1:

ub2 = {3, 1, 5, Infinity, Infinity};
lb2 = {0, 1, 1, 1, 0};

lb2 + KnapsackSolve[Transpose@{V, P, ub2 - lb2}, W - P.lb2]

{0, 1, 5, 1, 12}

LinearProgramming[-V, {P}, {{W, -1}}, Thread[{lb2, ub2}], Integers]

{0, 1, 5, 1, 12}

For constraints that involve multiple items (e.g., total count of items 3 and 4 should be between 2 and 5) I am not aware of a general method to get KnapsackSolve to work, but LinearProgramming can handle any linear constraint easily:

For the case with the constraints (1) items 3 and 4 should both be present, and (2) total count of items 3 and 4 should be between 2 and 5, we can use:

LinearProgramming[-V,
 {P, {0, 0, 1, 1, 0}, {0, 0, 1, 1, 0}},
 {{W, -1}, {2, 1}, {5, -1}}, 
 Thread[{lb, ub}],
 Integers]

AddAdding the constraint that exactly one unit of item 2 is in the solution:

ub2ub3 = {3, 1, 5, Infinity, Infinity};
lb2lb3 = {0, 1, 1, 1, 0};
LinearProgramming[-V,
  {P, {0, 0, 1, 1, 0}, {0, 0, 1, 1, 0}},
  {{W, -1}, {2, 1}, {5, -1}}, 
  Thread[{lb2lb3, ub2ub3}], 
  Integers]

Add the constraints (1) item 3 and item 4 should be selected and (2) item 3 and 4 total should be between 2 and 5:

lb = {0, 0, 1, 1, 0}; (* items 3 and 4 should in the knapsack*)

LinearProgramming[-V,
 {P, {0, 0, 1, 1, 0}, {0, 0, 1, 1, 0}},
 {{W, -1}, {2, 1}, {5, -1}}, 
 Thread[{lb, ub}],
 Integers]

Add the constraint that exactly one unit of item 2 is in the solution:

ub2 = {3, 1, 5, Infinity, Infinity};
lb2 = {0, 1, 1, 1, 0};
LinearProgramming[-V,
  {P, {0, 0, 1, 1, 0}, {0, 0, 1, 1, 0}},
  {{W, -1}, {2, 1}, {5, -1}}, 
  Thread[{lb2, ub2}], 
  Integers]

Constraints that specify lower bounds on item counts can be handled easily by changing the arguments. For example,

lb = {0, 0, 1, 1, 0}; (* items 3 and 4 should be included in the knapsack *) 

lb + KnapsackSolve[Transpose@{V, P, ub - lb}, W - P.lb]

{3, 14, 5, 1, 0}

which is the same as LP solution under the same constraints:

LinearProgramming[-V, {P}, {{W, -1}}, Thread[{lb, ub}], Integers]

{3, 14, 5, 1, 0}

Similarly, to add an additional constraint that requires having exactly 1 unit of item 2 in the solution we make the lower and upper bounds for that item 1:

ub2 = {3, 1, 5, Infinity, Infinity};
lb2 = {0, 1, 1, 1, 0};

lb2 + KnapsackSolve[Transpose@{V, P, ub2 - lb2}, W - P.lb2]

{0, 1, 5, 1, 12}

LinearProgramming[-V, {P}, {{W, -1}}, Thread[{lb2, ub2}], Integers]

{0, 1, 5, 1, 12}

For constraints that involve multiple items (e.g., total count of items 3 and 4 should be between 2 and 5) I am not aware of a general method to get KnapsackSolve to work, but LinearProgramming can handle any linear constraint easily:

For the case with the constraints (1) items 3 and 4 should both be present, and (2) total count of items 3 and 4 should be between 2 and 5, we can use:

LinearProgramming[-V,
 {P, {0, 0, 1, 1, 0}, {0, 0, 1, 1, 0}},
 {{W, -1}, {2, 1}, {5, -1}}, 
 Thread[{lb, ub}],
 Integers]

Adding the constraint that exactly one unit of item 2 is in the solution:

ub3 = {3, 1, 5, Infinity, Infinity};
lb3 = {0, 1, 1, 1, 0};
LinearProgramming[-V,
  {P, {0, 0, 1, 1, 0}, {0, 0, 1, 1, 0}},
  {{W, -1}, {2, 1}, {5, -1}}, 
  Thread[{lb3, ub3}], 
  Integers]
added 2 characters in body
Source Link
kglr
  • 400.5k
  • 18
  • 488
  • 929
W = 50;
V = {91, 71, 105, 103, 96};
P = {2.36, 2.12, 1.89, 3.77, 2.87};
ub = {3, Infinity, 5, Infinity, Infinity};
lb = {0, 0, 1, 1, 0}; (* items 3 and 4 should in the knapsack*)

KnapsackSolve[Transpose@{V, P, ub}, W]
{3, 9, 5, 0, 5}

Using LinearProgramming we get the same result:

LinearProgramming[-V, {P}, {{W, -1}}, Thread[{0, ub}], Integers]

{3, 9, 5, 0, 5}

Add the constraints (1) item 3 and item 4 should be selected and (2) item 3 and 4 total should be between 2 and 5:

lb = {0, 0, 1, 1, 0}; (* items 3 and 4 should in the knapsack*)

LinearProgramming[-V,
 {P, {0, 0, 1, 1, 0}, {0, 0, 1, 1, 0}},
 {{W, -1}, {2, 1}, {5, -1}}, 
 Thread[{lb, ub}],
 Integers]

{3, 0, 4, 1, 11}

Add the constraint that exactly one unit of item 2 is in the solution:

ub2 = {3, 1, 5, Infinity, Infinity};
lb2 = {0, 1, 1, 1, 0};
LinearProgramming[-V,
  {P, {0, 0, 1, 1, 0}, {0, 0, 1, 1, 0}},
  {{W, -1}, {2, 1}, {5, -1}}, 
  Thread[{lb2, ub2}], 
  Integers]

{2, 1, 4, 1, 11}

W = 50;
V = {91, 71, 105, 103, 96};
P = {2.36, 2.12, 1.89, 3.77, 2.87};
ub = {3, Infinity, 5, Infinity, Infinity};
lb = {0, 0, 1, 1, 0}; (* items 3 and 4 should in the knapsack*)

KnapsackSolve[Transpose@{V, P, ub}, W]
{3, 9, 5, 0, 5}

Using LinearProgramming we get the same result:

LinearProgramming[-V, {P}, {{W, -1}}, Thread[{0, ub}], Integers]

{3, 9, 5, 0, 5}

Add the constraints (1) item 3 and item 4 should be selected and (2) item 3 and 4 total should be between 2 and 5:

LinearProgramming[-V,
 {P, {0, 0, 1, 1, 0}, {0, 0, 1, 1, 0}},
 {{W, -1}, {2, 1}, {5, -1}}, 
 Thread[{lb, ub}],
 Integers]

{3, 0, 4, 1, 11}

Add the constraint that exactly one unit of item 2 is in the solution:

ub2 = {3, 1, 5, Infinity, Infinity};
lb2 = {0, 1, 1, 1, 0};
LinearProgramming[-V,
  {P, {0, 0, 1, 1, 0}, {0, 0, 1, 1, 0}},
  {{W, -1}, {2, 1}, {5, -1}}, 
  Thread[{lb2, ub2}], 
  Integers]

{2, 1, 4, 1, 11}

W = 50;
V = {91, 71, 105, 103, 96};
P = {2.36, 2.12, 1.89, 3.77, 2.87};
ub = {3, Infinity, 5, Infinity, Infinity};

KnapsackSolve[Transpose@{V, P, ub}, W]
{3, 9, 5, 0, 5}

Using LinearProgramming we get the same result:

LinearProgramming[-V, {P}, {{W, -1}}, Thread[{0, ub}], Integers]

{3, 9, 5, 0, 5}

Add the constraints (1) item 3 and item 4 should be selected and (2) item 3 and 4 total should be between 2 and 5:

lb = {0, 0, 1, 1, 0}; (* items 3 and 4 should in the knapsack*)

LinearProgramming[-V,
 {P, {0, 0, 1, 1, 0}, {0, 0, 1, 1, 0}},
 {{W, -1}, {2, 1}, {5, -1}}, 
 Thread[{lb, ub}],
 Integers]

{3, 0, 4, 1, 11}

Add the constraint that exactly one unit of item 2 is in the solution:

ub2 = {3, 1, 5, Infinity, Infinity};
lb2 = {0, 1, 1, 1, 0};
LinearProgramming[-V,
  {P, {0, 0, 1, 1, 0}, {0, 0, 1, 1, 0}},
  {{W, -1}, {2, 1}, {5, -1}}, 
  Thread[{lb2, ub2}], 
  Integers]

{2, 1, 4, 1, 11}

Source Link
kglr
  • 400.5k
  • 18
  • 488
  • 929

W = 50;
V = {91, 71, 105, 103, 96};
P = {2.36, 2.12, 1.89, 3.77, 2.87};
ub = {3, Infinity, 5, Infinity, Infinity};
lb = {0, 0, 1, 1, 0}; (* items 3 and 4 should in the knapsack*)

KnapsackSolve[Transpose@{V, P, ub}, W]
{3, 9, 5, 0, 5}

Using LinearProgramming we get the same result:

LinearProgramming[-V, {P}, {{W, -1}}, Thread[{0, ub}], Integers]

{3, 9, 5, 0, 5}

Add the constraints (1) item 3 and item 4 should be selected and (2) item 3 and 4 total should be between 2 and 5:

LinearProgramming[-V,
 {P, {0, 0, 1, 1, 0}, {0, 0, 1, 1, 0}},
 {{W, -1}, {2, 1}, {5, -1}}, 
 Thread[{lb, ub}],
 Integers]

{3, 0, 4, 1, 11}

Add the constraint that exactly one unit of item 2 is in the solution:

ub2 = {3, 1, 5, Infinity, Infinity};
lb2 = {0, 1, 1, 1, 0};
LinearProgramming[-V,
  {P, {0, 0, 1, 1, 0}, {0, 0, 1, 1, 0}},
  {{W, -1}, {2, 1}, {5, -1}}, 
  Thread[{lb2, ub2}], 
  Integers]

{2, 1, 4, 1, 11}