Production Planning Example with PuLP

Production Planning Example with PuLP

Let’s consider a simple Production Planning problem for a factory that produces two products: Product A and Product B.

The factory has limited resources: labor hours and raw material.

The goal is to maximize the profit while respecting the constraints of available resources.

Problem Statement:

  • Product A requires:
    • $2$ labor hours per unit
    • $3$ kg of raw material per unit
    • Yields a profit of $30 per unit
  • Product B requires:
    • $3$ labor hours per unit
    • $1$ kg of raw material per unit
    • Yields a profit of $20 per unit

The factory has:

  • $100$ labor hours available per week
  • $90$ kg of raw material available per week

The factory needs to decide how many units of each product to produce to maximize profit, given the constraints.

Mathematical Model:

Let:

  • $(x_1)$ = number of units of Product A produced
  • $(x_2)$ = number of units of Product B produced

Objective:
$$
\text{Maximize } 30x_1 + 20x_2
$$
Subject to:
$$
2x_1 + 3x_2 \leq 100 \quad \text{(labor hours constraint)}
$$
$$
3x_1 + 1x_2 \leq 90 \quad \text{(raw material constraint)}
$$
$$
x_1 \geq 0, \quad x_2 \geq 0 \quad \text{(non-negativity constraint)}
$$

Solution using PuLP:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import pulp

# Define the problem
problem = pulp.LpProblem("Production_Planning", pulp.LpMaximize)

# Decision variables
x1 = pulp.LpVariable('x1', lowBound=0, cat='Continuous')  # Units of Product A
x2 = pulp.LpVariable('x2', lowBound=0, cat='Continuous')  # Units of Product B

# Objective function
problem += 30 * x1 + 20 * x2, "Profit"

# Constraints
problem += 2 * x1 + 3 * x2 <= 100, "Labor_hours"
problem += 3 * x1 + 1 * x2 <= 90, "Raw_material"

# Solve the problem
problem.solve()

# Output the results
print("Status:", pulp.LpStatus[problem.status])
print(f"Optimal number of Product A to produce: {x1.varValue}")
print(f"Optimal number of Product B to produce: {x2.varValue}")
print(f"Maximum Profit: ${pulp.value(problem.objective)}")

Explanation:

  • Decision variables represent the number of units of each product to be produced.
  • Objective function aims to maximize the total profit from producing both products.
  • Constraints ensure that the production doesn’t exceed the available labor hours and raw material.

Results:

1
2
3
4
Status: Optimal
Optimal number of Product A to produce: 24.285714
Optimal number of Product B to produce: 17.142857
Maximum Profit: $1071.4285599999998

Explanation of the Results:

The problem has been solved, and the solution status is “$Optimal$”, meaning the solution found satisfies all the constraints and maximizes the profit under the given conditions.

  • Optimal number of Product A to produce: $24.29$ units (rounded to two decimal places)
  • Optimal number of Product B to produce: $17.14$ units (rounded to two decimal places)

Since the solution involves fractional units (which might represent part of a batch or a continuous process in certain industries), the optimal production mix is not whole numbers.

  • Maximum Profit: $1071.43

This means that producing approximately $24.29$ units of Product A and $17.14$ units of Product B will yield the highest possible profit of $1071.43, while respecting the constraints on labor hours and raw materials.

If the production process must involve whole units, you might consider rounding these values or solving the problem using integer programming, depending on the context.

Solving the Diet Problem with PuLP

An Example of Cost-Effective Nutrition Optimization

Example: Diet Problem

The diet problem is a classic $optimization$ $problem$ that aims to find the most $cost$-$effective$ way to meet nutritional requirements using a selection of foods.

Let’s solve a simple example using the $PuLP$ library in $Python$.

Problem Statement:

You are trying to meet your daily nutritional needs using three different foods.

Each food has a $cost$ and provides a certain amount of $calories$, $protein$, and $fat$.

Your goal is to minimize the cost while ensuring that you meet the minimum daily requirements for $calories$, $protein$, and $fat$.

Data:

  • Foods: Chicken, Beef, Vegetables
  • Cost per unit:
    • Chicken: $2.50
    • Beef: $3.00
    • Vegetables: $1.00
  • Nutritional content per unit:
    • Chicken: $250$ calories, $30$g protein, $10$g fat
    • Beef: $300$ calories, $20$g protein, $20$g fat
    • Vegetables: $50$ calories, $5$g protein, $0$g fat
  • Minimum daily requirements:
    • Calories: $2000$
    • Protein: $60$g
    • Fat: $50$g

Solution using PuLP:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
import pulp

# Define the problem
prob = pulp.LpProblem("Diet_Problem", pulp.LpMinimize)

# Define the decision variables: the amount of each food to consume
food_vars = {
    "Chicken": pulp.LpVariable("Chicken", lowBound=0, cat='Continuous'),
    "Beef": pulp.LpVariable("Beef", lowBound=0, cat='Continuous'),
    "Vegetables": pulp.LpVariable("Vegetables", lowBound=0, cat='Continuous')
}

# Define the cost of each food
costs = {
    "Chicken": 2.50,
    "Beef": 3.00,
    "Vegetables": 1.00
}

# Objective function: Minimize the total cost
prob += pulp.lpSum(food_vars[food] * costs[food] for food in food_vars)

