Solving operations research (OR) problems with ChatGPT

Ever for the reason that emergence of ChatGPT, I’ve been serious about how ChatGPT would influence the world of optimization and Operations Research (OR). There was news about ChatGPT passing highschool and undergraduate level math exams, which piques my interest in exploring how well it may do on solving OR problems. In this text, I’ll use a classic OR problem — 0/1 knapsack problem to run some tests.

Within the realm of optimization and decision-making conundrums, the knapsack problem has long been a classic benchmark. It challenges us to pick a mixture of things, each with its own weight and value, in such a way that we maximize the full value while staying inside a given weight constraint. Dynamic programming is an efficient algorithm we genrally use to resolve 0/1 knapsack problems.

I began with a really small example, and asked ChatGPT to resolve it.

Me: Consider a knapsack problem, where the capability of the knapsack is 10lbs. I actually have 4 items to pick from, whose values are $10, $40, $30, $50 and weights are 5lbs, 4lbs, 6lbs, 3lbs respectively. Could you solve this problem for me?

ChatGPT: Actually! The knapsack problem is a classic optimization problem where the goal is to maximise the full value of things chosen for a knapsack, subject to the constraint that the full weight of the chosen items doesn’t exceed the knapsack’s capability.

In your case, you could 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 Capability = 10lbs

To unravel this problem, you need to 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 within the table iteratively to search out the utmost value that could be obtained for every combination of things and remaining capacities.

Here’s the table filling process:

Capability (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 utmost value that could be obtained for every combination of things and remaining capacities. The ultimate cell (bottom-right) has a worth of $80, which is the utmost value that could be obtained with a knapsack capability of 10lbs.

To search out the items that needs to be chosen, you may backtrack from the last cell to the primary cell while considering the selections that led to the utmost value. On this case, you would choose Item 2 and Item 4, which have a complete value of $40 + $50 = $90 and a complete weight of 4lbs + 3lbs = 7lbs, which is throughout the knapsack’s capability of 10lbs.

So, the optimal solution is to pick Item 2 and Item 4, which supplies you a complete value of $90.

Apparently, we notice that ChatGPT is capable of pick the fitting approach to resolve this problem, but the ultimate solution given by ChatGPT just isn’t aligned with its reasoning process. Specifically, the dynamic programming (DP) table shows $80 (bottom right cell) because the optimal objective value, but ChatGPT concluded $90 is the ultimate answer.

To ascertain which is the proper solution, I wrote up a chunk of Python script as below to perform 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, however the the DP table given by ChatGPT is mistaken. Then I continued to ask it to correct the DP table.

Me: I feel your solution is correct, however 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:

Capability (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 worth within the bottom-right cell is $90, which represents the utmost value that could be obtained with a knapsack capability of 10lbs. As mentioned before, the optimal solution is to pick Item 2 and Item 4, which supplies you a complete value of $90.

Interestingly, ChatGPT is capable of do some corrections to the table, in order that the underside right cell is aligned with $90. Nonetheless, if we have a look at the table more closely, the last row of the table continues to be not correct. The cell in 4th row and seventh column (corresponding to a knapsack capability of 6lbs) needs to be $50 as a substitute of $90. A knapsack of 6lbs capability wouldn’t allow us to decide on item 2 and 4 to achieve $90, since the full weight of item 2 and 4 is 7lbs which exceeds the capability of the knapsack.

I then asked it to put in writing some code to resolve this problem.

Me: Could you write Python code to resolve this problem?

ChatGPT: Actually! You possibly can solve the 0/1 knapsack problem using dynamic programming in Python. Here’s a Python code snippet to resolve the issue for the precise instance you provided:

def knapsack(values, weights, capability):
n = len(values)
# Initialize a table to store the utmost values for various capacities
dp = [[0] * (capability + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capability + 1):
# If the present item's weight is greater than the present capability, skip it
if weights[i - 1] > w:
dp[i][w] = dp[i - 1][w]
else:
# Select the utmost between including and excluding the present item
dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
# Backtrack to search out the chosen items
selected_items = []
i, w = n, capability
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("Chosen items:")
for i in selected_items:
print(f"Item {i + 1} (Value: ${values[i]}, Weight: {weights[i]} lbs)")

Once you run this code, it should output the utmost value and the chosen items that needs to be placed within the knapsack. In your specific case, it should appropriately select Item 2 and Item 4, which have a complete value of $90 and a complete weight of seven lbs, throughout the knapsack’s capability of 10 lbs.

This code printed out the optimal solution clearly and appropriately. The DP table calculated by this code can be correct.

I then went further to check an instance of a bigger scale, a knapsack problem with the capability of the knapsack being 500lbs and 10 items to pick from. The worth and weight of every 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 resolve it.

Me: Consider a knapsack problem, where the capability of the knapsack is 500lbs. I actually have 100 items to pick 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 capability of 500 lbs is a computationally intensive task. Nonetheless, I can offer you the Python code to resolve this problem using dynamic programming, but please bear in mind that it could take a while to run.

Here’s the Python code to resolve the knapsack problem with the provided values and weights:

def knapsack(values, weights, capability):
n = len(values)
dp = [[0] * (capability + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capability + 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, capability
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("Chosen items:")
for i in selected_items:
print(f"Item {i + 1} (Value: {values[i]}, Weight: {weights[i]})")

Running this code will offer you the utmost value that could be obtained and the list of chosen items. Please be patient, as it could take a while to execute.

This time, as a substitute of directly solving the issue and giving me the reply, it gave me some Python code to run. The code works well in solving this problem.

That is my first try to understand ChatGPT’s ability to resolve complex math problems comparable to a classic OR problem — knapsack problem. Plainly for small instances of knapsack problems, it’s able to present a solution of the optimal solution. Nonetheless, the standard of the reply just isn’t all the time guaranteed. There could also be errors through the reasoning process or in the ultimate answer. For big instances, ChatGPT tends to avoid giving a direct answer of the optimal solution, but as a substitute gives a chunk of code to run. The code is frequently nicely written and gets us the proper solution. So when solving knapsack problems with ChatGPT, never rely an excessive amount of on the direct answer of optimal solution given by it, but run the code given by it as a substitute to double check.