Knapsack Optimization

Main.KnapsackOptimization History

Show minor edits - Show changes to output

May 23, 2021, at 07:22 PM by 136.36.4.38 -
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.
May 23, 2021, at 05:50 PM by 136.36.4.38 -
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>
March 12, 2021, at 05:00 PM by 10.35.117.248 -
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)
June 21, 2020, at 04:41 AM by 136.36.211.159 -
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:)
October 21, 2019, at 04:23 AM by 136.36.211.159 -
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:
October 21, 2019, at 04:21 AM by 136.36.211.159 -
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.
October 21, 2019, at 04:20 AM by 136.36.211.159 -
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:
October 21, 2019, at 02:36 AM by 136.36.211.159 -
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>
October 21, 2019, at 02:33 AM by 136.36.211.159 -
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>
Added line 35:
</td></tr></table>
October 21, 2019, at 02:32 AM by 136.36.211.159 -
Changed line 15 from:
<img src="/uploads/Main/knapsack.png">
to:
<img src="/me575/uploads/Main/knapsack.png">
October 21, 2019, at 02:31 AM by 136.36.211.159 -
Changed lines 11-12 from:
Attach:knapsack.png
to:

Added lines 14-16:

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

October 21, 2019, at 02:30 AM by 136.36.211.159 -
Added lines 10-11:

Attach:knapsack.png
October 21, 2019, at 02:24 AM by 136.36.211.159 -
Added lines 6-7:

Attach:knapsack_items.png
October 21, 2019, at 02:20 AM by 136.36.211.159 -
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>
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>
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>
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>
October 21, 2019, at 02:18 AM by 136.36.211.159 -
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>
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>
October 21, 2019, at 02:17 AM by 136.36.211.159 -
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>
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>
October 21, 2019, at 02:12 AM by 136.36.211.159 -
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>
October 21, 2019, at 01:17 AM by 136.36.211.159 -
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.
October 21, 2019, at 01:17 AM by 136.36.211.159 -
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>
October 21, 2019, at 01:17 AM by 136.36.211.159 -
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>
October 21, 2019, at 01:08 AM by 136.36.211.159 -
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>
October 21, 2019, at 01:07 AM by 136.36.211.159 -
Changed line 10 from:
<table border=1px>
to:
<table border=1px align="center">
October 21, 2019, at 01:06 AM by 136.36.211.159 -
Changed line 10 from:
<table>
to:
<table border=1px>
October 21, 2019, at 01:06 AM by 136.36.211.159 -
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\}$}
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\}$}
October 21, 2019, at 12:49 AM by 136.36.211.159 -
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:)