# Define the nutritional content of each food
calories = {
    "Chicken": 250,
    "Beef": 300,
    "Vegetables": 50
}

protein = {
    "Chicken": 30,
    "Beef": 20,
    "Vegetables": 5
}

fat = {
    "Chicken": 10,
    "Beef": 20,
    "Vegetables": 0
}

# Add constraints for minimum daily nutritional requirements
prob += pulp.lpSum(food_vars[food] * calories[food] for food in food_vars) >= 2000, "CaloriesRequirement"
prob += pulp.lpSum(food_vars[food] * protein[food] for food in food_vars) >= 60, "ProteinRequirement"
prob += pulp.lpSum(food_vars[food] * fat[food] for food in food_vars) >= 50, "FatRequirement"

# Solve the problem
prob.solve()

# Print the results
print("Optimal diet:")
for food in food_vars:
    print(f"{food}: {food_vars[food].varValue:.2f} units")

print(f"Total cost: ${pulp.value(prob.objective):.2f}")

Explanation:

  • Decision Variables: food_vars represent the amount of each food to consume.
  • Objective Function: Minimize the total cost of the diet.
  • Constraints: Ensure that the total intake of $calories$, $protein$, and $fat$ meets or exceeds the minimum daily requirements.

Output:

1
2
3
4
5
Optimal diet:
Chicken: 0.00 units
Beef: 6.67 units
Vegetables: 0.00 units
Total cost: $20.00

Explanation of the Result:

The optimal solution suggests that the most $cost$-$effective$ way to meet the daily nutritional requirements is to consume $6.67$ units of Beef and no units of Chicken or Vegetables.

The total cost of this diet is $20.00.

Key Points:

  1. Beef-only diet: The solution indicates that Beef alone is sufficient to meet the required minimums for calories, protein, and fat, making it the $cheapest$ option at $3.00 per unit.

  2. No Chicken or Vegetables: Since Beef provides a higher concentration of calories and fat compared to Chicken and Vegetables, the solver determined that only Beef is needed to satisfy the constraints without incurring extra costs.

  3. Total Cost: By consuming $6.67$ units of Beef, the total expenditure on this diet is minimized to $20.00.

This result demonstrates how optimization can find the most economical way to satisfy nutritional needs based on the available options.

Workforce Scheduling Optimization with PuLP

Workforce Scheduling Optimization with PuLP: Minimizing Staffing Costs

Here’s a simple Workforce Scheduling example and solution using $PuLP$ in $Python$.

Problem:

You manage a small company and need to assign workers for a week.
There are certain staffing requirements each day, and the workers have constraints on their availability.
You want to minimize the total cost while ensuring each day has enough workers.

Details:

  • You have $5$ workers available, each with a different cost per day.
  • Each worker can only work on specific days.
  • You need a minimum number of workers for each day of the week.

Data:

Worker Cost per day Available on days
Worker 1 100 Monday, Tuesday, Friday
Worker 2 150 Tuesday, Wednesday, Thursday
Worker 3 120 Monday, Wednesday, Friday
Worker 4 130 Thursday, Friday
Worker 5 110 Monday, Tuesday, Thursday
Day Required Workers
Monday 2
Tuesday 2
Wednesday 1
Thursday 2
Friday 1

Objective:

Minimize the total cost while meeting the staffing requirements for each day.

PuLP Implementation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
import pulp

# Define the problem
problem = pulp.LpProblem("Workforce_Scheduling", pulp.LpMinimize)

# Define workers, costs, and availability
workers = ["Worker1", "Worker2", "Worker3", "Worker4", "Worker5"]
costs = {"Worker1": 100, "Worker2": 150, "Worker3": 120, "Worker4": 130, "Worker5": 110}
availability = {
    "Monday": ["Worker1", "Worker3", "Worker5"],
    "Tuesday": ["Worker1", "Worker2", "Worker5"],
    "Wednesday": ["Worker2", "Worker3"],
    "Thursday": ["Worker2", "Worker4", "Worker5"],
    "Friday": ["Worker1", "Worker3", "Worker4"],
}

# Define staffing requirements
requirements = {"Monday": 2, "Tuesday": 2, "Wednesday": 1, "Thursday": 2, "Friday": 1}

# Define decision variables: worker_day[worker][day] = 1 if the worker is assigned to that day, else 0
worker_day = pulp.LpVariable.dicts("work", (workers, requirements.keys()), cat="Binary")

# Objective function: minimize total cost
problem += pulp.lpSum([costs[worker] * worker_day[worker][day] for worker in workers for day in requirements.keys()])

# Constraints: meet the daily staffing requirements
for day, required in requirements.items():
    problem += pulp.lpSum([worker_day[worker][day] for worker in availability[day]]) >= required, f"Staffing_{day}"

# Constraints: a worker can only be assigned to a day if they are available on that day
for worker in workers:
    for day in requirements.keys():
        if worker not in availability[day]:
            problem += worker_day[worker][day] == 0, f"Availability_{worker}_{day}"

# Solve the problem
problem.solve()

# Output results
print(f"Status: {pulp.LpStatus[problem.status]}")
for worker in workers:
    for day in requirements.keys():
        if worker_day[worker][day].varValue == 1:
            print(f"{worker} is assigned to {day}")

# Output total cost
print(f"Total cost: {pulp.value(problem.objective)}")

