How do I use my PTO? Part 1 – Problem Definition

For this series of articles, I want to do something related to a more practical problem we all have… deciding how to use our PTO days. If you’re like me, you have way too many trips on your list that your tiny amount of PTO days can’t possibly support in a year. The best we can do is to choose which trips to take in a smart way; a way where we can leverage weekends and holidays to make our PTO days stretch a bit further.

In Part 1 of this series, I’ll translate our PTO usage problem into an optimization problem. In later parts of this series, we’ll translate our optimization problem into code. We can then solve our problem and get an optimal set of trips to take given our amount of PTO days.

This series is not only to explore a fun topic like using PTO for trips, but also to serve as an example of how to construct and solve a decision problem mathematically and programmatically. Needless to say, this series is for all the math and programming nerds.

The problem statement in plain language

We have a list of potential trips to take, e.g. spend Jan 9-12 on a beach in Hawaii or go climb the Grand Teton August 1-4, and want to choose which set trips to take during the year but avoid going over our PTO day limit.  We need a goal to drive how we choose our trips.  Goals we could have are:

• Maximize the number of PTO days we take
• Maximize the total value of our trips
• Maximize the number of trips we take
• Etc.

For the sake of generality, let’s just say maximizing our total value from the trips we take is our only goal.  We’ll discuss a bit about how we might interpret value, but for now, let’s just assume we have some way to assign a value to each of our trip options.

Defining our decision variables

We have trips.  In our decision problem, we are determining a yes or no answer for each of these trips: yes I should take the trip or no I should not take the trip.  Let be a vector of elements.  Element in is 1 if we should take trip but 0 if we should not take trip .  Mathematically, we describe the elements of as the following:

(1)  

This means that our decision variables are binary.  Since we have binary decision variables, our optimization problem is an integer program. Recognizing our problem as an integer program becomes important when choosing how to solve our optimization problem, which we’ll discuss later.

Defining our constraints

Constraint 1: PTO Day Limit

We continue to set up our optimization problem by mathematically defining our constraints.  For our first constraint, we need to ensure we don’t go over our total number of PTO days.  To do this, we need to count how many non-holiday and non-weekend days a given selection of trips will use.  Let be a vector of 365 elements, one element for each day of the year.  If the th element corresponds to a holiday or a weekend (or a day where we wouldn’t have to take a PTO day to use), that element’s value in is 0, otherwise it is 1.  Let be a  matrix, where the element in row and column is 1 if trip occurs during day , otherwise the element is 0.  Using and along with our decision vector, , our constraint to ensure that we don’t exceed our total PTO days is the following:

(2)  

where  is the total number of PTO days we have for the year.

Constraint 2: Only 1 Trip at a Time

For our second constraint, we want to prevent choosing two trips that lie on the same day.  For this constraint, we can reuse and define as a vector of 365 elements, all of which are 1.  The second constraint is the following:

(3)  

where the righthand side computes the number of trips chosen for a given day.

Constraint 3: No Repeats

In our third constraint, we make sure that we don’t select two trips that have the same itinerary.  For example, we can go climb the Grand Teton in May or in August, but we don’t want our program to select both trips.  Let be a matrix of size , where is the number of unique itineraries in our set of potential trips.  The element in row and column is 1 if trip follows itinerary , and 0 otherwise.  Our third constraint becomes the following:

(4)  

where is a vector of elements, all of which are 1.

Defining our objective

In our problem statement, we say we want to maximize our total value of the trips we take. Let be a vector of element, where element is the value of trip . Therefore, our total value of the trips we select, , is the following:

(5)  

It’s interesting to note that if we let , then our total value is the number of PTO days we take. If , then our total value is the number of trips we take.

Constructing our decision problem

We model our decision problem as an optimization problem. Our objective is the following:

(6)  

subject to the constraints in Equations 1 – 4.

It’s important to note that all of the components of our decision problem are linear and thus is a linear program. Additionally, we noted above that our decision variables are binary, see Eq. 1, so our problem is both a linear and integer program. We’ll need to remember this when we need to select an algorithm to solve our problem in a later part of this series.

Closing remarks

Think of the decision problem we constructed in this article as an initial pass where we account for fundamental elements we care about when choose which trips to take with our PTO days. A part of search for a solution is refining our problem definition to include additional factors we may have initially missed. Potentially, we could solve the problem setup we’ve laid out here but the solution we get still doesn’t seem right. It may recommend back-to-back trips, which we might not want, or recommend to us just one long trip, which we might not want. When this happens, we reflect about what we truly want and adapt our goal or constraints to reflect this. Iteration is a necessary part of the process.