Design Optimization

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

%width=550px%Attach:knapsack_optimization.png

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

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

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

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

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

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:

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.

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

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:

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

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

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

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

<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"><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">3</td>
<td align="center">5</td>
<td align="center">7</td>
<td align="center">4</td>

<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>

<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><b>Value</b></td><td align="center">11</td><td align="center">8</td><td align="center">3</td><td align="center">6</td>

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

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

<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>

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

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

<table border=1px>

<table>

{$\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\}$}