Explanation:

  • Decision Variables: worker_day[worker][day] is a binary variable that indicates if a worker is assigned to work on a particular day.
  • Objective: Minimize the total cost based on the daily costs of the workers.
  • Constraints:
    • Ensure each day has at least the required number of workers.
    • Workers can only be assigned to days they are available.

Output:

For example, the solution might look like:

1
2
3
4
5
6
7
8
9
10
Status: Optimal
Worker1 is assigned to Monday
Worker1 is assigned to Tuesday
Worker1 is assigned to Friday
Worker3 is assigned to Wednesday
Worker4 is assigned to Thursday
Worker5 is assigned to Monday
Worker5 is assigned to Tuesday
Worker5 is assigned to Thursday
Total cost: 880.0

This example shows how to use $PuLP$ to solve a simple workforce scheduling problem by minimizing cost while ensuring staffing requirements are met.

Portfolio Optimization with PuLP in Python

Portfolio Optimization with PuLP in Python

  • Problem:
    You have a budget to invest in different assets, and you want to maximize your return while keeping risk under a certain threshold.
  • PuLP Solution:
    Formulate the portfolio optimization problem where the objective is to maximize the expected return subject to risk constraints.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import pulp

# Define the assets
assets = ["Asset1", "Asset2", "Asset3"]

# Define the expected returns for each asset
returns = {
    "Asset1": 0.08,  # 8% return
    "Asset2": 0.12,  # 12% return
    "Asset3": 0.10   # 10% return
}

# Define the risk (e.g., variance) for each asset
risk = {
    "Asset1": 0.05,  # Risk for Asset 1
    "Asset2": 0.10,  # Risk for Asset 2
    "Asset3": 0.07   # Risk for Asset 3
}

# Define the budget (total amount to invest)
budget = 100000  # e.g., $100,000

# Define the maximum acceptable risk
max_risk = 0.08  # Maximum risk tolerance

# Define the problem
prob = pulp.LpProblem("Portfolio_Optimization", pulp.LpMaximize)

# Decision variables: Amount invested in each asset
investment_vars = pulp.LpVariable.dicts("Invest", assets, lowBound=0, cat='Continuous')

# Objective function: Maximize expected return
prob += pulp.lpSum(investment_vars[i] * returns[i] for i in assets)

# Constraints: Budget constraint
prob += pulp.lpSum(investment_vars[i] for i in assets) <= budget

# Constraints: Risk constraint (variance)
prob += pulp.lpSum(investment_vars[i] * risk[i] for i in assets) <= max_risk * budget

# Solve the problem
prob.solve()

# Print the results
for i in assets:
    print(f"Invest in {i}: ${investment_vars[i].varValue:.2f}")

Explanation:

  • assets is a list of the different assets you can invest in.
  • returns is a dictionary that stores the expected return (as a percentage) for each asset.
  • risk is a dictionary that stores the risk (variance) for each asset.
  • budget is the total amount of money available for investment.
  • max_risk is the maximum level of risk you’re willing to accept.

The problem is then defined to maximize the expected return while staying within the budget and risk constraints.

The solution tells you how much to invest in each asset.

Result

1
2
3
Invest in Asset1: $0.00
Invest in Asset2: $33333.33
Invest in Asset3: $66666.67

The result of the portfolio optimization problem suggests the following investment strategy:

  • Asset1: Invest $0.00 (no investment).
  • Asset2: Invest $33,333.33.
  • Asset3: Invest $66,666.67.

Explanation:

The optimization algorithm has determined that the best way to maximize your expected return, given the constraints on your total budget and acceptable risk level, is to allocate all of your budget to Asset2 and Asset3. Specifically:

  • Asset2 and Asset3 have the most favorable combination of return and risk, so they receive the entire budget.
  • Asset1 is not invested in because its return-risk profile is less optimal compared to the other assets.

This strategy aims to achieve the highest possible return while staying within the predefined risk tolerance.

Optimizing Supply Chain Transportation Costs with PuLP in Python

Optimizing Supply Chain Transportation Costs with PuLP in Python

  • Problem:
    You have a network of factories and warehouses, and you need to minimize the total transportation cost while satisfying demand at different locations.
  • PuLP Solution:
    Use $PuLP$ to formulate the transportation problem, where the objective is to minimize the transportation cost subject to supply and demand constraints.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import pulp

# Define the number of factories and warehouses
num_factories = 3
num_warehouses = 3

# Define the transportation costs from each factory to each warehouse
costs = [
    [4, 8, 6],  # Costs from factory 0 to warehouses
    [2, 5, 7],  # Costs from factory 1 to warehouses
    [3, 6, 4]   # Costs from factory 2 to warehouses
]

# Define the supply at each factory
supply = [20, 30, 25]

# Define the demand at each warehouse
demand = [30, 25, 20]

# Define the problem
prob = pulp.LpProblem("Supply_Chain_Optimization", pulp.LpMinimize)

# Decision variables: Amount transported from factories to warehouses
routes = [(i, j) for i in range(num_factories) for j in range(num_warehouses)]
transport_vars = pulp.LpVariable.dicts("Route", routes, lowBound=0, cat='Continuous')

# Objective function: Minimize transportation cost
prob += pulp.lpSum(transport_vars[i, j] * costs[i][j] for i, j in routes)

