Miami Metrorail meets Python

Tallys Yunes recently posted his formulation of the "Buying Metrorail Tickets in Miami" optimization problem. His implementation is in Excel, but he kindly offered to fly me+1 out for a nice winter weekend in Miami if I would only reproduce the problem using Python and Gurobi.

I admit its possible I'm mis-remembering this part of our Twitter exchange, but I went ahead and coded the example up anyway.

Tallys sets up the problem better than I can, so I'll dive straight into some math. I'm using the same data and variable names as Tallys, but I've reformulated the problem slightly to make for simpler code.

Here is the objective function. This captures the goal of visiting the ticket office as little as possible.

The following constraint computes the dollar amount leftover after paying for the ticket office visits and going on n one-way trips. Using a KPI helper variable here makes my formulation a little simpler.

From here we address the three flavors of the problem that Tallys discusses.

1. The original version, where L >= a >= 0 is enforced. This is the default mode, and corresponds to the "Amount Leftover Constraint" parameter being set to "Upper Bound".
2. The version where L = a is enforced. This was used to generate Tallys's heat-map diagram which my code and sample data reproduces (with a few exceptions, see below). In my code, this corresponds to the "Amount Leftover Constraint" parameter being set to "Equality".
3. The "leftover multiple" flavor of the model. In my code, this corresponds to the "Amount Leftover Constraint" parameter being set to "Upper Bound With Leftover Multiple Rule". I implemented this mode as follows.

• An integral variable k is introduced.
• The constraint a=2.25 k is applied.
• The original L >= a >= 0 is enforced.

My code solves not one MIP but several. For each pair of n and L values, a distinct MIP problem is solved. The n values are read from the Number Of One Way Trips table, and the L values are read from the Amount Leftover table. The parameters table can be used to control not only the solve mode but also the one-way price. The Load Amounts table is used to read the different dollar amounts that can be added to a metro-pass.

My code was able to reproduce Tallys's heat map result almost perfectly. The only inconsistency is that while Tallys explicitly identifies two infeasible sub-problems (which my code does reproduce) his heat map also has 27 empty white cells. My code is able to find feasible solutions for each of those sub-models. I double checked (using, naturally, a Jupyter-style Python notebook) that all of the records in my Load Amount Summary report do indeed correspond to feasible solutions. I assume everything is working properly, and those 27 empty cells are just a typo.

Although the metrorail.py file only needs Python, gurobipy and ticdat to run on your computer, it is also configured to be loadable as an instant-app on the Opalytics Cloud Platform. I demonstrate this here, to include creating the "nearly consistent" heat-map result from standard Opalytics reporting functionality.

Tallys, thanks for the fun problem! I'll be sure to buy you a drink the time I'm in Miami (regardless of how I get there ;)