Linear Programming Python Libraries for Real-World Applications: Optimizing Nurse Scheduling
Powerful Tool for Optimization
Linear programming is a powerful mathematical method to optimize complex systems and processes. It falls under the umbrella of operations research and is widely used in various fields such as economics, engineering, business management, and many more.
The origins of linear programming can be attributed to the work of George Dantzig, a mathematician who developed the simplex method in the 1940s. Dantzig's groundbreaking algorithm provided a systematic approach to solving linear programming problems by iteratively moving toward the optimal solution along the edges of a polytope defined by the problem constraints. This development marked the beginning of a new era in optimization, revolutionizing decision-making processes in various industries and disciplines.
Throughout the decades, linear programming has evolved and expanded its applications, becoming a foundational tool in operations research, economics, engineering, and many other fields. The field experienced significant growth in the 1970s with advancements in interior-point methods, which provided alternative approaches to solving large-scale linear programming problems efficiently.
At its core, linear programming involves maximizing or minimizing a linear objective function subject to a set of linear constraints. The objective function represents the goal or outcome that needs to be optimized, while the constraints define the limitations or restrictions within which this optimization must occur.
One of the key advantages of linear programming is its ability to model and solve problems with multiple decision variables and constraints in a systematic and efficient manner. By formulating real-world problems into mathematical equations, practitioners can use specialized algorithms to find the optimal solution.
Applications of linear programming are diverse and encompass a wide range of industries. For example, in supply chain management, linear programming can be used to optimize production schedules, inventory levels, and distribution networks. In finance, it can help in portfolio optimization and risk management. In manufacturing, it can streamline production processes and resource allocation.
Linear Programming with Python
PuLP
PuLP is an open-source linear programming (LP) modeling tool in Python that allows users to define and solve optimization problems in a simple and straightforward manner. It provides an easy-to-use interface for constructing LP problems and interfaces with a variety of LP solvers, making it a versatile and accessible tool for optimization modeling.
Key features of PuLP include:
User-Friendly Modeling:? PuLP allows users to define decision variables, constraints, and the objective function using a syntax that closely resembles standard mathematical notation. This makes it easy for users to formulate complex LP problems without needing to learn a new modeling language.
Integration with Solvers: PuLP supports a range of LP solvers, including open-source solvers like CBC, GLPK, and COIN-OR, as well as commercial solvers like Gurobi and CPLEX. Users can easily switch between different solvers to find the most efficient solution to their LP problems.
Linear and Integer Programming Support: In addition to linear programming, PuLP also supports integer programming, allowing users to solve optimization problems with integer decision variables. This makes PuLP suitable for a wide range of optimization applications, including production planning, resource allocation, and scheduling.
Python Integration: PuLP is designed to work seamlessly with Python, allowing users to leverage the full power of the Python programming language when formulating and solving optimization problems. This integration makes it easy to incorporate data preprocessing, visualization, and other data manipulation tasks into the optimization workflow.
Alternative Linear Programming Python Libraries
When exploring alternative linear programming libraries to PuLP, several options provide similar functionality for optimization modeling in Python. These libraries offer unique features, interfaces, and solver compatibility, catering to different user preferences and requirements.
SciPy:
Overview: SciPy is a fundamental library for scientific computing in Python and includes optimization tools for linear programming among its extensive functionality.
Features: SciPy's optimize.linprog function provides a simple interface for linear programming with a focus on efficiency and performance.
Advantages: SciPy seamlessly integrates with other scientific computing functions in Python, providing a comprehensive environment for optimization and numerical computing tasks.
Usage: Ideal for users looking for a lightweight and efficient optimization library within the broader spectrum of scientific computing tools.
Example: An environmental engineering firm optimizing waste management processes to minimize landfill usage and transportation costs. SciPy's optimization tools can help model and solve linear programming problems to determine the most efficient waste collection and disposal routes while meeting environmental regulations and cost constraints.
CVXPY:
Overview: CVXPY is a domain-specific language for convex optimization embedded in Python, allowing users to formulate and solve convex optimization problems easily.
Features: CVXPY supports a wide range of convex optimization problems, including linear programming, quadratic programming, and semidefinite programming, using a user-friendly syntax.
Advantages: CVXPY offers high-level modeling and abstraction for optimization problems, particularly focusing on convex optimization scenarios.
Usage: Suited for users dealing with complex convex optimization problems or who require a more declarative and structured approach to optimization modeling.
Example: A financial services company developing an automated investment portfolio optimization tool. CVXPY's support for convex optimization is valuable in formulating efficient portfolio allocation strategies that maximize returns while managing risk within predefined constraints, considering factors like asset returns, risks, correlations, and investor preferences.
?
OR-Tools:
Overview: OR-Tools is an optimization library developed by Google that provides a suite of tools and solvers for combinatorial optimization and constraint programming.
Features: OR-Tools offers a wide range of solvers for various combinatorial optimization problems, including linear programming, mixed-integer programming, and routing problems.
Advantages: OR-Tools is highly efficient and versatile, making it suitable for solving complex optimization problems at scale.
Usage: Recommended for users working on combinatorial optimization tasks, routing problems, or operations research applications requiring specialized solvers.
Example: A logistics company optimizing delivery routes and vehicle assignments for a fleet of trucks. OR-Tools' specialized solvers for vehicle routing problems can help determine the most cost-effective routes, minimize fuel consumption, and ensure timely deliveries by efficiently allocating resources and optimizing transportation logistics.
?
Pyomo:
Overview: Pyomo is a flexible optimization modeling language for formulating and solving optimization models in Python, supporting a variety of optimization problem types.
Features: Pyomo provides a powerful modeling framework for expressing optimization problems in a concise and readable manner, with support for various solvers and modeling techniques.
Advantages: Pyomo offers advanced modeling capabilities and extensibility, making it suitable for researchers, engineers, and practitioners dealing with complex optimization challenges.
Usage: Ideal for users requiring a high level of customization, flexibility, and modeling capabilities in optimization tasks.
领英推荐
Example: An energy utility company optimizing power generation and distribution networks to meet demand and minimize operational costs. Pyomo's flexible modeling language can assist in formulating complex optimization models for energy grid management, considering variables like load balancing, renewable energy integration, transmission constraints, and demand-response mechanisms.
Real-life Example: Optimizing Nurse Scheduling with PuLP
Scenario
In healthcare settings, the scheduling of nursing staff is critical to ensure optimal patient care and staff well-being. The challenge involves assigning shifts in a way that balances the workload fairly among all nurses while adhering to specific constraints. The goal is to create a schedule that distributes day and night shifts evenly among nurses over a month, preventing fatigue and ensuring compliance with labor regulations.
Constraints
1. Two Nurses Per Shift, Every Day: Each shift every day must be covered by exactly two nurses.
2. Maximum One Shift Per Day Per Nurse: No nurse works more than one shift on any given day.
3. No Consecutive Night-Day Shifts: Nurses should not work a night shift followed by a day shift or a day shift followed by a night shift.
4. Balanced Shift Allocation: Aim to balance the total number of shifts each nurse gets.
5. Balanced Day-Night Shift Distribution: Each nurse should have a roughly equal number of day and night shifts, minimizing workload imbalance.
Python code
This Python code uses the PuLP library to create a linear programming model for nurse scheduling optimization.
import pulp
import csv
# Create the LP model
model = pulp.LpProblem("Nurse_Scheduling", pulp.LpMinimize)
# Parameters
n_days = 30
n_nurses = 8
shifts = ['day', 'night']
# Decision Variables
schedule = pulp.LpVariable.dicts("schedule",
((nurse, day, shift) for nurse in range(n_nurses) for day in range(n_days) for shift in shifts),
cat='Binary')
# Objective: Minimize the total number of shifts
model += pulp.lpSum(schedule[(nurse, day, shift)] for nurse in range(n_nurses) for day in range(n_days) for shift in shifts)
# Constraints
# Each shift on each day must be covered by exactly two nurses
for day in range(n_days):
for shift in shifts:
model += pulp.lpSum(schedule[(nurse, day, shift)] for nurse in range(n_nurses)) == 2
# No nurse works more than one shift per day
for nurse in range(n_nurses):
for day in range(n_days):
model += pulp.lpSum(schedule[(nurse, day, shift)] for shift in shifts) <= 1
# No consecutive day-night or night-day shifts for any nurse
for nurse in range(n_nurses):
for day in range(n_days - 1):
model += schedule[(nurse, day, 'night')] + schedule[(nurse, day + 1, 'day')] <= 1
model += schedule[(nurse, day, 'day')] + schedule[(nurse, day + 1, 'night')] <= 1
# Balance the total shifts and day-night shift ratio per nurse
total_shifts = [pulp.lpSum(schedule[(nurse, day, shift)] for day in range(n_days) for shift in shifts) for nurse in range(n_nurses)]
day_shifts = [pulp.lpSum(schedule[(nurse, day, 'day')] for day in range(n_days)) for nurse in range(n_nurses)]
balance_tol = 2 # Set a tolerance for shift balance
# Ensure total shifts are evenly distributed among nurses
avg_shifts = pulp.LpVariable("avg_shifts", lowBound=0)
model += avg_shifts == pulp.lpSum(total_shifts) / n_nurses
for nurse in range(n_nurses):
model += total_shifts[nurse] >= avg_shifts - balance_tol
model += total_shifts[nurse] <= avg_shifts + balance_tol
# Ensure day-night shift balance per nurse
for nurse in range(n_nurses):
shift_diff = day_shifts[nurse] - (total_shifts[nurse] / 2) # Calculate the deviation between day and night shifts
model += shift_diff <= balance_tol
model += shift_diff >= -balance_tol
# Solve the model
status = model.solve()
# Output the schedule to CSV
if status == pulp.LpStatusOptimal:
with open('nurse_schedule.csv', 'w', newline='') as file:
writer = csv.writer(file)
header = ['Nurse/Day'] + [f"Day {d+1}" for d in range(n_days)]
writer.writerow(header)
for nurse in range(n_nurses):
row = [f"Nurse {nurse + 1}"]
for day in range(n_days):
shift_str = ''
if pulp.value(schedule[(nurse, day, 'day')]) == 1:
shift_str += 'D'
elif pulp.value(schedule[(nurse, day, 'night')]) == 1:
shift_str += 'N'
row.append(shift_str)
writer.writerow(row)
print("The schedule has been successfully written to 'nurse_schedule.csv'.")
elif status == pulp.LpStatusInfeasible:
print("No feasible solution exists.")
else:
print(f"An unexpected issue occurred with status: {pulp.LpStatus[status]}")
Python Code Walkthrough
Imports: The code first imports the necessary libraries - pulp for linear programming modeling and optimization, and csv for handling CSV file operations.
import pulp
import csv
LP Model Initialization: It initializes an LP model named "Nurse_Scheduling" with the objective of minimizing the total number of shifts.
# Create the LP model
model = pulp.LpProblem("Nurse_Scheduling", pulp.LpMinimize)
Parameters: It defines parameters such as the number of days (n_days), the number of nurses (n_nurses), and the types of shifts (shifts).
?# Parameters
n_days = 30
n_nurses = 8
shifts = ['day', 'night']
Decision Variables: The code snippet below creates decision variables for the nurse scheduling optimization problem.
?# Decision Variables
schedule = pulp.LpVariable.dicts("schedule",
((nurse, day, shift) for nurse in range(n_nurses) for day in range(n_days) for shift in shifts),
cat='Binary')
Objective Function: Here, the objective function is defined to minimize the total number of shifts.
# Objective: Minimize the total number of shifts
model += pulp.lpSum(schedule[(nurse, day, shift)] for nurse in range(n_nurses) for day in range(n_days) for shift in shifts)
Constraints - Coverage and Working Limit: Constraints are imposed to ensure each shift on each day is covered by exactly two nurses and that no nurse works more than one shift per day.
# Constraints
# Each shift on each day must be covered by exactly two nurses
for day in range(n_days):
for shift in shifts:
model += pulp.lpSum(schedule[(nurse, day, shift)] for nurse in range(n_nurses)) == 2
# No nurse works more than one shift per day
for nurse in range(n_nurses):
for day in range(n_days):
model += pulp.lpSum(schedule[(nurse, day, shift)] for shift in shifts) <= 1
Balancing Shifts and Constraints: The code balances the total shifts and day-night shift ratio per nurse with a given tolerance.
# Balance the total shifts and day-night shift ratio per nurse
total_shifts = [pulp.lpSum(schedule[(nurse, day, shift)] for day in range(n_days) for shift in shifts) for nurse in range(n_nurses)]
day_shifts = [pulp.lpSum(schedule[(nurse, day, 'day')] for day in range(n_days)) for nurse in range(n_nurses)]
balance_tol = 2 # Set a tolerance for shift balance
Solving the Model: It solves the LP model using PuLP's solver and stores the status of the optimization process.
# Solve the model
status = model.solve()
Output to CSV: If an optimal solution is found, the nurse schedule is outputted to a CSV file named 'nurse_schedule.csv.' The nurse schedules are written in the CSV file, and each nurse's shifts are listed for each day.
# Output the schedule to CSV
if status == pulp.LpStatusOptimal:
with open('nurse_schedule.csv', 'w', newline='') as file:
writer = csv.writer(file)
header = ['Nurse/Day'] + [f"Day {d+1}" for d in range(n_days)]
writer.writerow(header)
for nurse in range(n_nurses):
row = [f"Nurse {nurse + 1}"]
for day in range(n_days):
shift_str = ''
if pulp.value(schedule[(nurse, day, 'day')]) == 1:
shift_str += 'D'
elif pulp.value(schedule[(nurse, day, 'night')]) == 1:
shift_str += 'N'
row.append(shift_str)
writer.writerow(row)
print("The schedule has been successfully written to 'nurse_schedule.csv'.")
Output Analysis
The result, saved to 'nurse_schedule.csv,' will detail the shift schedule for each of the 8 nurses across 30 days, denoted by 'D' for day shifts and 'N' for night shifts. By examining the CSV, we can analyze the distribution:
Uniformity Checks: Each nurse should have close to the total shifts divided by the number of nurses (balanced workload).
Day/Night Checks: Each nurse's number of 'D's should roughly equal 'N's, indicating an even spread between different shift types.
Additional tuning of constraints is required to adjust the optimal solutions to business needs.
.\python.exe .\py_dev\TestPy\lp.py
Welcome to the CBC MILP Solver
Version: 2.10.3
Problem MODEL has 797 rows, 481 columns and 4305 elements
Result - Optimal solution found
Objective value: 120.00000000
Enumerated nodes: 0
Total iterations: 0
Time (CPU seconds): 0.23
Time (Wallclock seconds): 0.22
Option for printingOptions changed from normal to all
Total time (CPU seconds): 0.27 (Wallclock seconds): 0.27
The schedule has been successfully written to 'nurse_schedule.csv'.
Process finished with exit code 0
This approach demonstrates the practical application of linear programming to solve complex scheduling tasks in critical environments like healthcare. By automating the schedule generation and ensuring it meets defined constraints, we can significantly improve operational efficiency and staff satisfaction. The flexibility of this model means it can be adjusted and extended based on additional requirements or changes in operational constraints.
Neven Dujmovic, May 2024
#LinearProgramming #lp #python #scheduling #PuLP #SciPy #CVXPY #ORTools #Pyomo #LPModel #Optimization #DecisionMaking