# Constraints: Meet demand at each warehouse
for j in range(num_warehouses):
    prob += pulp.lpSum(transport_vars[i, j] for i in range(num_factories)) == demand[j]

# Constraints: Do not exceed supply at each factory
for i in range(num_factories):
    prob += pulp.lpSum(transport_vars[i, j] for j in range(num_warehouses)) <= supply[i]

# Solve the problem
prob.solve()

# Print the results
for i in range(num_factories):
    for j in range(num_warehouses):
        print(f"Transport from factory {i} to warehouse {j}: {transport_vars[i, j].varValue}")

Explanation of the Code

  • num_factories and num_warehouses are the number of factories and warehouses in the supply chain.
  • costs is a 2D list where each entry represents the transportation cost from a factory to a warehouse.
  • supply is a list that defines the maximum amount of goods available at each factory.
  • demand is a list that defines the required amount of goods at each warehouse.
  • The decision variables, transport_vars, represent the amount transported from each factory to each warehouse.
  • The objective function minimizes the total transportation cost.
  • Constraints ensure that the demand at each warehouse is met and that the supply at each factory is not exceeded.

With these changes, the code should run without errors and provide the optimal transportation plan.

Result

1
2
3
4
5
6
7
8
9
Transport from factory 0 to warehouse 0: 20.0
Transport from factory 0 to warehouse 1: 0.0
Transport from factory 0 to warehouse 2: 0.0
Transport from factory 1 to warehouse 0: 10.0
Transport from factory 1 to warehouse 1: 20.0
Transport from factory 1 to warehouse 2: 0.0
Transport from factory 2 to warehouse 0: 0.0
Transport from factory 2 to warehouse 1: 5.0
Transport from factory 2 to warehouse 2: 20.0

The results describe the optimal transportation plan for minimizing costs in a supply chain. Here’s the breakdown:

  1. Factory 0 sends:

    • $20$ units to Warehouse 0.
    • $0$ units to Warehouse 1 and Warehouse 2.

  2. Factory 1 sends:

    • $10$ units to Warehouse 0.
    • $20$ units to Warehouse 1.
    • $0$ units to Warehouse 2.

  3. Factory 2 sends:

    • $0$ units to Warehouse 0.
    • $5$ units to Warehouse 1.
    • $20$ units to Warehouse 2.

Explanation:

  • Warehouse 0 receives a total of $30$ units
    ($20$ from Factory $0$ and $10$ from Factory $1$).
  • Warehouse 1 receives a total of $25$ units
    ($20$ from Factory $1$ and $5$ from Factory $2$).
  • Warehouse 2 receives a total of $20$ units
    (all from Factory $2$).

The plan ensures that each warehouse’s demand is met while keeping the transportation costs as low as possible.

Factory $0$, with a relatively low cost to Warehouse $0$, is utilized for that route, while Factory $2$ is used to supply Warehouse $2$.

Practical Uses of SymPy for Symbolic Mathematics in Python

Practical Uses of SymPy for Symbolic Mathematics in Python

$SymPy$ is a powerful $Python$ library for symbolic mathematics, which allows you to perform algebraic manipulations, calculus, equation solving, and more, all symbolically.

Here are some practical and convenient ways to use $SymPy$:

1. Symbolic Algebra:

  • Defining Symbols:
    You can define symbols for algebraic expressions using symbols() or Symbol(). 
    1
    2
    3
    4
    5
    from sympy import symbols

    x, y = symbols('x y')
    expression = x + 2*y
    print(expression)
  • Output: 
    1
    x + 2*y
    This allows you to perform operations like simplification, expansion, and factorization symbolically.
  • Simplification: 
    1
    2
    3
    4
    5
    from sympy import simplify

    expr = (x**2 + 2*x + 1)/(x + 1)
    simplified_expr = simplify(expr)
    print(simplified_expr)
  • Output: 
    1
    x + 1

2. Solving Equations:

  • Solving Algebraic Equations:
    $SymPy$ can solve equations for you symbolically. 
    1
    2
    3
    4
    5
    from sympy import Eq, solve

    equation = Eq(x**2 - 4, 0)
    solutions = solve(equation, x)
    print(solutions)
  • Output: 
    1
    [-2, 2]
  • Solving Systems of Equations:
    $SymPy$ also handles systems of linear or nonlinear equations. 
    1
    2
    3
    4
    equation1 = Eq(x + y, 2)
    equation2 = Eq(x - y, 0)
    solutions = solve((equation1, equation2), (x, y))
    print(solutions)
  • Output: 
    1
    {x: 1, y: 1}

3. Calculus:

  • Differentiation:
    Perform symbolic differentiation with ease. 
    1
    2
    3
    4
    5
    from sympy import diff

    function = x**3 + 3*x**2 + 2*x + 1
    derivative = diff(function, x)
    print(derivative)
  • Output: 
    1
    3*x**2 + 6*x + 2
  • Integration:
    Symbolic integration (both definite and indefinite) is straightforward. 
    1
    2
    3
    4
    5
    6
    7
    8
    from sympy import integrate

    integral = integrate(function, x)
    print(integral)

    # Definite integral
    definite_integral = integrate(function, (x, 0, 2))
    print(definite_integral)
  • Output: 
    1
    2
    x**4/4 + x**3 + x**2 + x
    18

