Miami Metrorail meets Python
Snakes on a Train

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

要查看或添加评论,请登录

Peter Cacioppi的更多文章

  • The Paint-by-Numbers Anti-Art of Modeling

    The Paint-by-Numbers Anti-Art of Modeling

    I recently listened to a Gurobi webcast about generative AI. I can’t remember anything about it, other than Irv Lustig…

    5 条评论
  • My two cents on LLMs and Optimization

    My two cents on LLMs and Optimization

    I’d like to weigh in briefly on a Harvard Business Review (HBR) article by former colleague, Prof. David Simchi-Levi…

    9 条评论
  • Blood, sweat and tears

    Blood, sweat and tears

    Jean-Francois Puget, a friend and former colleague, recently kicked off an interesting conversation with the following…

    3 条评论
  • Building Pythonic MIPs with AMPL

    Building Pythonic MIPs with AMPL

    Update Sadly, as of June 2021, AMPL has failed to follow through on their early promise of connecting their modeling…

    4 条评论
  • Connect OPL to Python with ticdat

    Connect OPL to Python with ticdat

    FYI Subsequent to this post, I've worked with combining AMPL and Python and have found this approach works even better…

    1 条评论
  • ML and MIP Gurobi Webinar Follow Up

    ML and MIP Gurobi Webinar Follow Up

    I recently had the pleasure of collaborating with Dr. Daniel Espinoza on a Gurobi webinar discussing Machine Learning…

  • We few. We happy few.

    We few. We happy few.

    I admit to having strong opinions. As I’ve mentioned in previous blogs, I think Python is the right programing language…

    2 条评论
  • Why Python for MIP? Four Key Points

    Why Python for MIP? Four Key Points

    FYI - I've since recanted the dogmatic positions outlined below. Please go here https://t.

    4 条评论
  • Fantasy Footballers are Nerds Too

    Fantasy Footballers are Nerds Too

    There are two types of nerds. Fantasy football nerds, and Dungeon and Dragons nerds.

  • Retire the Five Grand Old Men

    Retire the Five Grand Old Men

    Every two years, INFORMS gives out an Impact Prize “to recognize contributions that have had a broad impact on the…

社区洞察

其他会员也浏览了