Mastering Optimization with Python/

...

/

Solutions

Solutions

Solve the exercises about linear and integer programming.

We'll cover the following...

Exercise 1: Fractional knapsack

In the fractional knapsack problem, we don’t have to choose the entire item, but we can get a part of it. That way, we aren’t solving an integer problem anymore. The constraints are the same, but the solution is different from the original knapsack problem. In the original version, a solution is a zero or a one for each item, representing whether we take the item or not. Now a solution is a number between zero and one for each item, representing the fraction of that item we take. So the problem can be written as follows:

max⁡xvx⊤s.t.:wx⊤≤w0≤xi≤1\max_{\mathbf{x}} \mathbf{v}\mathbf{x}^\top\\ s.t.: \mathbf{w}\mathbf{x}^\top \leq w\\ 0 \leq x_i \leq 1

Let’s see the code:

Python 3.10.4
from scipy.optimize import linprog
import numpy as np
N = 5
v = np.random.uniform(1, 10, size=N)
W = np.random.uniform(1, 10, size=(1,N))
w = np.random.uniform(5, 15)
# all variables should be between 0 and 1
bounds = [(0, 1) for _ in range(N)]
# this solves a minimization problem so we use -v
sol = linprog(-v, A_ub = W, b_ub=[w], bounds=bounds)
print("Number of objects:", N)
print("Max weight:", w)
print("Weights:", W)
print("Values :", v)
print("Success:", sol.success)
print("Solution:", sol.x)
print("Target func:", -sol.fun)

Let’s break down the most essential details of this code:

  • Line 10: Function linprog receives another parameter bounds containing the bounds of each variable. This should be a sequence of tuples of the form (a,b)(a, b), where aa is the lower bound and bb is the upper bound. As we have the constraint 0≤xi≤10 \leq x_i \leq 1, we add the tuples (0,1)(0, 1) for each item.

  • Line 13: We call linprog with the vector -v since linprog solves a minimization problem and we’re maximizing. Remember the parameter b_ub is expected to be a 1D array, so we need to wrap the limit weight ww inside an array. The parameter bounds is a sequence of tuples, as explained above.

  • Line 17: To get the value of the target function in the solution, we need to multiply by -1 again since we solved the equivalent minimization problem.

Exercise 2: Product mix problem

If we take v\mathbf{v} as the selling price vector and m\mathbf{m} as the total amount of each material, then we can write the mix problem as follows:

max⁡xvx⊤s.t.:Mx⊤≤m\max_{\mathbf{x}}\mathbf{v}\mathbf{x}^\top\\ s.t.: M\mathbf{x}^\top \leq \mathbf{m} ...