4. Series Expansion:

  • Taylor Series:
    You can find the Taylor series expansion of functions. 
    1
    2
    3
    4
    from sympy import symbols, sin, series

    expansion = series(sin(x), x, 0, 6)
    print(expansion)
  • Output: 
    1
    x - x**3/6 + x**5/120 + O(x**6)

5. Matrix Operations:

  • Symbolic Matrices:
    $SymPy$ can handle symbolic matrices and perform operations like inversion, determinant calculation, and eigenvalue finding. 
    1
    2
    3
    4
    5
    from sympy import Matrix

    matrix = Matrix([[x, 2], [3, y]])
    determinant = matrix.det()
    print(determinant)
  • Output: 
    1
    x*y - 6

6. Limits:

  • Calculating Limits:
    $SymPy$ allows you to calculate limits of functions. 
    1
    2
    3
    4
    5
    from sympy import limit

    function = (x**2 - 1)/(x - 1)
    lim = limit(function, x, 1)
    print(lim)
  • Output: 
    1
    2

7. Solving Differential Equations:

  • Ordinary Differential Equations:
    $SymPy$ can symbolically solve ODEs. 
    1
    2
    3
    4
    5
    6
    from sympy import Function, dsolve, Eq

    f = Function('f')
    ode = Eq(f(x).diff(x, x) - 2*f(x), 0)
    solution = dsolve(ode, f(x))
    print(solution)
  • Output: 
    1
    Eq(f(x), C1*exp(-sqrt(2)*x) + C2*exp(sqrt(2)*x))

8. Plotting:

  • Basic Plotting:
    $SymPy$ integrates with matplotlib for basic plotting. 
    1
    2
    3
    from sympy.plotting import plot

    plot(x**2 + 2*x + 1)
  • Output:

9. Substitution:

  • Substituting Values:
    Substitute specific values into expressions. 
    1
    2
    3
    expr = x**2 + 2*x + 1
    result = expr.subs(x, 2)
    print(result)
  • Output: 
    1
    9

10. Polynomial Manipulation:

  • Factoring and Expanding Polynomials:
    $SymPy$ can factor and expand polynomial expressions. 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    from sympy import symbols, factor, expand

    x = symbols('x')

    # Factor the polynomial x^2 - 4
    factored = factor(x**2 - 4)

    # Expand the expression (x + 2)(x - 2)
    expanded = expand((x + 2)*(x - 2))

    print(factored)
    print(expanded)
  • Output: 
    1
    2
    (x - 2)*(x + 2)
    x**2 - 4

These examples showcase some of the most common and convenient uses of $SymPy$.

Whether you’re working on algebra, calculus, or solving equations, $SymPy$ provides a powerful toolset for symbolic mathematics in $Python$.

Knapsack Problem

Example of a Knapsack Problem

Problem Statement:
You are given a set of items, each with a weight and a value.

You need to determine the number of each item to include in a knapsack so that the total weight is less than or equal to a given limit, and the total value is as large as possible.

Items:

  • Item 1: Weight = $2$, Value = $3$
  • Item 2: Weight = $3$, Value = $4$
  • Item 3: Weight = $4$, Value = $5$
  • Item 4: Weight = $5$, Value = $6$

Knapsack Capacity: $8$

The goal is to maximize the total value without exceeding the knapsack capacity of $8$.

Python Solution:

This is a $dynamic$ $programming$ approach to solve the $0$/$1$ Knapsack Problem.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def knapsack(values, weights, capacity):
    n = len(values)
    # Create a 2D DP table with (n+1) x (capacity+1) size
    dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]

    # Fill the DP table
    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
            else:
                dp[i][w] = dp[i - 1][w]

    # The maximum value will be in dp[n][capacity]
    return dp[n][capacity]

# Example data
values = [3, 4, 5, 6]
weights = [2, 3, 4, 5]
capacity = 8

# Solve the problem
max_value = knapsack(values, weights, capacity)
print("Maximum value that can be carried in the knapsack:", max_value)

Explanation:

  1. Initialization:

    • The function knapsack takes three arguments: values, weights, and capacity.
    • The $dynamic$ $programming$ ($DP$) table dp is initialized with zeros.
      The table has dimensions (n+1) x (capacity+1), where n is the number of items.

  2. Filling the DP Table:

    • The outer loop iterates through the items, and the inner loop iterates through possible capacities from 1 to capacity.
    • For each item and capacity, the $DP$ table is updated by considering two possibilities:
      • Not including the item in the knapsack (value remains the same as the previous row).
      • Including the item in the knapsack (value is updated based on the remaining capacity and the value of the item).

  3. Result:

    • After filling the $DP$ table, the maximum value that can be carried in the knapsack is found in dp[n][capacity].

Output:

1
Maximum value that can be carried in the knapsack: 10

In this example, the optimal solution is to include Item $2$ (weight $3$, value $4$) and Item $4$ (weight $5$, value $6$), which gives a total value of $10$ while staying within the capacity limit of $8$.

Scheduling Problem

Scheduling Problem

A more practical application of $python$-$constraint$ is solving $scheduling$ $problems$, such as assigning people to tasks without conflicts.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from constraint import Problem

problem = Problem()

# Add variables (people and time slots)
people = ["Alice", "Bob", "Charlie"]
slots = ["Slot1", "Slot2", "Slot3"]
problem.addVariables(people, slots)

