Solving operations research (OR) problems with ChatGPT
Ever since the emergence of ChatGPT, I’ve been thinking about how ChatGPT would influence the world of optimization and Operations Research (OR). There has been news about ChatGPT passing high school and undergraduate level math exams, which piques my interest in exploring how well it can do on solving OR problems. In this article, I will use a classic OR problem — 0/1 knapsack problem to run some tests.
In the realm of optimization and decision-making conundrums, the knapsack problem has long been a classic benchmark. It challenges us to select a combination of items, each with its own weight and value, in such a way that we maximize the total value while staying within a given weight constraint. Dynamic programming is an efficient algorithm we genrally use to solve 0/1 knapsack problems.
I started with a very small example, and asked ChatGPT to solve it.
Me: Consider a knapsack problem, where the capacity of the knapsack is 10lbs. I have 4 items to choose from, whose values are $10, $40, $30, $50 and weights are 5lbs, 4lbs, 6lbs, 3lbs respectively. Could you solve this problem for me?
ChatGPT: Certainly! The knapsack problem is a classic optimization problem where the goal is to maximize the total value of items selected for a knapsack, subject to the constraint that the total weight of the selected items does not exceed the knapsack’s capacity.
In your case, you have 4 items with their respective values and weights:
Item 1: Value = $10, Weight = 5lbs Item 2: Value = $40, Weight = 4lbs Item 3: Value = $30, Weight = 6lbs Item 4: Value = $50, Weight = 3lbs
Knapsack Capacity = 10lbs
To solve this problem, you can use a dynamic programming approach. Create a 2D table where rows represent items and columns represent the remaining knapsack capacities (from 0lbs to 10lbs). Fill in the table iteratively to find the maximum value that can be obtained for each combination of items and remaining capacities.
Here’s the table filling process:
Capacity (lbs) 0 1 2 3 4 5 6 7 8 9 10
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Item 1 (5lbs) 0 0 0 0 0 10 10 10 10 10 10
Item 2 (4lbs) 0 0 0 0 40 40 40 40 50 50 50
Item 3 (6lbs) 0 0 0 0 40 40 30 70 70 70 70
Item 4 (3lbs) 0 0 0 50 50 50 50 70 70 70 80
The table shows the maximum value that can be obtained for each combination of items and remaining capacities. The final cell (bottom-right) has a value of $80, which is the maximum value that can be obtained with a knapsack capacity of 10lbs.
To find the items that should be selected, you can backtrack from the last cell to the first cell while considering the decisions that led to the maximum value. In this case, you would select Item 2 and Item 4, which have a total value of $40 + $50 = $90 and a total weight of 4lbs + 3lbs = 7lbs, which is within the knapsack’s capacity of 10lbs.
So, the optimal solution is to select Item 2 and Item 4, which gives you a total value of $90.
Apparently, we notice that ChatGPT is able to pick the right approach to solve this problem, but the final solution given by ChatGPT is not aligned with its reasoning process. Specifically, the dynamic programming (DP) table shows $80 (bottom right cell) as the optimal objective value, but ChatGPT concluded $90 is the final answer.
To check which is the correct solution, I wrote up a piece of Python script as below to carry out the DP algorithm.
import numpy as np
v = [10, 40, 30, 50]
w = [5, 4, 6, 3]
c = 10
dp = np.zeros((5,11))
for i in range(1,5):
for j in range(1,11):
if j < w[i-1]:
dp[i,j] = dp[i-1,j]
else:
dp[i,j] = max(dp[i-1,j],dp[i-1,j-w[i-1]]+v[i-1])
dp[1:,1:]
The DP table printed out is as follows.
This confirms that the conclusion ChatGPT arrived at is correct, but the the DP table given by ChatGPT is wrong. Then I continued to ask it to correct the DP table.
Me: I think your solution is correct, but the table has some errors.
ChatGPT: I apologize for any confusion. Let me correct the table for you. Here’s the corrected dynamic programming table for the knapsack problem:
Capacity (lbs) 0 1 2 3 4 5 6 7 8 9 10
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Item 1 (5lbs) 0 0 0 0 0 10 10 10 10 10 10
Item 2 (4lbs) 0 0 0 0 40 40 40 40 40 50 50
Item 3 (6lbs) 0 0 0 0 40 40 40 40 40 50 70
Item 4 (3lbs) 0 0 0 50 50 50 90 90 90 90 90
Now, the table is correct. The value in the bottom-right cell is $90, which represents the maximum value that can be obtained with a knapsack capacity of 10lbs. As mentioned before, the optimal solution is to select Item 2 and Item 4, which gives you a total value of $90.
Interestingly, ChatGPT is able to do some corrections to the table, so that the bottom right cell is aligned with $90. However, if we look at the table more closely, the last row of the table is still not correct. The cell in 4th row and 7th column (corresponding to a knapsack capacity of 6lbs) should be $50 instead of $90. A knapsack of 6lbs capacity wouldn’t allow us to choose item 2 and 4 to reach $90, since the total weight of item 2 and 4 is 7lbs which exceeds the capacity of the knapsack.
I then asked it to write some code to solve this problem.
Me: Could you write Python code to solve this problem?
ChatGPT: Certainly! You can solve the 0/1 knapsack problem using dynamic programming in Python. Here’s a Python code snippet to solve the problem for the specific instance you provided:
def knapsack(values, weights, capacity):
n = len(values)
# Initialize a table to store the maximum values for different capacities
dp = [[0] * (capacity + 1) for _ in range(n + 1)]for i in range(1, n + 1):
for w in range(capacity + 1):
# If the current item's weight is more than the current capacity, skip it
if weights[i - 1] > w:
dp[i][w] = dp[i - 1][w]
else:
# Choose the maximum between including and excluding the current item
dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
# Backtrack to find the selected items
selected_items = []
i, w = n, capacity
while i > 0 and w > 0:
if dp[i][w] != dp[i - 1][w]:
selected_items.append(i - 1)
w -= weights[i - 1]
i -= 1
return dp[n][capacity], selected_items
# Item values and weights
values = [10, 40, 30, 50]
weights = [5, 4, 6, 3]
knapsack_capacity = 10
max_value, selected_items = knapsack(values, weights, knapsack_capacity)
print(f"Maximum value: ${max_value}")
print("Selected items:")
for i in selected_items:
print(f"Item {i + 1} (Value: ${values[i]}, Weight: {weights[i]} lbs)")
When you run this code, it will output the maximum value and the selected items that should be placed in the knapsack. In your specific case, it will correctly select Item 2 and Item 4, which have a total value of $90 and a total weight of 7 lbs, within the knapsack’s capacity of 10 lbs.
This code printed out the optimal solution clearly and correctly. The DP table calculated by this code is also correct.
I then went further to test an instance of a larger scale, a knapsack problem with the capacity of the knapsack being 500lbs and 10 items to choose from. The value and weight of each item are randomly generated using the code below.
import numpy as np
np.random.seed(0)
w = np.random.normal(10, 3, 100)
w = [int(x) if x>= 1 else 1 for x in w]
v = np.random.normal(100, 30, 100)
v = [int(x) if x>= 10 else 10 for x in v]dp = np.zeros((101,501))
for i in range(1,101):
for j in range(1,501):
if j < w[i-1]:
dp[i,j] = dp[i-1,j]
else:
dp[i,j] = max(dp[i-1,j],dp[i-1,j-w[i-1]]+v[i-1])
dp[1:,1:]
I copied and pasted the generated values and weights, and asked ChatGPT to solve it.
Me: Consider a knapsack problem, where the capacity of the knapsack is 500lbs. I have 100 items to choose from, whose values are given by the list [156, 59, 61, 129, 64, 158, 87, 77, 157, 144, 156, 127, 74, 157, 91, 124, 128, 95, 118, 127, 111, 67, 108, 139, 79, 95, 86, 155, 120, 112, 76, 116, 79, 100, 80, 120, 117, 93, 111, 67, 55, 113, 105, 119, 171, 128, 72, 133, 60, 86, 97, 151, 77, 75, 97, 80, 133, 67, 65, 86, 85, 157, 128, 102, 63, 125, 69, 53, 135, 109, 127, 109, 125, 80, 68, 120, 75, 79, 86, 100, 89, 58, 80, 33, 118, 51, 66, 101, 77, 146, 61, 108, 98, 64, 115, 94, 123, 124, 164, 140] and weights are given by the list [15, 11, 12, 16, 15, 7, 12, 9, 9, 11, 10, 14, 12, 10, 11, 11, 14, 9, 10, 7, 2, 11, 12, 7, 16, 5, 10, 9, 14, 14, 10, 11, 7, 4, 8, 10, 13, 13, 8, 9, 6, 5, 4, 15, 8, 8, 6, 12, 5, 9, 7, 11, 8, 6, 9, 11, 10, 10, 8, 8, 7, 8, 7, 4, 10, 8, 5, 11, 7, 10, 12, 10, 13, 6, 11, 7, 7, 8, 9, 10, 6, 12, 11, 5, 14, 15, 13, 9, 6, 13, 8, 13, 10, 12, 11, 12, 10, 15, 10, 11] respectively. Could you solve this problem for me?
ChatGPT: Solving the knapsack problem for 100 items with a capacity of 500 lbs is a computationally intensive task. However, I can provide you with the Python code to solve this problem using dynamic programming, but please be aware that it may take some time to run.
Here’s the Python code to solve the knapsack problem with the provided values and weights:
def knapsack(values, weights, capacity):
n = len(values)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]for i in range(1, n + 1):
for w in range(capacity + 1):
if weights[i - 1] > w:
dp[i][w] = dp[i - 1][w]
else:
dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
selected_items = []
i, w = n, capacity
while i > 0 and w > 0:
if dp[i][w] != dp[i - 1][w]:
selected_items.append(i - 1)
w -= weights[i - 1]
i -= 1
return dp[n][capacity], selected_items
# Item values and weights
values = [
156, 59, 61, 129, 64, 158, 87, 77, 157, 144, 156, 127, 74, 157, 91, 124,
128, 95, 118, 127, 111, 67, 108, 139, 79, 95, 86, 155, 120, 112, 76, 116,
79, 100, 80, 120, 117, 93, 111, 67, 55, 113, 105, 119, 171, 128, 72, 133,
60, 86, 97, 151, 77, 75, 97, 80, 133, 67, 65, 86, 85, 157, 128, 102, 63,
125, 69, 53, 135, 109, 127, 109, 125, 80, 68, 120, 75, 79, 86, 100, 89, 58,
80, 33, 118, 51, 66, 101, 77, 146, 61, 108, 98, 64, 115, 94, 123, 124, 164,
140
]
weights = [
15, 11, 12, 16, 15, 7, 12, 9, 9, 11, 10, 14, 12, 10, 11, 11, 14, 9, 10, 7,
2, 11, 12, 7, 16, 5, 10, 9, 14, 14, 10, 11, 7, 4, 8, 10, 13, 13, 8, 9, 6, 5,
4, 15, 8, 8, 6, 12, 5, 9, 7, 11, 8, 6, 9, 11, 10, 10, 8, 8, 7, 8, 7, 4, 10,
8, 5, 11, 7, 10, 12, 10, 13, 6, 11, 7, 7, 8, 9, 10, 6, 12, 11, 5, 14, 15, 13,
9, 6, 13, 8, 13, 10, 12, 11, 12, 10, 15, 10, 11
]
knapsack_capacity = 500
max_value, selected_items = knapsack(values, weights, knapsack_capacity)
print(f"Maximum value: {max_value}")
print("Selected items:")
for i in selected_items:
print(f"Item {i + 1} (Value: {values[i]}, Weight: {weights[i]})")
Running this code will provide you with the maximum value that can be obtained and the list of selected items. Please be patient, as it may take some time to execute.
This time, instead of directly solving the problem and giving me the answer, it gave me some Python code to run. The code works well in solving this problem.
This is my first attempt to understand ChatGPT’s ability to solve complex math problems such as a classic OR problem — knapsack problem. It seems that for small instances of knapsack problems, it’s able to give an answer of the optimal solution. However, the quality of the answer is not always guaranteed. There may be errors during the reasoning process or in the final answer. For large instances, ChatGPT tends to avoid giving a direct answer of the optimal solution, but instead gives a piece of code to run. The code is usually nicely written and gets us the correct solution. So when solving knapsack problems with ChatGPT, never rely too much on the direct answer of optimal solution given by it, but run the code given by it instead to double check.
This post originally appeared on TechToday.