Linear programming (linprog) in SciPy - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main goal of linear programming?

Linear programming aims to find the best value (maximum or minimum) of a linear function, called the objective, while following certain linear constraints.

beginner

In scipy's linprog, what does the 'c' parameter represent?

The 'c' parameter is a list or array of coefficients for the objective function that we want to minimize.

intermediate

What types of constraints can you specify in linprog?

You can specify inequality constraints (A_ub x ≤ b_ub) and equality constraints (A_eq x = b_eq) in linprog.

beginner

What does the result of linprog contain?

The result includes the optimal values for variables, the minimum value of the objective function, and a success flag indicating if the solution was found.

intermediate

Why do we often minimize the objective function in linprog instead of maximizing?

linprog is designed to minimize by default. To maximize, we multiply the objective coefficients by -1 and then minimize.

What does the 'linprog' function in scipy.optimize do?

A Generates random linear equations

B Solves linear programming problems to minimize a linear objective function

C Calculates eigenvalues of a matrix

D Performs linear regression on data

linprog is used to find the minimum of a linear objective function subject to linear constraints.

In linprog, which parameter represents the inequality constraint matrix?

A A_ub

B b

C A

D c

A_ub is the matrix for inequality constraints of the form A_ub x ≤ b_ub.

How do you represent the constraint x1 + 2x2 ≤ 4 in linprog?

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

B A_eq = [[1, 2]], b_eq = [4]

C A_ub = [[1, 2]], b_ub = [4]

D A_ub = [[4]], b_ub = [1, 2]

Inequality constraints use A_ub and b_ub where A_ub x ≤ b_ub.

If you want to maximize 3x + 4y using linprog, what should you do?

A Use c = [-3, -4] to minimize the negative

B Set maximize=True in linprog

C Use c = [3, 4] directly

D Use equality constraints instead

linprog minimizes by default, so multiply coefficients by -1 to maximize.

What does the 'success' attribute in linprog's result indicate?

A If constraints are all equalities

B If the input data was valid

C If the objective function is linear

D If the optimization found a solution

The 'success' flag tells if linprog found an optimal solution.

Explain how to set up a linear programming problem using scipy's linprog.

Think about what you want to minimize and the rules your variables must follow.

Describe how to convert a maximization problem into a minimization problem for linprog.

Remember linprog only minimizes by default.

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