# Add constraints: no two people can be in the same time slot
problem.addConstraint(lambda a, b: a != b, ("Alice", "Bob"))
problem.addConstraint(lambda a, c: a != c, ("Alice", "Charlie"))
problem.addConstraint(lambda b, c: b != c, ("Bob", "Charlie"))

# Get the solution
solution = problem.getSolution()

# Print the solution
print(solution)

Explanation

This $Python$ code uses the $python$-$constraint$ library to solve a scheduling problem where three people (Alice, Bob, and Charlie) need to be assigned to different time slots (Slot1, Slot2, and Slot3).

The goal is to ensure that no two people are assigned to the same time slot.

Step-by-Step Explanation:

  1. Importing the Required Module:

    1
    from constraint import Problem

    The Problem class from the $python$-$constraint$ library is used to define and solve the constraint satisfaction problem (CSP).

  2. Creating the Problem Instance:

    1
    problem = Problem()

    A Problem object is instantiated, which will be used to define the variables (people and time slots) and constraints (no two people in the same slot).

  3. Defining Variables:

    1
    2
    3
    people = ["Alice", "Bob", "Charlie"]
    slots = ["Slot1", "Slot2", "Slot3"]
    problem.addVariables(people, slots)

    Three variables (Alice, Bob, and Charlie) are created, representing the people who need to be assigned to time slots.
    Each variable can take one of the values from the slots list (Slot1, Slot2, Slot3).

  4. Adding Constraints:

    1
    2
    3
    problem.addConstraint(lambda a, b: a != b, ("Alice", "Bob"))
    problem.addConstraint(lambda a, c: a != c, ("Alice", "Charlie"))
    problem.addConstraint(lambda b, c: b != c, ("Bob", "Charlie"))

    These constraints ensure that no two people are assigned to the same time slot:

    • The first constraint ensures Alice and Bob do not share the same slot.
    • The second constraint ensures Alice and Charlie do not share the same slot.
    • The third constraint ensures Bob and Charlie do not share the same slot.

    These constraints effectively enforce that each person must be in a unique time slot.

  5. Solving the Problem:

    1
    solution = problem.getSolution()

    The getSolution() method is used to find a solution that satisfies all the constraints.
    The solution is returned as a dictionary where the keys are the names of the people and the values are the assigned time slots.

  6. Printing the Solution:

    1
    print(solution)

    The solution is printed, showing which time slot each person is assigned to.

    For example, the output might be something like {'Alice': 'Slot3', 'Bob': 'Slot2', 'Charlie': 'Slot1'}, indicating that Alice is in Slot3, Bob is in Slot2, and Charlie is in Slot1.

Summary

This code solves a simple scheduling problem using constraints to ensure that three people (Alice, Bob, and Charlie) are assigned to different time slots (Slot1, Slot2, and Slot3).

The constraints ensure that no two people share the same time slot, and the solution provides a valid assignment that meets these conditions.

Constructing a $3 \times 3$ Magic Square

Constructing a $3 \times 3$ Magic Square

The $python$-$constraint$ library is a powerful tool for solving constraint satisfaction problems (CSPs) in $Python$.

It allows you to define variables, domains, and constraints, then finds solutions that satisfy all the constraints.

While the basic usage is straightforward, here are some unconventional or “curious” ways to use $python$-$constraint$ that showcase its flexibility.

Magic Square

A $magic$ $square$ is a grid where the sum of the numbers in each row, column, and diagonal is the same.

This is another interesting constraint satisfaction problem that can be solved with $python$-$constraint$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
from constraint import Problem, AllDifferentConstraint

problem = Problem()

# Add variables for a 3x3 magic square
variables = [(row, col) for row in range(3) for col in range(3)]
problem.addVariables(variables, range(1, 10))

# Add the all-different constraint
problem.addConstraint(AllDifferentConstraint(), variables)

# Add the magic square sum constraints
magic_sum = 15
for row in range(3):
    problem.addConstraint(lambda *args: sum(args) == magic_sum, [(row, col) for col in range(3)])

for col in range(3):
    problem.addConstraint(lambda *args: sum(args) == magic_sum, [(row, col) for row in range(3)])

problem.addConstraint(lambda *args: sum(args) == magic_sum, [(i, i) for i in range(3)])
problem.addConstraint(lambda *args: sum(args) == magic_sum, [(i, 2 - i) for i in range(3)])

# Get the solution
solution = problem.getSolution()

# Print the solution in a grid format
if solution:
    for row in range(3):
        print([solution[(row, col)] for col in range(3)])
else:
    print("No solution found.")

Explanation

This $Python$ code uses the $python$-$constraint$ library to solve a constraint satisfaction problem, specifically constructing a $ 3 \times 3 $ magic square.

In a magic square, all rows, columns, and diagonals must sum to the same value, known as the “$magic$ $sum$.”

For a $3 \times 3$ grid with the numbers $1$ to $9$, this magic sum is $15$.

