Linear programming (linprog) in SciPy - Practice Problems & Coding Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of a simple linear programming problem

What is the output of the following code that solves a linear programming problem?

SciPy

from scipy.optimize import linprog

c = [-1, -2]
A = [[2, 1], [1, 1]]
b = [20, 16]

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

A [5. 5.]

B [10. 0.]

C [8. 8.]

D [0. 16.]

💡 Hint

Think about maximizing the objective by minimizing the negative coefficients under the constraints.

The linear program minimizes -x - 2y subject to 2x + y ≤ 20 and x + y ≤ 16. The optimal solution is x=0, y=16.

❓ data_output

intermediate

Number of iterations in linprog solution

How many iterations does the solver take to solve this linear programming problem?

SciPy

from scipy.optimize import linprog

c = [3, 1]
A = [[1, 2], [4, 0]]
b = [8, 16]

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

A 0

B 2

C 3

D 1

💡 Hint

Check the solver's iteration count attribute after solving.

The 'highs' method often solves small problems in zero iterations because it uses advanced presolve techniques.

🔧 Debug

advanced

Identify the error in linear programming code

What error will this code raise when executed?

SciPy

from scipy.optimize import linprog

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

result = linprog(c, A_eq=A, b_eq=b, method='highs')
print(result.success)

A No error, prints False

B ValueError: A_eq and b_eq dimensions mismatch

C LinAlgError: Singular matrix

D TypeError: unsupported operand type(s)

💡 Hint

Check if the dimensions of A_eq and b_eq match and if the problem is feasible.

The dimensions of A_eq (2x2) and b_eq (length 2) match, but the problem is infeasible because the equality constraints require negative values for the variables (x=-4, y=-3), which violate the default bounds x >= 0, y >= 0, so no error occurs and success is False.

🚀 Application

advanced

Interpreting linprog results for resource allocation

A factory produces two products with profits $5 and $3 per unit. It has 40 hours of labor and 30 units of raw material. Labor and material requirements per product are:

• Product 1: 2 hours labor, 1 unit material
• Product 2: 1 hour labor, 2 units material

Using linprog, what is the maximum profit?

SciPy

from scipy.optimize import linprog

c = [-5, -3]
A = [[2, 1], [1, 2]]
b = [40, 30]

result = linprog(c, A_ub=A, b_ub=b, method='highs')
print(round(-result.fun, 2))

A 80.0

B 75.0

C 103.33

D 105.0

💡 Hint

Remember to negate the objective function value to get maximum profit.

The optimal production mix yields a maximum profit of $103.33 by solving the constraints and maximizing profit.

🧠 Conceptual

expert

Understanding linprog infeasibility output

What does the linprog result indicate if result.success is False and result.status is 2?

A The problem is unbounded; objective can decrease indefinitely.

B The problem is infeasible; no solution satisfies all constraints.

C The solver encountered a numerical error during optimization.

D The problem has multiple optimal solutions.

💡 Hint

Check the meaning of status codes in linprog documentation.

Status code 2 means the problem is infeasible, so no solution meets all constraints.

Practice

1. What is the main purpose of the linprog function in scipy.optimize?

easy

A. To find the best solution for a problem with linear constraints and objective

B. To perform nonlinear regression analysis

C. To generate random linear equations

D. To plot linear graphs

Solution

1. Step 1: Understand the purpose of linear programming

   Linear programming is used to find the best (optimal) solution under given linear constraints and objectives.

2. Step 2: Identify what linprog does

   The linprog function in scipy.optimize solves linear programming problems by minimizing a linear objective function subject to linear constraints.

3. Final Answer:

   To find the best solution for a problem with linear constraints and objective -> Option A

4. Quick Check:

   Purpose of linprog = find best solution [OK]

Hint: Remember: linprog solves linear optimization problems [OK]

Common Mistakes:

• Confusing linprog with plotting functions
• Thinking linprog handles nonlinear problems
• Assuming linprog generates random data

2. Which of the following is the correct way to import the linprog function from scipy.optimize?

easy

A. import scipy.optimize.linprog

B. import linprog from scipy.optimize

C. from scipy import linprog.optimize

D. from scipy.optimize import linprog

Solution

1. Step 1: Recall Python import syntax

   To import a specific function from a module, use from module import function.

2. Step 2: Apply to linprog in scipy.optimize

   The correct syntax is from scipy.optimize import linprog.

3. Final Answer:

   from scipy.optimize import linprog -> Option D

4. Quick Check:

   Correct import syntax = from scipy.optimize import linprog [OK]

Hint: Use 'from module import function' to import specific functions [OK]

Common Mistakes:

