## Knapsack Optimization

## Main.KnapsackOptimization History

Show minor edits - Show changes to output

Changed line 90 from:

print("Objective = %f" % (m.options.objfcnval))

to:

print("Objective = %f" % (-m.options.objfcnval))

Changed lines 5-6 from:

to:

(:html:)

<iframe width="560" height="315" src="https://www.youtube.com/embed/UB2VH9lFelY" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>

(:htmlend:)

<iframe width="560" height="315" src="https://www.youtube.com/embed/UB2VH9lFelY" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>

(:htmlend:)

Added line 93:

%width=550px%Attach:knapsack_optimization.png

Added lines 49-50:

An alternative to using optimization is a greedy algorithm where the items are successively selected based on a metric such as the highest value to weight ratio. This is done until the weight limit is exceeded. While this approach is computationally fast and intuitive, it may give suboptimal results because a constraint limit (weight) is not reached. The greedy algorithm is an example of a heuristic (rule-based) approach that is often specific to the application. Heuristics may be valuable to initialize the optimization solution or identify at least one feasible solution that can be improved with optimization.

Changed line 30 from:

<td align="center" bgcolor="#~~fbc76d~~">5</td>

to:

<td align="center" bgcolor="#fbf96d">5</td>

Changed line 32 from:

<td align="center" bgcolor="#~~fbf96d~~">4</td>

to:

<td align="center" bgcolor="#fbc76d">4</td>

Changed lines 68-69 from:

m.Maximize(m.sum(v[i]*x[i] for i in range(items)))

to:

m.Maximize(m.sum([v[i]*x[i] for i in range(items)]))

Deleted lines 84-85:

m.open_folder()

Changed lines 68-69 from:

m.~~Obj~~(~~-~~sum(v[i]*x[i] for i in range(items)))

to:

m.Maximize(m.sum(v[i]*x[i] for i in range(items)))

Changed line 72 from:

m.Equation(sum([w[i]*x[i] for i in range(items)]) <= limit)

to:

m.Equation(m.sum([w[i]*x[i] for i in range(items)]) <= limit)

Deleted lines 88-106:

----

(:html:)

<div id="disqus_thread"></div>

<script type="text/javascript">

/* * * CONFIGURATION VARIABLES: EDIT BEFORE PASTING INTO YOUR WEBPAGE * * */

var disqus_shortname = 'apmonitor'; // required: replace example with your forum shortname

/* * * DON'T EDIT BELOW THIS LINE * * */

(function() {

var dsq = document.createElement('script'); dsq.type = 'text/javascript'; dsq.async = true;

dsq.src = 'https://' + disqus_shortname + '.disqus.com/embed.js';

(document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);

})();

</script>

<noscript>Please enable JavaScript to view the <a href="https://disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>

<a href="https://disqus.com" class="dsq-brlink">comments powered by <span class="logo-disqus">Disqus</span></a>

(:htmlend:)

Changed line 38 from:

