Integer programming and the knapsack problem

An integer program is a linear program in which some or all of the variables must be whole numbers. You cannot hire half a driver or bake 1.5 cakes to sell, so many real problems are of this kind.

They look like small changes and they are much harder to solve. You will see why rounding the easy answer fails.

The bakery plan from lesson 3 is 5 loaf batches and 1.5 cake batches. If a batch cannot be split, that plan is not allowed.

The model without the whole-number rule is called the relaxation. Its best answer is always at least as good as the best whole-number answer.

The easy idea is to round 1.5 to a whole number. Rounding up gives 5 and 2, which needs 9 oven hours and breaks the limit. Rounding down gives 5 and 1, which is feasible but earns only 130 pounds.

The best whole plan is 4 and 2, which earns 140. It is not close to the rounded answer.

docker exec jupyter python3 -c "print(20 * 5 + 30 * 1, 20 * 4 + 30 * 2, 20 * 5 + 30 * 1.5)"

docker exec jupyter python3 -c "from scipy.optimize import linprog; r = linprog([-20, -30], A_ub=[[1, 2], [3, 2]], b_ub=[8, 18], integrality=[1, 1]); print(-r.fun, r.x)"

The argument integrality has one number for each variable, and 1 means whole. The command printed 140.0 [4. 2.], the best whole plan that the table found by hand.

The solver does this by solving relaxations again and again. That is why integer problems can take far longer than ordinary ones.

A courier van can carry 5 kg. Parcel 1 weighs 2 kg and pays 3 pounds. Parcel 2 weighs 3 kg and pays 4. Parcel 3 weighs 4 kg and pays 5. Each parcel is taken whole or left behind.

This is the knapsack problem: the most value that fits. Taking parcels 1 and 2 pays 7. Parcel 3 alone pays only 5.

List the best value for every amount of room, from 0 kg up to 5 kg. Start with no parcels. Then add one parcel at a time, and ask whether taking it beats the earlier best for that room.

Each step reuses the answers of smaller rooms. This is dynamic programming.

weights = [2, 3, 4]
values = [3, 4, 5]
capacity = 5

# best[room] is the largest value that fits in that much room.
best = [0] * (capacity + 1)

for parcel in range(len(weights)):
    for room in range(capacity, weights[parcel] - 1, -1):
        with_parcel = best[room - weights[parcel]] + values[parcel]
        if with_parcel > best[room]:
            best[room] = with_parcel

print(best)
print(best[capacity])
# Change capacity to 6. Work out the answer by hand first.

Each parcel is taken or left. So 30 parcels give 2 to the power of 30 choices, and 40 parcels give 2 to the power of 40. Brute force cannot keep up.

Dynamic programming needs only parcels times room steps, but the room can itself be a huge number. In general, whole-number problems have no known fast method for every case.

docker exec jupyter python3 -c "print(2 ** 30, 2 ** 40)"

Change the code so the van carries 6 kg, and check the answer against a list of every choice of parcels. Then add a fourth parcel of your own.

Say why the best whole plan for the bakery is not the nearest whole plan to the relaxation.