Step-by-Step Explanation:

  1. Importing Required Modules:

    1
    from constraint import Problem, AllDifferentConstraint

    The Problem class is used to define and solve the constraint satisfaction problem (CSP).
    The AllDifferentConstraint ensures that all variables (the cells in the magic square) take different values.

  2. Creating the Problem Instance:

    1
    problem = Problem()

    A Problem object is instantiated to manage the variables and constraints of the problem.

  3. Defining Variables:

    1
    2
    variables = [(row, col) for row in range(3) for col in range(3)]
    problem.addVariables(variables, range(1, 10))

    The variables represent each cell in the $3 \times 3$ grid, identified by their row and column indices (e.g., (0, 0) for the top-left cell).
    Each cell can take a value from $1$ to $9$.

  4. Adding the All-Different Constraint:

    1
    problem.addConstraint(AllDifferentConstraint(), variables)

    This constraint ensures that all cells in the magic square have different values.
    In other words, no two cells can have the same number.

  5. Defining the Magic Sum:

    1
    magic_sum = 15

    The sum of each row, column, and diagonal in the magic square must equal $15$, which is the “$magic$ $sum$” for a $3 \times 3$ magic square using numbers $1$ to $9$.

  6. Adding Row Constraints:

    1
    2
    for row in range(3):
        problem.addConstraint(lambda *args: sum(args) == magic_sum, [(row, col) for col in range(3)])

    This loop adds constraints for each row in the grid, ensuring that the sum of the numbers in each row equals $15$.

  7. Adding Column Constraints:

    1
    2
    for col in range(3):
        problem.addConstraint(lambda *args: sum(args) == magic_sum, [(row, col) for row in range(3)])

    This loop adds constraints for each column in the grid, ensuring that the sum of the numbers in each column equals $15$.

  8. Adding Diagonal Constraints:

    1
    2
    problem.addConstraint(lambda *args: sum(args) == magic_sum, [(i, i) for i in range(3)])
    problem.addConstraint(lambda *args: sum(args) == magic_sum, [(i, 2 - i) for i in range(3)])

    These lines add constraints for the two diagonals of the magic square.
    The first constraint ensures that the main diagonal (top-left to bottom-right) sums to $15$, and the second ensures that the anti-diagonal (top-right to bottom-left) sums to $15$.

  9. Solving the Problem:

    1
    solution = problem.getSolution()

    The getSolution() method attempts to find a solution that satisfies all the constraints.
    If a solution is found, it is returned as a dictionary, where each key is a cell (e.g., (0, 0)) and each value is the number assigned to that cell.

  10. Printing the Solution:

    1
    2
    3
    4
    5
    if solution:
        for row in range(3):
            print([solution[(row, col)] for col in range(3)])
    else:
        print("No solution found.")

    If a solution is found, the code prints the magic square in a $3 \times 3$ grid format.
    If no solution is found, it prints “No solution found.”

Summary:

This code constructs a $3 \times 3$ magic square where each number from $1$ to $9$ is used exactly once, and the sum of the numbers in each row, column, and diagonal equals $15$.

By defining the problem as a set of constraints and solving it with the python-constraint library, the code finds a valid configuration for the magic square.

Output

[Output]

1
2
3
[6, 1, 8]
[7, 5, 3]
[2, 9, 4]

The result displayed represents a $3 \times 3$ magic square.

A magic square is a grid in which the numbers in each row, column, and diagonal all add up to the same value, known as the “$magic$ $sum$.”

For a $3 \times 3$ magic square using the numbers $1$ to $9$, this sum is $15$.

Breakdown of the Result:

  • First Row: [6, 1, 8]
    Sum: 6 + 1 + 8 = 15

  • Second Row: [7, 5, 3]
    Sum: 7 + 5 + 3 = 15

  • Third Row: [2, 9, 4]
    Sum: 2 + 9 + 4 = 15

Column Sums:

  • First Column: 6 + 7 + 2 = 15
  • Second Column: 1 + 5 + 9 = 15
  • Third Column: 8 + 3 + 4 = 15

Diagonal Sums:

  • Main Diagonal (Top-Left to Bottom-Right): 6 + 5 + 4 = 15
  • Anti-Diagonal (Top-Right to Bottom-Left): 8 + 5 + 2 = 15

Conclusion:

This $3 \times 3$ grid is a valid magic square.

Every row, column, and diagonal sums to $15$, satisfying the conditions of the magic square.

The numbers $1$ to $9$ are used exactly once, and the constraints of the problem have been correctly applied to generate this solution.

Cryptarithmetic Puzzle with Python-Constraint

Cryptarithmetic Puzzlewith Python-Constraint: A Creative Approach to Constraint Satisfaction

The $python$-$constraint$ library is a powerful tool for solving constraint satisfaction problems (CSPs) in $Python$.

It allows you to define variables, domains, and constraints, then finds solutions that satisfy all the constraints.

While the basic usage is straightforward, here are some unconventional or “curious” ways to use $python$-$constraint$ that showcase its flexibility.

Cryptarithmetic Puzzle

$Cryptarithmetic$ $puzzles$ involve solving mathematical equations where digits are replaced with letters.

For example, in the puzzle SEND + MORE = MONEY, each letter represents a unique digit.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
from constraint import Problem, AllDifferentConstraint

problem = Problem()

# Add variables for each letter
letters = 'SENDMORY'
problem.addVariables(letters, range(10))

# Add constraints: all letters must represent different digits
problem.addConstraint(AllDifferentConstraint(), letters)

