Using MILP and Python for Optimal Business Analytics

Decision-making is one of the most stressful human endeavors. Every now and then people use all forms of frameworks such as SWOT Analysis, MoSCoW Analysis, Pros & Cons which I call hedges to consider in decision making by Benjamin Franklin, the Eisenhower matrix, Ikigai which is a Japanese method for figuring out whether your life is headed in the correct direction—as it translates approximately to "cause for living”, the SPADE framework, Modified Borda Count, RICE decisions framework, Hoy-Tarter Model, Cynefin framework, Hartnett's consensus-oriented decision model, Vroom-Yetton Decision Model, OODA loops, the STAR framework in solving conflicts—to mention but a few.

These frameworks aforementioned do not leave out optimization techniques; which relatively include finding the shortest path between two points. Several disciplines, including engineering, finance, economics, operations research, and machine learning, can benefit from the usage of optimization techniques. MILP (Mixed Integer Linear Programming) is one of the solvers that embodies optimization techniques. Hence, we’ll focus on using it to solve a problem in this article, majorly because, MILP is a mathematical optimization technique that combines “linear programming” and “integer programming” to solve problems with both continuous and discrete variables.

We will take on a Nursing Scheduling Problem (NSP) in this article, and below are the concerns we need to solve:

Our goal in this problem is to find the optimal values of the variables that satisfy a set of linear constraints and an objective function that is to be maximized or minimized. Also, I want to emphasize in the question's points that said full-time nurses are "specialized with extensive training." I do think expertise specializations are great enough perks to build in a hospital environment, considering the fact that they deal with hospital patients, and precedence for that will not be a bad idea even if we will augment with part-time nurses. Most importantly, you don’t want high adverse effects in your hospital administration.

We will solve this question/problem with the Gurobi Optimizer Python module. But before solving it, let’s talk about Gurobi.

What is Gurobi?

Gurobi is an industry-standard optimization solution for computer programming. It offers a strong and adaptable framework for dealing with a wide range of mathematical optimization issues, including those involving linear programming (LP), mixed-integer programming (MIP), quadratic programming (QP), second-order conic programming (SOCP), and many more. With applications ranging from supply chain management and logistics to portfolio optimization and machine learning, Gurobi is extensively utilized in business, academia, and research. Python, C++, Java, MATLAB, and R are just a few of the programming languages for which Gurobi provides interfaces.

We are going to be using the following functions in the Gurobi Python Optimization module:

Having established the nitty-gritty of our forte, let’s proceed to solve the question and take the following steps:

1. Install the Gurobi Optimizer software and obtain a license, if you haven't done so already.

   python -m pip install gurobipy==10.0.1
   

2. Import the Gurobi Python module and initialize the Gurobi environment.

   from gurobipy import *
   

3. Define the days of the week as given in the question.

   days = ['Mon', 'Tue', 'Wed', 'Thu', 'Fri', 'Sat', 'Sun']
   

4. Define the demand for nurses on each day of the week as given.

   demand = {'Mon': 17, 'Tue': 13, 'Wed': 15, 
                        'Thu': 19, 'Fri': 14, 'Sat': 16, 'Sun': 11}
   

5. Define the cost of employing full-time nurses on each day of the week as given.

   cost_fulltime = {'Mon': 250, 'Tue': 250, 'Wed': 250, 
                                'Thu': 250, 'Fri': 250, 'Sat': 315, 'Sun': 375}
   

6. Define the cost of employing part-time nurses on each day of the week

   cost_parttime = {'Mon': 150, 'Tue': 150, 'Wed': 150, 
                                'Thu': 150, 'Fri': 150, 'Sat': 185, 'Sun': 225}
   

7. Define the maximum proportion of time that can be covered by part-time employment. The question says 25% which is 0.25

   max_parttime = 0.25
   

8. Define the number of consecutive days worked by full-time and part-time nurses

   fulltime_days_on = 5
   parttime_days_on = 3
   

9. Create the Gurobi model

   model = Model()
   

10. Define the decision variables

    fulltime = model.addVars(days, vtype=GRB.INTEGER, name="fulltime")
    parttime = model.addVars(days, vtype=GRB.INTEGER, name="parttime")
    

11. Define the objective function to minimize the total cost of nurses

    model.setObjective(sum(
        cost_fulltime[d] * fulltime[d] + cost_parttime[d] * parttime[d] for d in days))
    

    For setObjective() functions, we did not supply to minimize or maximize. Not supplying it will make Gurobi default this to ModelSense, which it is understood to be that we are minimizing. Our expression indeed represents the minimize objective function.

    Minimization and maximization are the two fundamental types of objectives in optimization.

    Finding the minimal value of a function or objective, or the point at which it has the lowest conceivable value is referred to as minimization.

    On the other hand, maximization describes the process of determining the point at which a function or aim has the highest potential value or its maximum value.

    For instance, in linear programming, we frequently aim to maximize or reduce an objective function while taking into account certain limitations. The quantity that we want to maximize or minimize is represented by the objective function, and the constraints are the restrictions or boundaries placed on the task.

