Integer programming in SciPy - Practice Problems & Coding Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of integer programming solution with scipy.optimize

What is the output of the following code that solves a simple integer programming problem using scipy.optimize.linprog with integer constraints simulated?

SciPy

from scipy.optimize import linprog

# Objective: minimize x + 2y
c = [1, 2]

# Constraints:
# x + y >= 3  -> -x - y <= -3
# x >= 0, y >= 0
A = [[-1, -1]]
b = [-3]

# Bounds for variables (integers simulated by rounding)
bounds = [(0, None), (0, None)]

res = linprog(c, A_ub=A, b_ub=b, bounds=bounds, method='highs')

# Round solution to integers
x_int, y_int = map(round, res.x)

print((x_int, y_int))

A (0, 3)

B (3, 0)

C (2, 1)

D (1, 2)

💡 Hint

Think about the minimum values of x and y that satisfy x + y >= 3 and minimize x + 2y.

The linear program minimizes x + 2y subject to x + y >= 3 and x,y >= 0. The minimal solution before rounding is (3, 0). Rounding keeps it (3, 0).

❓ data_output

intermediate

Number of feasible integer solutions in a bounded problem

Given the integer constraints 0 <= x <= 3 and 0 <= y <= 3 with the linear inequality x + 2y <= 5, how many integer pairs (x, y) satisfy these constraints?

SciPy

count = 0
for x in range(4):
    for y in range(4):
        if x + 2*y <= 5:
            count += 1
print(count)

A 10

B 12

C 9

D 11

💡 Hint

Try counting all pairs (x,y) with x and y from 0 to 3 that satisfy x + 2y <= 5.

Counting all integer pairs (x,y) with 0 <= x,y <= 3 and x + 2y <= 5 yields 10 valid pairs.

🔧 Debug

advanced

Identify the error in integer programming code using scipy.optimize

What error does the following code produce when trying to solve an integer programming problem with scipy.optimize.linprog?

SciPy

from scipy.optimize import linprog

c = [1, 1]
A = [[1, 1]]
b = [5]
bounds = [(0, None), (0, None)]

res = linprog(c, A_eq=A, b_eq=b, bounds=bounds, method='highs')

x_int, y_int = map(round, res.x)
print(x_int, y_int)

A TypeError: 'A_eq' must be 2-D array

B ValueError: Infeasible problem

C AttributeError: 'OptimizeResult' object has no attribute 'x'

D No error, prints '5 0'

💡 Hint

Check if the equality constraint x + y = 5 is feasible with the objective and bounds.

The code runs without error. The problem is feasible (x + y = 5, x,y >= 0), and the solver finds a solution like (5, 0) or (0, 5), which rounds to integers.

🧠 Conceptual

advanced

Understanding integer programming constraints

Which statement correctly describes the difference between linear programming and integer programming?

A Integer programming requires all variables to be integers, linear programming allows continuous variables.

B Both require variables to be integers but differ in objective function type.

C Linear programming requires integer variables, integer programming allows continuous variables.

D Integer programming solves problems faster than linear programming.

💡 Hint

Think about the variable types allowed in each programming type.

Integer programming restricts variables to integer values, while linear programming allows variables to take any real values within bounds.

🚀 Application

expert

Optimal integer solution for a knapsack problem

Given items with weights [2, 3, 4] and values [3, 4, 5], and a knapsack capacity of 5, which integer vector x (0 or 1 for each item) maximizes total value without exceeding capacity?

SciPy

import numpy as np
from scipy.optimize import linprog

weights = np.array([2, 3, 4])
values = np.array([3, 4, 5])
capacity = 5

# Objective: maximize values, so minimize negative values
c = -values

# Constraints: weights * x <= capacity
A_ub = [weights]
b_ub = [capacity]

# Bounds: x in {0,1} but linprog does not support integer constraints
bounds = [(0, 1) for _ in weights]

res = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=bounds, method='highs')

# Round solution to nearest integer
x_int = tuple(map(round, res.x))
print(x_int)

A (1, 0, 1)

B (0, 1, 1)

C (1, 1, 0)

D (0, 0, 1)

💡 Hint

Try combinations of items that fit in capacity 5 and maximize value.

Items 1 and 2 (weights 2 and 3) fit exactly in capacity 5 with total value 7, which is higher than other combinations.