Why Integer programming in SciPy? - Purpose & Use Cases

The Big Idea

What if a computer could instantly find the best plan when your choices are too many to count?

The Scenario

Imagine you are trying to plan a delivery route for trucks that must visit several cities exactly once. You try to list all possible routes by hand to find the shortest one.

The Problem

Listing every possible route manually is overwhelming and takes forever. It's easy to make mistakes, and you can't realistically check all options when there are many cities.

The Solution

Integer programming lets you describe the problem with rules and goals, then a computer quickly finds the best solution without checking every possibility.

Before vs After

✗ Before

routes = [all possible permutations of cities]
best_route = min(routes, key=distance)

✓ After

from scipy.optimize import milp
# define variables, constraints, and objective
result = milp(c, A_ub=A_ub, b_ub=b_ub, integrality=1)

What It Enables

It enables solving complex decision problems with yes/no choices quickly and accurately, even when options are huge.

Real Life Example

Companies use integer programming to schedule workers, assign tasks, or plan routes that save time and money.

Key Takeaways

Manual trial of all options is slow and error-prone.

Integer programming models problems with clear rules and finds best solutions fast.

This approach helps solve real-world planning and scheduling challenges efficiently.

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