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.

Practice

1.

What is the main purpose of integer programming in scipy?

easy

A. To perform statistical hypothesis testing

B. To solve differential equations numerically

C. To find the best solution where some variables must be whole numbers

D. To visualize data with plots

Solution

1. Step 1: Understand integer programming concept

   Integer programming is used to find optimal solutions where some or all variables are restricted to integers (whole numbers).

2. Step 2: Match with scipy usage

   In scipy, integer programming helps solve optimization problems with integer constraints, unlike other tasks like plotting or statistics.

3. Final Answer:

   To find the best solution where some variables must be whole numbers -> Option C

4. Quick Check:

   Integer programming = whole number solutions [OK]

Hint: Integer programming means variables are whole numbers [OK]

Common Mistakes:

• Confusing integer programming with plotting or statistics
• Thinking it solves differential equations
• Assuming variables can be fractional

2.

Which of the following is the correct way to specify integer variables in scipy.optimize.linprog?

from scipy.optimize import linprog

result = linprog(c, A_ub=A, b_ub=b, integrality=...)

easy

A. integrality=True # boolean for all integer

B. integrality=[1, 0, 1] # 1 means integer, 0 means continuous

C. integrality='integer' # string to specify all integer

D. integrality=None # default no integer constraints

Solution

1. Step 1: Recall integrality parameter usage

   The integrality argument takes a list or array indicating which variables are integers (1) or continuous (0).

2. Step 2: Check options

   integrality=[1, 0, 1] # 1 means integer, 0 means continuous correctly uses a list with 1s and 0s. Options A, B, and D use incorrect types.

3. Final Answer:

   integrality=[1, 0, 1] # 1 means integer, 0 means continuous -> Option B

4. Quick Check:

   integrality list = integer flags [OK]

Hint: Use list of 1/0 to mark integer variables [OK]

Common Mistakes:

• Passing a string or boolean instead of list
• Leaving integrality as None to expect integers
• Confusing integrality with other parameters

3.

What will be the output of this code snippet?

from scipy.optimize import linprog

c = [-1, -2]
A = [[1, 1]]
b = [3]
integrality = [1, 1]

result = linprog(c, A_ub=A, b_ub=b, integrality=integrality, method='highs')
print(result.x.round())

medium

A. [1. 1.]

B. [1. 2.]

C. [3. 0.]

D. [0. 3.]

Solution

1. Step 1: Understand the problem setup

   The objective is to minimize -x - 2y, which is equivalent to maximizing x + 2y, with constraint x + y ≤ 3 and both x,y integers.

2. Step 2: Find integer values maximizing x + 2y under constraint

   Feasible integer points include (0,3): x+2y=6, (1,2):5, (2,1):4, (3,0):3. Maximum at (0,3), so result.x.round() prints [0. 3.].

3. Final Answer:

   [0. 3.] -> Option D

4. Quick Check:

   Max x+2y with x+y≤3 integer = [0,3] [OK]

Hint: Maximize by checking integer combos under constraints [OK]

Common Mistakes:

• Picking suboptimal integer point like [1,2]
• Misunderstanding objective sign for maximization
• Ignoring non-negativity bounds

4.

Identify the error in this integer programming code using scipy.optimize.linprog:

from scipy.optimize import linprog

c = [1, 1]
A = [[-1, 2]]
b = [4]
integrality = [1, 1]

result = linprog(c, A_ub=A, b_ub=b, integrality=integrality)
print(result.x)

medium

A. No error; code runs correctly

B. Missing method='highs' argument causes solver failure

C. Constraint matrix A has wrong sign for inequality

D. integrality must be a boolean, not a list

Solution

1. Step 1: Check linprog default solver compatibility

   In recent SciPy, the default method is 'highs', which supports integrality for integer programming.

2. Step 2: Identify if any error exists

   integrality=[1,1] is correct format. Parameters c, A_ub, b_ub are valid. No syntax or runtime errors; code runs.

3. Final Answer:

   No error; code runs correctly -> Option A

4. Quick Check:

   Default method='highs' supports integrality [OK]

Hint: Default method='highs' supports integer constraints [OK]

Common Mistakes:

• Assuming default solver lacks integer support
• Passing integrality as boolean instead of list
• Misinterpreting constraint matrix

5.

You want to solve an integer programming problem to maximize profit with variables x and y, where x + 2y ≤ 8, x ≥ 0, y ≥ 0, and both x and y must be integers. Which scipy.optimize.linprog call correctly models this problem?

hard

A. c = [-1, -2]
A = [[1, 2]]
b = [8]
integrality = [1, 1]
linprog(c, A_ub=A, b_ub=b, bounds=[(0, None), (0, None)], integrality=integrality, method='highs')

B. c = [1, 2]
A = [[1, 2]]
b = [8]
integrality = [1, 1]
linprog(c, A_ub=A, b_ub=b, bounds=[(0, None), (0, None)], integrality=integrality, method='highs')

C. c = [-1, -2]
A = [[-1, -2]]
b = [-8]
integrality = [1, 1]
linprog(c, A_ub=A, b_ub=b, bounds=[(0, None), (0, None)], integrality=integrality, method='highs')

D. c = [-1, -2]
A = [[1, 2]]
b = [8]
integrality = [0, 0]
linprog(c, A_ub=A, b_ub=b, bounds=[(0, None), (0, None)], method='highs')

Solution

1. Step 1: Translate maximization to minimization

   Maximize profit = x + 2y is same as minimize -x - 2y, so c = [-1, -2].

2. Step 2: Set constraints and integrality

   Constraint x + 2y ≤ 8 is A = [[1, 2]], b = [8]. Variables are non-negative with bounds (0, None). Both x and y are integers, so integrality = [1, 1].

3. Step 3: Confirm method and parameters

   Use method='highs' to support integer programming.

4. Final Answer:

   The code with c = [-1, -2], A = [[1, 2]], integrality = [1, 1], method='highs' -> Option A

5. Quick Check:

   Maximize -> minimize negative, integrality=1 for integers [OK]

Hint: Maximize by minimizing negative objective with integer flags [OK]

Common Mistakes:

• Using positive c vector for maximization
• Incorrect sign or values in constraints
• Not setting integrality for integer variables
• Omitting method='highs' for integer programming