paint-brush
Using MILP and Python for Optimal Business Analyticsby@olaoluwa
1,404 reads
1,404 reads

Using MILP and Python for Optimal Business Analytics

by Olaoluwa AfolabiMarch 3rd, 2023
Read on Terminal Reader
Read this story w/o Javascript
tldt arrow

Too Long; Didn't Read

Gurobi is an industry-standard optimization solution for computer programming. It offers a wide range of mathematical framework for dealing with a range of optimization issues. MILP (Mixed Integer Linear Programming) is one of the solvers that embodies optimization techniques. We will 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.
featured image - Using MILP and Python for Optimal Business Analytics
Olaoluwa Afolabi HackerNoon profile picture


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:


The infusion center at UMC Hospital provides (drug) administration services for various treatments, including cancer Chemotherapy, Immunotherapy, Rheumatoid treatments, Ferrotherapy, and blood transfusion.


To ensure a reliable patient flow throughout the day, i.e., short waiting time for patients and little overtime for nurses, the center requires "at least" (this can be factored as "greater than or equals to") the following number of nurses to be scheduled to work at the center throughout the week: Monday = 17 Tuesday = 13 Wednesday = 15 Thursday = 19 Friday = 14 Saturday = 16 Sunday = 11. If a full-time nurse is employed, she is required to work five consecutive days followed by two days off. A part-time nurse is required to work three consecutive days followed by four days off.


The cost of employing full-time and part-time nurses depends on the day of the week: For Weekdays, Full-time = €250/day and Part-time = €150/day. For Saturdays, full-time = €315/day and Part-time = €185/day. For Sundays, Full-time = €375/day and Part-time = €225/day.


The pay difference is because full-time nurses are specialized with extensive trainings and with permanent contracts (more costs), whereas part-time nurses are general nurses (e.g., not specialized in chemotherapy) with temporary contracts. However, according to labor regulations, at most 25% of the time can be covered by part-time employment.


Formulate and solve a mathematical program (MILP) to answer the following questions:


  1. How many full-time and how many part-time nurses should the infusion center have on its payroll to minimize the total nursing cost, while meeting all requirements?


  2. How much is the minimum total cost per week?


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:

GRBModel.AddVars(count, type)

This lets you add a new decision variable to a model.


The argument allows you to supply the “count object of variables to add”, and “variable type for new variables, in which we will use INTEGER in our own case since we are dealing with the number of days scheduled for nurses.”

GRBModel.setObjective(expr, sense=None)

This function lets you set the model objective equal to a linear or quadratic expression.


The argument allows you to supply an expression, as well an as optional optimization sense (i.e.GRB.MINIMIZE for minimization, GRB.MAXIMIZE for maximization).

If optimization sense argumentis not supplied, it uses the ModelSense attribute value to determine the sense.

GRBModel.AddConstr(lhsExpr, sense, rhsExpr, name)

This lets you add a single linear constraint to a model.


The argument allows you to supply “left-hand side expression for new linear constraint,” “sense for new linear constraint which can be less-than-or-equals-to, equals-to, greater-than-or-equals-to,” “right-hand side expression for new linear constraint,” and “name of the expression which is a string.”

Model.optimize(callback=None)

This takes the callback class attribute.


A callback is a user function that is called periodically by the Gurobi optimizer in order to allow the user to query or modify the state of the optimization. More precisely, if you pass a function that takes two arguments (model and where) as the argument to Model.optimize() or Model.computeIIS(), your function will be called during the optimization.


We must use the optimize() method to discover the best outcome that fulfills the requirements and minimizes or maximizes the objective function after establishing the variables, constraints, and objective function.


Gurobi resolves the optimization issue when the optimize() function is used, and it then returns the value of the ideal objective function as well as the values of the ideal choice variables.

The optimize() method produces a suitable message describing the nature of the issue if the optimization task is “unsolvable” or “infeasible”.


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()
    


  1. Define the decision variables


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


  2. 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.


  3. 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])
    


  1. 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))
    


  1. 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)
    


  2. 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)
    


  3. Now, let’s solve the model


    model.optimize()
    


  4. 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

Solution Report for MILP:


While making sure that the necessary staffing levels are reached, our goal is to reduce the hospital's overall nursing cost. To tackle the issue, we employed Python and the MILP (Mixed Integer Linear Programming) method.


The ideal answer has been discovered by optimizing the MILP model. The ideal goal is

€25,155, while the ideal bound, with a 0% gap, is €25,155. This shows that we are quite confident that we have discovered the best option.


We may deduce that the personnel levels for each day of the week are as follows based on the ideal solution:


  • On Monday, there are 17 shifts of full-time nursing employment; part-time nursing is not available on that day.
  • There are 13 full-time nursing shifts on Tuesday, but no part-time nursing shifts.
  • Part-time nurses work 3 shifts on Wednesday, compared to 12 shifts for full-time nurses.
  • There are 19 full-time nursing shifts on Thursday, but no part-time nursing shifts.
  • There are no part-time nurses on Friday; instead, full-time nurses work 14 shifts.
  • Full-time nurses work 4 shifts on Saturday, while part-time nurses work 12 shifts.
  • There are no full-time nurses on duty on Sunday, but part-time nurses cover 11 shifts.


This strategy minimizes the overall nursing cost while meeting the minimal staffing requirements for each day of the week. This ideal option will cost €25155 in nursing costs overall.


Overall, this solution offers a practical and cost-effective approach to improving workforce numbers in hospitals.



Lead image generated with stable diffusion.