Integer Programming：Solving the Knapsack Problem in Python with PuLP

I’ll solve an integer programming example using $Python$, showing the implementation, solution, and visualization.

Let’s solve a classic integer programming problem - the Knapsack Problem.

Integer Programming Example: Knapsack Problem

The knapsack problem is a classic optimization problem: Given a set of items, each with a weight and a value, determine which items to include in a collection so that the total weight is less than or equal to a given limit and the total value is maximized.

Mathematically, we can formulate this as:

$$\begin{align}
\text{Maximize} & \sum_{i=1}^{n} v_i x_i \
\text{Subject to} & \sum_{i=1}^{n} w_i x_i \leq W \
& x_i \in {0,1} \quad \forall i \in {1,2,\ldots,n}
\end{align}$$

Where:

• $v_i$ is the value of item $i$
• $w_i$ is the weight of item $i$
• $x_i$ is a binary variable indicating whether item $i$ is selected
• $W$ is the maximum weight capacity

Let’s implement this using $PuLP$, a popular linear programming library in $Python$:

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import seaborn as sns
from pulp import *

# Problem data
items = ["Item_" + str(i) for i in range(1, 11)]
values = [10, 13, 18, 31, 7, 15, 28, 22, 11, 17]
weights = [5, 8, 12, 16, 3, 9, 14, 11, 5, 8]
capacity = 40

# Create a dataframe for better visualization
data = pd.DataFrame({
    'Item': items,
    'Value': values,
    'Weight': weights,
    'Value/Weight': [v/w for v, w in zip(values, weights)]
})

# Create the LP problem
prob = LpProblem("Knapsack_Problem", LpMaximize)

# Create binary variables for each item
x = LpVariable.dicts("Include", items, lowBound=0, upBound=1, cat='Integer')

# Objective function: maximize total value
prob += lpSum([values[i] * x[items[i]] for i in range(len(items))]), "Total Value"

# Constraint: total weight must not exceed capacity
prob += lpSum([weights[i] * x[items[i]] for i in range(len(items))]) <= capacity, "Weight_Constraint"

# Solve the problem
prob.solve()

# Extract results
selected_items = []
selected_values = []
selected_weights = []
total_value = 0
total_weight = 0

for i in range(len(items)):
    if value(x[items[i]]) == 1:
        selected_items.append(items[i])
        selected_values.append(values[i])
        selected_weights.append(weights[i])
        total_value += values[i]
        total_weight += weights[i]

# Create results dataframe
results = pd.DataFrame({
    'Item': selected_items,
    'Value': selected_values,
    'Weight': selected_weights
})

# Print solution information
print("Status:", LpStatus[prob.status])
print("\nSelected Items:")
print(results)
print("\nTotal Value:", total_value)
print("Total Weight:", total_weight)
print("Capacity:", capacity)

# Visualization of the solution
plt.figure(figsize=(12, 10))

# Plot 1: All items with Value vs Weight
plt.subplot(2, 2, 1)
sns.scatterplot(x='Weight', y='Value', data=data, s=100)
for i, row in data.iterrows():
    plt.annotate(row['Item'], (row['Weight'], row['Value']), fontsize=9)
plt.title('All Items: Value vs Weight')
plt.grid(True, alpha=0.3)

# Plot 2: Selected vs Not Selected
plt.subplot(2, 2, 2)
selected_status = ['Selected' if item in selected_items else 'Not Selected' for item in items]
plot_data = data.copy()
plot_data['Status'] = selected_status
sns.scatterplot(x='Weight', y='Value', hue='Status', data=plot_data, s=100)
plt.title('Selected vs Not Selected Items')
plt.grid(True, alpha=0.3)

# Plot 3: Value/Weight Efficiency
plt.subplot(2, 2, 3)
sns.barplot(x='Item', y='Value/Weight', data=data)
plt.xticks(rotation=45)
plt.title('Value/Weight Ratio of Items')
plt.grid(True, alpha=0.3)

# Plot 4: Contribution to Solution
plt.subplot(2, 2, 4)
if not results.empty:
    results['Percentage'] = results['Value'] / total_value * 100
    sns.barplot(x='Item', y='Percentage', data=results)
    plt.xticks(rotation=45)
    plt.title('Contribution to Total Value (%)')
    plt.ylabel('Percentage of Total Value')
    plt.grid(True, alpha=0.3)

plt.tight_layout()
plt.show()

Code Explanation

1. Setting up the problem:

   • We defined $10$ items with corresponding values and weights
   • The knapsack capacity is set to $40$ units

2. Formulating the integer program with PuLP:

   • Created binary decision variables for each item (x)
   • Set the objective function to maximize total value
   • Added a constraint to ensure the total weight doesn’t exceed capacity

3. Solving the problem:

   • $PuLP$ uses branch and bound algorithms to solve the integer program
   • Results are extracted and organized into a pandas DataFrame

4. Visualization:

   • Four plots are created to analyze different aspects of the solution:
     • All items plotted by weight vs. value
     • Selected vs. not selected items
     • Value/weight efficiency ratio for each item
     • Each selected item’s contribution to the total value

Solution Analysis

When executed, this code will select the optimal combination of items that maximizes value while staying within the weight limit.

The optimization model makes trade-offs based on both the absolute value of items and their weight efficiency (value per unit weight).

Items with high values and relatively low weights are preferred.

The visualizations help us understand:

1. The distribution of all items in the value-weight space
2. Which items were selected by the optimizer
3. The efficiency (value/weight) of each item
4. How much each selected item contributes to the total solution value

This example demonstrates how integer programming can be applied to combinatorial optimization problems, finding the optimal solution among a finite but potentially very large set of possibilities.

Result

Status: Optimal

Selected Items:
     Item  Value  Weight
0  Item_1     10       5
1  Item_4     31      16
2  Item_5      7       3
3  Item_8     22      11
4  Item_9     11       5

Total Value: 81
Total Weight: 40
Capacity: 40