The Side Benefits of True Optimization

Ric Kosiba, Ph.D. Vice President, Genesys

Math Magic

When I was in college, I ran across a field of study that included a type of math that had magical properties. I was so enamored with this math that I know I must have written about it in this space before. But while I’ve mentioned it and its main superpower, I haven’t delved into the extra stuff that it provides.

The magic is, of course, mathematical optimization, and in particular, a type of math called mixed-integer programming (MIP). What’s magical about MIP? It’s this: any problem that can be described in such a way that it is an MIP, can be solved using store-bought algorithms. And by solved, I mean that it can be solved to find the very best answer possible.

More explanation: problems that can be described in a linear fashion (unimportant for our discussion), that have an objective and a series of constraints, can be solved to find the absolute best possible solution of the objective, that meet all constraints. Here is something cool: an MIP can be used for agent scheduling. For instance, in workforce scheduling, we might have an objective and constraints that look something like:

  • Minimize Total Staffing Costs = {a lot of linear math here}
  • Subject to:
  • Constraint 1: employees can only work up to 40 hours a week = {a lot of linear math here}
  • Constraint 2: we must hit our service levels at each interval = {a lot of linear math here}
  • Constraint 3: employees get two days off in a row = {a lot of linear math here}
  • Constraint 4: employee preferences for their shifts are good to hit = {a lot of linear math here}
  • … and so on.

After we develop our MIP and run it through the store-bought algorithm, we would be able to find the set of shifts that hit every constraint and do so at the absolute least Total Staffing Costs. It’s magical, because we can prove (again through math) that it is the definite best solution, and therefore the solution to the scheduling problem that will always save our companies the most amount of money.

That, in and of itself, is a fantastic thing. Knowing that the math model solves in a true optimal way, gives the process credibility that heuristic (rule-of-thumb) algorithms cannot have. There is never a point when developing an MIP that the process is suspect, because we know it will consistently give us the purest, best, least-cost solution.

But optimality has other benefits, other than that big money-saving one, that us WFM math-types should appreciate. Let’s discuss these.

The Cost of Constraints

MIPs spit out a few extra pieces of analytics every time they solve. One natural output of an MIP is it will tell us the cost of every constraint. Meaning, while we have objectives and constraints, each constraint moves us farther from absolute optimality, and MIP algorithms will determine the cost of each constraint as it solves.

For instance, if we were to add to our scheduling MIP a constraint that says we can only schedule agents to start their shifts at the top of any hour, it would be trivial to determine the cost of this additional constraint. Maybe it costs a lot, but maybe it is not a lot. But because our scheduler is a true optimization process, we can know the true cost of this, and any other constraint we dream up.

In my olden days, I worked at a union-shop airline, and one of my jobs — every time there was a contract negotiation — was to determine the costs of every union work rule. When negotiating with the union, the company wanted to know what efficiencies they would gain or give up as they added or subtracted a work rule. This was easy to determine, because our scheduling process used real optimization. Heuristics cannot do this accurately.

Multiple Objectives: WEM vs. WFM

With the current push to develop ways to help our agent’s quality of life, there are clearly competing objectives. We would like to run our operation as efficiently as possible, but we also would like to create shifts that are desired by our agents. There are obviously trade-offs in doing this, the question is, how do we draw out and make clear these trade-offs?

As in the previous section, we can layer multiple constraints onto our scheduling MIP and determine the cost of each additional quality-of-life constraint. For many of the quality of life issues, adding constraints and seeing the costs is the best approach.

But another math approach is to quantify the agent’s objectives and to create almost a sliding scale of what is important to the company (efficiency) and what is important to agents. In my experience, agents had a strong preference for work-hours that were deemed more traditional – more “nine to five like.” Assuming that this is your agent’s strong preference, we could construct a linear objective that we could add to the previous objective (Minimize Total Staffing Costs). So our new MIP would be:

  • Fudge Factor 1 * (Minimize Total Staffing Costs) + Fudge Factor 2 * (Maximize Agent’s Favorite Shifts)
  • Subject to:
  • (the same previous constraints) plus
  • Fudge Factor 1 + Fudge Factor 2 = 1

By varying the value of Fudge Factor 1, we could understand (and graph) the efficiency cost of providing more or fewer good shifts.
In your organization, there might be other quality of life objectives, and if you truly optimized your schedules, you could determine these sorts of tradeoffs, between agent engagement and operational efficiency.

Determine the Next Best Shift

Yet another cool thing that pops out of our MIP is the value, also called the opportunity cost, of each variable. What that means for our scheduling MIP is that we get to know which variable, which shift, would be the most valuable if we could have just one more. For our multi-objective MIP, that means we would know the value—in terms of both the efficiency and agent preference of having one more of each shift type. This would help us know that if we could hire more agents, what their shifts would likely be.

Absolute Consistency

One sure problem with developing shift schedulers that are based on rules-of-thumb, are their natural inconsistency. I’ve built a fair number of them, and the amount of testing that needs to be done for these heuristics is off the charts, simply because we are not always certain how the heuristic algorithms will behave. Contact center scheduling and staff planning is a very difficult problem to solve, and it is simply too easy to get results that are inconsistent or unintuitive if using rules-of-thumb algorithms to build schedules.

Making changes to heuristics is difficult, too, as each time constraints are added or changed, the whole behavior of the algorithm might also change. Developers prefer to not add new code to older heuristics, for fear of breaking the code.

That is not the case with true optimization. Adding constraints or changing values will for sure change the results of the math model, but it will always be consistent and clean. The effect from a new constraint on an optimization model is the effect of the new constraint, and not the lingering effect of long forgotten legacy code (as with the heuristic).

What-if Analyses and Multiple Scenarios

Another repercussion of having the consistency of an optimization algorithm is the ability to try different scenarios and understand the trade-offs between them.

Plotting cost versus service level goal is achievable with optimization, because the results from an optimization algorithm will always return consistent results. Resulting graphs will be smooth, consistent, intuitive, and most importantly accurate. Heuristics always introduce the risk that results change, not because the scenario has changed, but because legacy code has not anticipated this sort of scenario. This is a problem with the algorithm, rather than the scenario being considered.

This makes optimization models perfect for performing what-ifs quickly and accurately. It is usually easy to change an MIP and nearly impossible to change a heuristic.

Finally, Speed

MIP’s are usually pretty fast when compared to its heuristic cousins. This is because those store-bought solvers have been in a state of constant improvement by companies and academics for over fifty years. Improving these generic solvers includes a whole field of study in engineering (called operations research), because these solvers are the key to solving many important and interesting problems.
So MIPs are faster, yield lower cost solutions, and have many interesting side-benefits than old timey heuristic solvers. Plus, you get to call yourself a magician if you use one.

Ric Kosiba, Ph.D. is a charter member of SWPP and vice president of Genesys’ Decisions Group. He can be reached at Ric.Kosiba@Genesys.com or (410) 224-9883.