• Using 'import linprog from ...' which is invalid syntax
• Trying to import submodules as functions
• Using dot notation incorrectly in import statements

3. What will be the output of the following code snippet?

from scipy.optimize import linprog
c = [-1, -2]
A = [[2, 1], [1, 1]]
b = [20, 16]
res = linprog(c, A_ub=A, b_ub=b)
print(res.x.round(2))

medium

A. [0. 0.]

B. [10. 0.]

C. [8. 8.]

D. [0. 16.]

Solution

1. Step 1: Understand the problem setup

   The objective is to minimize -1*x1 - 2*x2, which is equivalent to maximizing x1 + 2*x2, with constraints 2*x1 + x2 <= 20 and x1 + x2 <= 16.

2. Step 2: Solve constraints to find feasible maximum

   The feasible region vertices include (10,0), which maximizes the objective (x1 + 2*x2 = 10) and satisfies both constraints (2*10 + 0 = 20 <= 20, 10 + 0 = 10 <= 16). Thus res.x.round(2) prints [10. 0.].

3. Final Answer:

   [10. 0.] -> Option B

4. Quick Check:

   Optimal solution = [10, 0] [OK]

Hint: Remember: linprog minimizes; negate objective to maximize [OK]

Common Mistakes:

• Forgetting linprog minimizes, not maximizes
• Mixing up constraint inequalities
• Ignoring variable bounds defaulting to non-negative

4. Identify the error in this code snippet that uses linprog:

from scipy.optimize import linprog
c = [1, 2]
A = [[-1, 1], [3, 4]]
b = [1, 12]
res = linprog(c, A_eq=A, b_eq=b)
print(res.success)

medium

A. Objective coefficients should be negative to minimize

B. Missing variable bounds argument

C. Using A_eq with inequality constraints instead of A_ub

D. Incorrect import statement

Solution

1. Step 1: Check constraint type usage

   The code uses A_eq and b_eq, which define equality constraints, but the constraints given are inequalities (e.g., -1*x1 + x2 <= 1).

2. Step 2: Correct constraint parameter

   For inequality constraints, A_ub and b_ub should be used instead of A_eq and b_eq.

3. Final Answer:

   Using A_eq with inequality constraints instead of A_ub -> Option C

4. Quick Check:

   Use A_ub for inequalities, A_eq for equalities [OK]

Hint: Use A_ub for inequalities, A_eq for equalities [OK]

Common Mistakes:

• Confusing equality and inequality constraint parameters
• Assuming linprog automatically detects constraint types
• Ignoring error messages about constraint shapes

5. You want to minimize the cost function 3x + 4y subject to constraints:
- x + 2y ≥ 8
- 3x + y ≤ 15
- x, y ≥ 0
Which is the correct way to set up the linprog call in Python?

hard

A. c = [3, 4]; A_ub = [[-1, -2], [-3, -1]]; b_ub = [-8, -15]; res = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=[(0, None), (0, None)])

B. c = [3, 4]; A_ub = [[1, 2], [3, 1]]; b_ub = [8, 15]; res = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=(0, None))

C. c = [3, 4]; A_ub = [[-1, -2], [3, 1]]; b_ub = [-8, 15]; res = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=(0, None))

D. c = [3, 4]; A_ub = [[1, 2], [-3, -1]]; b_ub = [8, -15]; res = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=[(0, None), (0, None)])

Solution

1. Step 1: Convert constraints to ≤ form for linprog

   linprog requires constraints as A_ub * x ≤ b_ub. The first constraint x + 2y ≥ 8 can be rewritten as -x - 2y ≤ -8. The second constraint 3x + y ≤ 15 stays as is.

2. Step 2: Set up matrices and bounds correctly

   So A_ub = [[-1, -2], [-3, -1]], b_ub = [-8, -15]. Bounds for x and y are (0, None) each, so use bounds=[(0, None), (0, None)].

3. Step 3: Match options to correct setup

   c = [3, 4]; A_ub = [[-1, -2], [-3, -1]]; b_ub = [-8, -15]; res = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=[(0, None), (0, None)]) matches this setup exactly.

4. Final Answer:

   c = [3, 4]; A_ub = [[-1, -2], [-3, -1]]; b_ub = [-8, -15]; res = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=[(0, None), (0, None)]) -> Option A

5. Quick Check:

   Rewrite ≥ as negative ≤ and set bounds as list of tuples [OK]

Hint: Rewrite ≥ constraints as negative ≤ for linprog [OK]

Common Mistakes:

• Not converting ≥ constraints to ≤ form
• Using single tuple for bounds instead of list of tuples
• Mixing signs in constraint matrices