12. Add the constraints to ensure that the demand for nurses is met on each day of the week

    for d in days:
        model.addConstr(fulltime[d] + parttime[d] >= demand[d])
    

13. Add the constraints to ensure that the maximum proportion of time is covered by part-time employment

    model.addConstr(sum(parttime[d] for d in days) <=
                    max_parttime * sum(fulltime[d] + parttime[d] for d in days))
    

14. Add the constraints to ensure that full-time nurses work five consecutive days followed by two days off.

    for i in range(len(days) - fulltime_days_on + 1):
        model.addConstr(sum(fulltime[days[j]]
                        for j in range(i, i + fulltime_days_on)) >= 5)
    

15. Add the constraints to ensure that part-time nurses work three consecutive days followed by four days off.

    for i in range(len(days) - parttime_days_on + 1):
        model.addConstr(sum(parttime[days[j]]
                        for j in range(i, i + parttime_days_on)) >= 3)
    

16. Now, let’s solve the model

    model.optimize()
    

17. Since we optimized our model. Let’s print out the result of the optimization to answer our sub-questions.

    print("Optimal Solution:")
    for d in days:
        print("{}: Full-time={}, Part-time={}".format(d, int(fulltime[d].x), int(parttime[d].x)))
    
    print("Total Cost: €{}".format(int(model.objVal)))
    

    Output

    On my own local system, this is the solution I got:

    Restricted license - for non-production use only - expires 2024-10-28
    Gurobi Optimizer version 10.0.1 build v10.0.1rc0 (mac64[x86])
    
    CPU model: Intel(R) Core(TM) i7-4558U CPU @ 2.80GHz
    Thread count: 2 physical cores, 4 logical processors, using up to 4 threads
    
    Optimize a model with 16 rows, 14 columns and 58 nonzeros
    Model fingerprint: 0xbd18a424
    Variable types: 0 continuous, 14 integer (0 binary)
    Coefficient statistics:
      Matrix range     [2e-01, 1e+00]
      Objective range  [2e+02, 4e+02]
      Bounds range     [0e+00, 0e+00]
      RHS range        [3e+00, 2e+01]
    Found heuristic solution: objective 27615.000000
    Presolve time: 0.00s
    Presolved: 16 rows, 14 columns, 58 nonzeros
    Variable types: 0 continuous, 14 integer (0 binary)
    Found heuristic solution: objective 26835.000000
    
    Root relaxation: objective 2.512250e+04, 14 iterations, 0.00 seconds (0.00 work units)
    
        Nodes    |    Current Node    |     Objective Bounds      |     Work
     Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time
    
         0     0 25122.5000    0    2 26835.0000 25122.5000  6.38%     -    0s
    H    0     0                    25155.000000 25122.5000  0.13%     -    0s
    
    Explored 1 nodes (14 simplex iterations) in 0.01 seconds (0.00 work units)
    Thread count was 4 (of 4 available processors)
    
    Solution count 3: 25155 26835 27615 
    
    Optimal solution found (tolerance 1.00e-04)
    Best objective 2.515500000000e+04, best bound 2.515500000000e+04, gap 0.0000%
    
    Optimal Solution:
    Mon: Full-time=17, Part-time=0
    Tue: Full-time=13, Part-time=0
    Wed: Full-time=12, Part-time=3
    Thu: Full-time=19, Part-time=0
    Fri: Full-time=14, Part-time=0
    Sat: Full-time=4, Part-time=12
    Sun: Full-time=0, Part-time=11
    
    Total Cost: 
    €25155
    

    To arrive at the total number of full-time and part-time nurses asked in Question 1, we simply sum the number of nurses scheduled to work on each day of the week. For example, the optimal solution shows that on Monday, 17 full-time and 0 part-time nurses should be scheduled to work, so the total number of nurses for that day is 17 + 0 = 17.

    If we sum the number of nurses scheduled to work on each day of the week, we get the following:

    Full-time nurses: 17 + 13 + 12 + 19 + 14 + 4 + 0 = 79
    Part-time nurses: 0 + 0 + 3 + 0 + 0 + 12 + 11 = 26
    

    As for Question 2; the total cost of €25,155 is the minimum cost that was obtained from solving the optimization problem. This represents the total cost that the infusion center will incur while meeting all the requirements of the problem statement, and employing the optimal number of full-time and part-time nurses.

    In conclusion, we can see our solution is feasible. However, this can still be worked on in such a way that the optimization reduces the number of full-time nurses since they come on the high side of emoluments. But we need to ask ourselves if the perks of the consistency of training the full-time nurses have are what we can forego. If so, then we may find a solution that will be on the high side of part-time nurses and a few full-time nurses with a considerable amount of cost lower than our €25,155 result, even while maintaining 0.25% of the workload and 3 days of work schedule with 4 days off.

How do you present your report as a Business Analyst?

This is how I will go about it below

Lead image generated with stable diffusion.