The purpose of the [[https://en.wikipedia.org/wiki/Knapsack_problem|knapsack problem]] is to select which items to fit into the bag without exceeding a weight limit of what can be carried. ~~Solve~~ the problem with ~~a~~ integer programming solver by setting up each item as a binary variable (0 or 1). A zero (0) is a decision to not place the item in the knapsack while a one (1) is a decision to include it. More generally, suppose there are {`n`} items with values {`v_1, \ldots, v_n`} and weights {`w_1, \ldots, w_n`} with a total weight limit of the sack {`W=14`}. The decision variables are {`x_1, \ldots, x_n`} that can be 0 or 1. The following optimization formulation represents this problem as an integer program:

to:

The purpose of the [[https://en.wikipedia.org/wiki/Knapsack_problem|knapsack problem]] is to select which items to fit into the bag without exceeding a weight limit of what can be carried. We solve the problem with an integer programming solver ([[https://apopt.com|APOPT]]) by setting up each item as a binary variable (0 or 1). A zero (0) is a decision to not place the item in the knapsack while a one (1) is a decision to include it. More generally, suppose there are {`n`} items with values {`v_1, \ldots, v_n`} and weights {`w_1, \ldots, w_n`} with a total weight limit of the sack {`W=14`}. The decision variables are {`x_1, \ldots, x_n`} that can be 0 or 1. The following optimization formulation represents this problem as an integer program:

Changed line 9 from:

There are 4 items available to be placed in a knapsack: a towel, hammer, wrench, and screwdriver. The value ~~of the items and weight~~ are listed in the table below.

to:

There are 4 items available to be placed in a knapsack: a towel, hammer, wrench, and screwdriver. The value and weight of the items are listed in the table below.

Changed lines 5-6 from:

'''Objective:''' Maximize the value of items that can fit into a knapsack without exceeding a maximum weight constraint~~ of 14~~.

to:

'''Objective:''' Maximize the value of items that can fit into a knapsack without exceeding a maximum weight constraint.

Changed line 38 from:

The purpose of the [[https://en.wikipedia.org/wiki/Knapsack_problem|knapsack problem]] is to select which items to fit into the bag without exceeding a weight limit of what can be carried. Solve the problem with a integer programming solver by setting up each item as a binary variable (0 or 1). A zero (0) is a decision to not place the item in the knapsack while a one (1) is a decision to include it. More generally, suppose there are {`n`} items with values {`v_1, \ldots, v_n`} and weights {`w_1, \ldots, w_n`} with a total weight limit of the sack {~~`W`~~}. The decision variables are {`x_1, \ldots, x_n`} that can be 0 or 1. The following optimization formulation represents this problem as an integer program:

to:

The purpose of the [[https://en.wikipedia.org/wiki/Knapsack_problem|knapsack problem]] is to select which items to fit into the bag without exceeding a weight limit of what can be carried. Solve the problem with a integer programming solver by setting up each item as a binary variable (0 or 1). A zero (0) is a decision to not place the item in the knapsack while a one (1) is a decision to include it. More generally, suppose there are {`n`} items with values {`v_1, \ldots, v_n`} and weights {`w_1, \ldots, w_n`} with a total weight limit of the sack {`W=14`}. The decision variables are {`x_1, \ldots, x_n`} that can be 0 or 1. The following optimization formulation represents this problem as an integer program:

Changed line 21 from:

<td><b>Value (v)</b></td>

to:

<td><b>Item Value (<i>v<sub>i</sub></i>)</b></td>

Changed line 28 from:

<td align="center"><b>Weight (w)</b></td>

to:

<td align="center"><b>Item Weight (<i>w<sub>i</sub></i>)</b></td>

Deleted lines 10-11:

Changed lines 13-14 from:

<img src="/me575/uploads/Main/knapsack.png">

to:

<table><tr>

<td><img src="/me575/uploads/Main/knapsack.png"></td>

<td>

<td><img src="/me575/uploads/Main/knapsack.png"></td>

<td>

Added line 35:

</td></tr></table>

Changed line 15 from:

<img src="/uploads/Main/knapsack.png">

to:

<img src="/me575/uploads/Main/knapsack.png">

Changed lines 11-12 from:

to:

Added lines 14-16:

<img src="/uploads/Main/knapsack.png">

Changed lines 15-19 from:

<td><b>Value</b></td>

<td align="center" bgcolor="#~~fb946d~~">11</td>

<td align="center" bgcolor="#~~fbc76d~~">8</td>

<td align="center" bgcolor="#~~bafb6d~~">3</td>

<td align="center" bgcolor="#~~fbf96d~~">6</td>

<td align="center" bgcolor="#

<td align="center" bgcolor="#

<td align="center" bgcolor="#

<td align="center" bgcolor="#

to:

<td><b>Value (v)</b></td>

<td align="center" bgcolor="#bafb6d">11</td>

<td align="center" bgcolor="#fbf96d">8</td>

<td align="center" bgcolor="#fb946d">3</td>

<td align="center" bgcolor="#fbc76d">6</td>

<td align="center" bgcolor="#bafb6d">11</td>

<td align="center" bgcolor="#fbf96d">8</td>

<td align="center" bgcolor="#fb946d">3</td>

<td align="center" bgcolor="#fbc76d">6</td>

Changed lines 22-26 from:

<td align="center"><b>Weight</b></td>

<td align="center" bgcolor="#~~fb946d~~">3</td>

<td align="center" bgcolor="#~~fbf96d~~">5</td>

<td align="center" bgcolor="#~~bafb6d~~">7</td>

<td align="center" bgcolor="#~~fbc76d~~">4</td>

<td align="center" bgcolor="#

<td align="center" bgcolor="#

<td align="center" bgcolor="#

<td align="center" bgcolor="#

to:

<td align="center"><b>Weight (w)</b></td>

<td align="center" bgcolor="#bafb6d">3</td>

<td align="center" bgcolor="#fbc76d">5</td>

<td align="center" bgcolor="#fb946d">7</td>

<td align="center" bgcolor="#fbf96d">4</td>

<td align="center" bgcolor="#bafb6d">3</td>

<td align="center" bgcolor="#fbc76d">5</td>

<td align="center" bgcolor="#fb946d">7</td>

<td align="center" bgcolor="#fbf96d">4</td>

Changed lines 23-26 from:

<td align="center">3</td>

<td align="center">5</td>

<td align="center">7</td>

<td align="center">4</td>

<td align="center">5</td>

<td align="center">7</td>

<td align="center">4</td>

to:

<td align="center" bgcolor="#fb946d">3</td>

<td align="center" bgcolor="#fbf96d">5</td>

<td align="center" bgcolor="#bafb6d">7</td>

<td align="center" bgcolor="#fbc76d">4</td>

<td align="center" bgcolor="#fbf96d">5</td>

<td align="center" bgcolor="#bafb6d">7</td>

<td align="center" bgcolor="#fbc76d">4</td>

Changed lines 15-19 from:

<td><b>Value</b></td><td align="center" ~~color~~="~~red~~">11</td><td align="center"~~>8</td><td align~~="~~center~~">~~3~~</td><td align="center">6</td>

to:

<td><b>Value</b></td>

<td align="center" bgcolor="#fb946d">11</td>

<td align="center" bgcolor="#fbc76d">8</td>

<td align="center" bgcolor="#bafb6d">3</td>

<td align="center" bgcolor="#fbf96d">6</td>

<td align="center" bgcolor="#fb946d">11</td>

<td align="center" bgcolor="#fbc76d">8</td>

<td align="center" bgcolor="#bafb6d">3</td>

<td align="center" bgcolor="#fbf96d">6</td>

Changed lines 22-26 from:

<td align="center"><b>Weight</b></td><td align="center">3</td><td align="center">5</td><td align="center">7</td><td align="center">4</td>

to:

<td align="center"><b>Weight</b></td>

<td align="center">3</td>

<td align="center">5</td>

<td align="center">7</td>

<td align="center">4</td>

<td align="center">3</td>

<td align="center">5</td>

<td align="center">7</td>

<td align="center">4</td>

Changed line 15 from:

<td><b>Value</b></td><td align="center">11</td><td align="center">8</td><td align="center">3</td><td align="center">6</td>

to:

<td><b>Value</b></td><td align="center" color="red">11</td><td align="center">8</td><td align="center">3</td><td align="center">6</td>

Changed line 5 from:

'''Objective:''' Maximize the value of items that can fit into a knapsack without exceeding a maximum weight constraint.

to:

'''Objective:''' Maximize the value of items that can fit into a knapsack without exceeding a maximum weight constraint of 14.

Changed line 10 from:

<table border=~~1px~~ align="center">

to:

<table border=0 align="center">

Changed line 18 from:

<td align="center"><b>Weight</b></td><td align="center">3</td><td align="center">5</td><td align="center">7</td><td>4</td>

to:

<td align="center"><b>Weight</b></td><td align="center">3</td><td align="center">5</td><td align="center">7</td><td align="center">4</td>

Changed line 18 from:

<td><b>Weight</b></td><td>3</td><td>5</td><td>7</td><td>4</td>

to:

<td align="center"><b>Weight</b></td><td align="center">3</td><td align="center">5</td><td align="center">7</td><td>4</td>

Changed line 15 from:

<td><b>Value</b></td><td>11</td><td>8</td><td>3</td><td>6</td>

to:

<td><b>Value</b></td><td align="center">11</td><td align="center">8</td><td align="center">3</td><td align="center">6</td>

Changed line 10 from:

<table border=1px>

to:

<table border=1px align="center">

Changed lines 26-30 from:

{$\max ~~& ~~\sum _{i=1}^{n} v_{i} x_{i}$}

{$\textrm{subject to}~~& ~~\sum _{i=1}^{n} w_{i} x_{i}\leq W$}

{$~~ & ~~x_{i}\in \{0,1\}$}

{$\textrm{subject to}

{$

to:

{$\max \sum _{i=1}^{n} v_{i} x_{i}$}

{$\textrm{subject to} \sum _{i=1}^{n} w_{i} x_{i}\leq W$}

{$x_{i}\in \{0,1\}$}

{$\textrm{subject to} \sum _{i=1}^{n} w_{i} x_{i}\leq W$}

{$x_{i}\in \{0,1\}$}

Added lines 1-92:

(:title Knapsack Optimization:)

(:keywords Optimization, Selection, Volume, Weight, Decision, Maximize, Minimize, Benchmark:)

(:description The objective of the knapsack optimization problem is maximize the value of selected items without exceeding a weight constraint. This knapsack problem is solved with integer programming in Python Gekko.:)

'''Objective:''' Maximize the value of items that can fit into a knapsack without exceeding a maximum weight constraint.

There are 4 items available to be placed in a knapsack: a towel, hammer, wrench, and screwdriver. The value of the items and weight are listed in the table below.

(:html:)

<table>

<tr>

<td></td><td><b>Towel</b></td><td><b>Hammer</b></td><td><b>Wrench</b></td><td><b>Screwdriver</b></td>

</tr>

<tr>

<td><b>Value</b></td><td>11</td><td>8</td><td>3</td><td>6</td>

</tr>

<tr>

<td><b>Weight</b></td><td>3</td><td>5</td><td>7</td><td>4</td>

</tr>

</table>

(:htmlend:)

The purpose of the [[https://en.wikipedia.org/wiki/Knapsack_problem|knapsack problem]] is to select which items to fit into the bag without exceeding a weight limit of what can be carried. Solve the problem with a integer programming solver by setting up each item as a binary variable (0 or 1). A zero (0) is a decision to not place the item in the knapsack while a one (1) is a decision to include it. More generally, suppose there are {`n`} items with values {`v_1, \ldots, v_n`} and weights {`w_1, \ldots, w_n`} with a total weight limit of the sack {`W`}. The decision variables are {`x_1, \ldots, x_n`} that can be 0 or 1. The following optimization formulation represents this problem as an integer program:

{$\max & \sum _{i=1}^{n} v_{i} x_{i}$}

{$\textrm{subject to} & \sum _{i=1}^{n} w_{i} x_{i}\leq W$}

{$ & x_{i}\in \{0,1\}$}

(:html:)

(:htmlend:)

!!!! Python GEKKO Solution

(:div id=gekko:)

(:source lang=python:)

from gekko import GEKKO

y = ['towel','hammer','wrench','screwdriver']

v = [11,8,3,6]

w = [3,5,7,4]

items = len(y)

# Create model

m = GEKKO()

# Variables

x = m.Array(m.Var,len(y),lb=0,ub=1,integer=True)

# Objective

m.Obj(-sum(v[i]*x[i] for i in range(items)))

# Constraint

limit = 14

m.Equation(sum([w[i]*x[i] for i in range(items)]) <= limit)

# Optimize with APOPT

m.options.SOLVER = 1

m.solve()

# Print the value of the variables at the optimum

for i in range(items):

print("%s = %f" % (y[i], x[i].value[0]))

# Print the value of the objective

print("Objective = %f" % (m.options.objfcnval))

m.open_folder()

(:sourceend:)

----

(:html:)

<div id="disqus_thread"></div>

<script type="text/javascript">

/* * * CONFIGURATION VARIABLES: EDIT BEFORE PASTING INTO YOUR WEBPAGE * * */

var disqus_shortname = 'apmonitor'; // required: replace example with your forum shortname

/* * * DON'T EDIT BELOW THIS LINE * * */

(function() {

var dsq = document.createElement('script'); dsq.type = 'text/javascript'; dsq.async = true;

dsq.src = 'https://' + disqus_shortname + '.disqus.com/embed.js';

(document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);

})();

</script>

<noscript>Please enable JavaScript to view the <a href="https://disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>

<a href="https://disqus.com" class="dsq-brlink">comments powered by <span class="logo-disqus">Disqus</span></a>

(:htmlend:)

(:keywords Optimization, Selection, Volume, Weight, Decision, Maximize, Minimize, Benchmark:)

(:description The objective of the knapsack optimization problem is maximize the value of selected items without exceeding a weight constraint. This knapsack problem is solved with integer programming in Python Gekko.:)

'''Objective:''' Maximize the value of items that can fit into a knapsack without exceeding a maximum weight constraint.

There are 4 items available to be placed in a knapsack: a towel, hammer, wrench, and screwdriver. The value of the items and weight are listed in the table below.

(:html:)

<table>

<tr>

<td></td><td><b>Towel</b></td><td><b>Hammer</b></td><td><b>Wrench</b></td><td><b>Screwdriver</b></td>

</tr>

<tr>

<td><b>Value</b></td><td>11</td><td>8</td><td>3</td><td>6</td>

</tr>

<tr>

<td><b>Weight</b></td><td>3</td><td>5</td><td>7</td><td>4</td>

</tr>

</table>

(:htmlend:)

The purpose of the [[https://en.wikipedia.org/wiki/Knapsack_problem|knapsack problem]] is to select which items to fit into the bag without exceeding a weight limit of what can be carried. Solve the problem with a integer programming solver by setting up each item as a binary variable (0 or 1). A zero (0) is a decision to not place the item in the knapsack while a one (1) is a decision to include it. More generally, suppose there are {`n`} items with values {`v_1, \ldots, v_n`} and weights {`w_1, \ldots, w_n`} with a total weight limit of the sack {`W`}. The decision variables are {`x_1, \ldots, x_n`} that can be 0 or 1. The following optimization formulation represents this problem as an integer program:

{$\max & \sum _{i=1}^{n} v_{i} x_{i}$}

{$\textrm{subject to} & \sum _{i=1}^{n} w_{i} x_{i}\leq W$}

{$ & x_{i}\in \{0,1\}$}

(:html:)

(:htmlend:)

!!!! Python GEKKO Solution

(:div id=gekko:)

(:source lang=python:)

from gekko import GEKKO

y = ['towel','hammer','wrench','screwdriver']

v = [11,8,3,6]

w = [3,5,7,4]

items = len(y)

# Create model

m = GEKKO()

# Variables

x = m.Array(m.Var,len(y),lb=0,ub=1,integer=True)

# Objective

m.Obj(-sum(v[i]*x[i] for i in range(items)))

# Constraint

limit = 14

m.Equation(sum([w[i]*x[i] for i in range(items)]) <= limit)

# Optimize with APOPT

m.options.SOLVER = 1

m.solve()

# Print the value of the variables at the optimum

for i in range(items):

print("%s = %f" % (y[i], x[i].value[0]))

# Print the value of the objective

print("Objective = %f" % (m.options.objfcnval))

m.open_folder()

(:sourceend:)

----

(:html:)

<div id="disqus_thread"></div>

<script type="text/javascript">

/* * * CONFIGURATION VARIABLES: EDIT BEFORE PASTING INTO YOUR WEBPAGE * * */

var disqus_shortname = 'apmonitor'; // required: replace example with your forum shortname

/* * * DON'T EDIT BELOW THIS LINE * * */

(function() {

var dsq = document.createElement('script'); dsq.type = 'text/javascript'; dsq.async = true;

dsq.src = 'https://' + disqus_shortname + '.disqus.com/embed.js';

(document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);

})();

</script>

<noscript>Please enable JavaScript to view the <a href="https://disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>

<a href="https://disqus.com" class="dsq-brlink">comments powered by <span class="logo-disqus">Disqus</span></a>

(:htmlend:)