Solving Integer Problems with CVXPY

We already know how to define an integer problem mathematically. In this lesson, we’ll solve an integer problem using cvxpy. Let’s find out what the problem is about.

The knapsack problem

The salesman is moving from one city to another. Unfortunately, he can’t carry all his possessions. He has a knapsack that can carry up to $w$ kilograms, so he can’t load more than that weight. The salesman has a list of all the items he has with the weight and value of each item. He has to try to decide what items to carry with him, so he gets the maximum possible value without exceeding the weight that the knapsack can load.

As always, we first analyze what a solution to this problem looks like. We want to determine what items he should pack to maximize the total value. So a solution to the problem is a “yes” or “no” for each possible item. If there are $N$ items, then we can represent this as a vector with values of zero or one for each object. Zero represents “no” (don’t take this item) and one represents “yes” (take this item).

The total value of a solution will be the value of each item multiplied by the decision of taking or not taking the item, and the total weight will be the weight multiplied by the decision. Let’s see an example.

Suppose we have three items. The value of each item is $\mathbf{v} = (3, 5, 2)$ ...