# Add leading digit constraints (e.g., S and M cannot be zero)
problem.addConstraint(lambda S: S != 0, 'S')
problem.addConstraint(lambda M: M != 0, 'M')

# Add the equation constraint: SEND + MORE = MONEY
def equation(S, E, N, D, M, O, R, Y):
    send = S * 1000 + E * 100 + N * 10 + D
    more = M * 1000 + O * 100 + R * 10 + E
    money = M * 10000 + O * 1000 + N * 100 + E * 10 + Y
    return send + more == money

problem.addConstraint(equation, 'SENDMORY')

# Get the solution
solution = problem.getSolution()

# Print the solution
if solution:
    print(solution)
else:
    print("No solution found.")

Explanation

This $Python$ code uses the python-constraint library to solve a $cryptarithmetic$ $puzzle$, specifically the puzzle SEND + MORE = MONEY.

In this type of puzzle, each letter represents a unique digit, and the goal is to find the digits that satisfy the equation.

Step-by-Step Explanation:

  1. Importing the Required Modules:

    1
    from constraint import Problem, AllDifferentConstraint

    The Problem class from the python-constraint library is used to define and solve constraint satisfaction problems (CSPs).
    The AllDifferentConstraint ensures that all variables (letters) represent different digits.

  2. Creating the Problem Instance:

    1
    problem = Problem()

    A Problem object is instantiated, which will be used to define the variables and constraints for this puzzle.

  3. Defining Variables:

    1
    2
    letters = 'SENDMORY'
    problem.addVariables(letters, range(10))

    The letters in the puzzle (‘S’, ‘E’, ‘N’, ‘D’, ‘M’, ‘O’, ‘R’, ‘Y’) are treated as variables.
    Each letter can take a value between $0$ and $9$, representing a digit.

  4. Adding the All-Different Constraint:

    1
    problem.addConstraint(AllDifferentConstraint(), letters)

    This constraint ensures that all letters represent different digits.
    For example, ‘S’ cannot be the same as ‘E’, and so on.

  5. Adding Leading Digit Constraints:

    1
    2
    problem.addConstraint(lambda S: S != 0, 'S')
    problem.addConstraint(lambda M: M != 0, 'M')

    These constraints ensure that the leading digits of the numbers formed by the letters cannot be zero.
    For example, ‘S’ (the first digit of “SEND”) and ‘M’ (the first digit of “MORE” and “MONEY”) must be non-zero.

  6. Defining the Equation Constraint:

    1
    2
    3
    4
    5
    def equation(S, E, N, D, M, O, R, Y):
        send = S * 1000 + E * 100 + N * 10 + D
        more = M * 1000 + O * 100 + R * 10 + E
        money = M * 10000 + O * 1000 + N * 100 + E * 10 + Y
        return send + more == money

    This function converts the letters into the corresponding numbers and defines the equation SEND + MORE = MONEY.
    It calculates the numeric values of “SEND”, “MORE”, and “MONEY” and checks if the sum of “SEND” and “MORE” equals “MONEY”.

  7. Adding the Equation Constraint to the Problem:

    1
    problem.addConstraint(equation, 'SENDMORY')

    The equation function is added as a constraint to the problem, ensuring that the solution must satisfy the equation SEND + MORE = MONEY.

  8. Solving the Problem:

    1
    solution = problem.getSolution()

    The getSolution() method attempts to find a solution that satisfies all the constraints.
    If a solution exists, it returns the solution as a dictionary mapping each letter to its corresponding digit.

  9. Printing the Solution:

    1
    2
    3
    4
    if solution:
        print(solution)
    else:
        print("No solution found.")

    If a solution is found, it is printed. Otherwise, the program outputs “No solution found.”

Summary:

This code solves the $cryptarithmetic$ $puzzle$ SEND + MORE = MONEY using constraint satisfaction techniques.

It assigns digits to each letter while ensuring that the digits satisfy the puzzle’s rules:
no two letters have the same digit, the first letters (‘S’ and ‘M’) are non-zero, and the equation SEND + MORE = MONEY holds true.

Output

[Output]

1
{'M': 1, 'S': 9, 'D': 7, 'E': 5, 'N': 6, 'O': 0, 'R': 8, 'Y': 2}

The result {'M': 1, 'S': 9, 'D': 7, 'E': 5, 'N': 6, 'O': 0, 'R': 8, 'Y': 2} represents a valid solution to the $cryptarithmetic$ $puzzle$ SEND + MORE = MONEY.

Explanation of the Solution:

  • Letter-to-Digit Mapping:
    • M = 1
    • S = 9
    • D = 7
    • E = 5
    • N = 6
    • O = 0
    • R = 8
    • Y = 2

Substitution in the Equation:

  • SEND becomes 9567 (S = 9, E = 5, N = 6, D = 7)
  • MORE becomes 1085 (M = 1, O = 0, R = 8, E = 5)
  • MONEY becomes 10652 (M = 1, O = 0, N = 6, E = 5, Y = 2)

Verification:

The equation SEND + MORE = MONEY can be verified as follows:

  • 9567 + 1085 = 10652
  • The sum is correct, and the equation holds true.

Conclusion:

This mapping of letters to digits correctly satisfies the $cryptarithmetic$ $puzzle$, making it a valid solution.

The unique digits assigned to each letter, along with the correct calculation, ensure that the equation SEND + MORE = MONEY is fulfilled.