Sorry for being off-topic but I'm still going to use this as an opportunity to vent. This is the most pointless piece of regulation. It's unfortunate non-US users are also subjected to it. What bit of good does it really do for your average user? It's complete overregulation. If users don't want cookies they can turn them off in their browser. The average user doesn't know or care and these incessant popups help nobody.
This is really cool. Is it possible to express the edge coloring constraints simply via integer linear programming? This seems like the type of problem that might be NP-hard but tractable in practice with good heuristics.
You can use heuristics if/when the problem becomes ugly due to various constraints you may impose. The trick is to select heuristics depending on the problem at hand and in a way that their hyperparameter values are selected properly.
Most modern solvers like CPLEX and Gurobi have built-in heuristics [1] that are automatically selected and applied without user intervention. They typically exploit the structure of the problem or encode the experiences of the developers over large problem testsets.
The default heuristics for commercial solvers are actually pretty darned good these days and there's typically no need to hand-pick them.
In the MIP world, they are the secret sauce to fast solution times.
Hyperparameter tuning has been studied for MIPs (many papers written on this), but ultimately they are black box solutions. My experience inclines me to not even consider hyperparameters except as a last resort or unless you know something specific that a hyperparameter can exploit; there are other more high leverage things than can be done.
Random perturbations to the problem have been found to be much more fruitful for forcing a diversity of branch traversal paths and have lead to significant speedups. (M. Fischetti popularized this idea in 2010s [2])
Thank you for providing useful references. Hyperparameter tuning can accelarate CPLEX by 10x and more depending on problem instances (however, it it true that each new version of CPLEX is faster and faster).
What I meant is that in the case if your problem is formulated in a way that the CPLEX and Gurobi cannot treat it (e.g., stochastic and multiobjective) and is not very large-scale, then one can use heuristics. However, the efficiency of the latter will likely depend on hyperparameter settings which need to be set properly.
> What I meant is that in the case if your problem is formulated in a way that the CPLEX and Gurobi cannot treat it (e.g., stochastic and multiobjective) and is not very large-scale, then one can use heuristics. However, the efficiency of the latter will likely depend on hyperparameter settings which need to be set properly.
Ah makes sense... stochastic and multiobjective formulations have superstructures that are not exploited by MIP solvers by default, so hyperparameter tuning might be useful. Creating (exact) heuristics for these superstructures are also an active area of research.
Some solvers like CPLEX are starting to natively support higher level structures like Benders decompositions [1], but they will never support every structural variation.
Yes, that's right. NP-hard doesn't mean intractable in general, though it has acquired that reputation among computer types. Large mixed-integer programming programs (millions of variables) are routinely solved in reasonable times (seconds to less than an hour).
Sure, full or brute-force enumeration algorithms makes you hit the worst case complexity every time.
However, most commercial mixed integer solvers don't use brute-force enumeration. Instead they pre-analyze the problem, and then employ a boatload of mathematical techniques--including heuristics--which exploit problem structure and prune off non-solutions and helps the solver reach a solution fairly quickly on average. (luck is involved, of course)
Hi, I am an algorithm developer at optibus. So I can explain the logic of the use of heuristics in this case.
We actually use MIP solvers for many of our problems, and are quite proficient with it.
However, mass transit problems, especially in large cities, tend to be highly complex for CPLEX or any other solver to solve out of the box. There are billions of variables, and many global constrains which involves: vehicle types, multiple depots, fueling and charging considerations, driver unions and regulation, and hundreds of others.
Simply using generic solver (though very advanced one) works well for small instances but doesn’t scale well for medium to large ones. Just fitting the model in memory is challenging. We, at Optibus, are distributing the problem using massive cloud resources and dedicated algorithms, and use a mixture of this, MIP solvers, and the heuristics discussed in the article.
We wanted to keep our competitive edge, but hopefully, we may write a blog post about it in the near future.
Makes sense. MIPs are good for getting to rigorous optimality, but right now they have limits to their scaling (every binary variable and every inequality constraint you add increases the complexity of the problem).
Your experiences track those of the folks working in airline fare pricing (e.g. ITA software, now Google Flights).
If you are willing to give up strict optimality (or small MIP gap), any number of greedy and / or embarassingly parallel algorithms will likely get you reasonable (maybe not optimal, but good enough) results in a shorter amount of time. Plus, you can do much more massive scale out.
1) What are the metrics that mass transit operators tend to optimize for? Do you think they are in line with improving the service to customers?
2) How much is "dependability" of a mass transit service a metric that operators are interested in?
Intuitively I feel that there are places (e.g. Chicago) where I know that I can get out of the house, get the bus/train, and get to my destination with little variance in arrival time.
Others (like SF), where the variance on the arrival time seems much higher: e.g., generally related to unexpected delays while waiting for train/bus.
Do you think it's possible to optimize on such factors?
You may formulate it as a multi-objective problem where you minimize the estimated time of the trip and your uncertainty of this estimate. Often, the two objectives are conflicting. As a user, the software should show you a Pareto set of optimal solutions where each solution has its duration and uncertainty. Then it is up to you which solution to pick. I hope they have this feature at optibus.
It is planning that was done to prepare for when BART service reaches Santa Clara county, and how the bus network will need to be reorganized. In the documents, you can see how they looked at different plans, covering different levels of geography vs. population.
Thanks! The design tradeoff between ridership and coverage is very interesting, and ripe for political discussion.
I wonder if there are opportunities for working with on-demand ride companies for coverage, while focusing infrastructure on high-ridership corridors. Fairness of access for disadvantaged people would be a problem to solve.
Hi, I am actually an algorithm dev at Optibus, so I can provide a few insights.
1) Naturally, mass transit operators optimize for highest payoff - so they would try to use the least number of buses, least number of drivers' work hours, least deadheads etc. However, the government rightfully enforces both driver work regulations (enough rest, coffee breaks etc) and highly penalize them for service unreliability - each city is different, but in general - if a bus is late for more than X minutes\doesn't show up, the operator will get a heavy fine. Also - if consumer satisfaction is low, this operator will not get to operate the city's buses again, so they try to keep them reasonably high.
2) for these reasons, service reliability (or dependability) is animportant factor. in general - schedulers should have a few reserve vehicles and drivers, so that in case of a delayed bus - they can replace it with their reserve.
Here, at Optibus, we have started a pilot where after looking at historical data, we use AI to predict which trips are likely to be delayed. and by how much. With our predictions we first warn the operator that the estimate for this trip is questionable, and more importantly, build the schedule accordingly - give more time spread between these trips and the next scheduleued trip on this vehicle, so that this delay will not affect subsequeent trips and cause a cascade of delays. This way - we make the schedule more robust.
so far it looks promising
Oh gosh what a mess of an article... completely undecipherable. There are many kinds of universality... this article concerns the flavor where many kinds of physical systems appear to be shockingly well-modeled as random matrices. But doesn't manage to convey a single kernel of what this __means__, it just plops information on you like a high-school math class. Tells you the name of things and some basic properties, leaves you with the misleading impression that you have come away with some better understanding...
Here's something more substantive to chew on, about universality in transitions to chaos: [1]. Turns out that many chaotic systems 'descend' into chaos in the very same way. What does that really _mean_? I have no idea, but at least this discussion rigorously explains what this universality class is, instead of dousing you with feel good science-hoodoo-voodoo quotes.
The edges between the trips mean that one trip can be performed after the other on the same vehicle.
The costs on these edges represent the distance of the idle trip - if they are far away - it would be more expensive.
The depot pull outs are connected to the earlier trips,and depot pull ins to the later trips. The cost of these edges also represents the distance of the depot from this trip.
40 comments
[ 3.7 ms ] story [ 93.4 ms ] threadIt is an EU policy, not US (http://ec.europa.eu/ipg/basics/legal/cookies/index_en.htm).
I have them blocked but still they are awful.
The default heuristics for commercial solvers are actually pretty darned good these days and there's typically no need to hand-pick them.
In the MIP world, they are the secret sauce to fast solution times.
Hyperparameter tuning has been studied for MIPs (many papers written on this), but ultimately they are black box solutions. My experience inclines me to not even consider hyperparameters except as a last resort or unless you know something specific that a hyperparameter can exploit; there are other more high leverage things than can be done.
Random perturbations to the problem have been found to be much more fruitful for forcing a diversity of branch traversal paths and have lead to significant speedups. (M. Fischetti popularized this idea in 2010s [2])
[1] https://resources.mpi-inf.mpg.de/conferences/adfocs-03/Slide... Also: http://transp-or.epfl.ch/zinal/2017/slides/group5.pdf
[2] https://mat.tepper.cmu.edu/blog/index.php/2012/09/25/fischet...
What I meant is that in the case if your problem is formulated in a way that the CPLEX and Gurobi cannot treat it (e.g., stochastic and multiobjective) and is not very large-scale, then one can use heuristics. However, the efficiency of the latter will likely depend on hyperparameter settings which need to be set properly.
Ah makes sense... stochastic and multiobjective formulations have superstructures that are not exploited by MIP solvers by default, so hyperparameter tuning might be useful. Creating (exact) heuristics for these superstructures are also an active area of research.
Some solvers like CPLEX are starting to natively support higher level structures like Benders decompositions [1], but they will never support every structural variation.
[1] Benders: https://www.ibm.com/support/knowledgecenter/en/SSSA5P_12.7.0...
Sure, full or brute-force enumeration algorithms makes you hit the worst case complexity every time.
However, most commercial mixed integer solvers don't use brute-force enumeration. Instead they pre-analyze the problem, and then employ a boatload of mathematical techniques--including heuristics--which exploit problem structure and prune off non-solutions and helps the solver reach a solution fairly quickly on average. (luck is involved, of course)
Your experiences track those of the folks working in airline fare pricing (e.g. ITA software, now Google Flights).
If you are willing to give up strict optimality (or small MIP gap), any number of greedy and / or embarassingly parallel algorithms will likely get you reasonable (maybe not optimal, but good enough) results in a shorter amount of time. Plus, you can do much more massive scale out.
1) What are the metrics that mass transit operators tend to optimize for? Do you think they are in line with improving the service to customers?
2) How much is "dependability" of a mass transit service a metric that operators are interested in?
Intuitively I feel that there are places (e.g. Chicago) where I know that I can get out of the house, get the bus/train, and get to my destination with little variance in arrival time.
Others (like SF), where the variance on the arrival time seems much higher: e.g., generally related to unexpected delays while waiting for train/bus.
Do you think it's possible to optimize on such factors?
It is planning that was done to prepare for when BART service reaches Santa Clara county, and how the bus network will need to be reorganized. In the documents, you can see how they looked at different plans, covering different levels of geography vs. population.
I wonder if there are opportunities for working with on-demand ride companies for coverage, while focusing infrastructure on high-ridership corridors. Fairness of access for disadvantaged people would be a problem to solve.
For example, this is a post about bus branching: https://pedestrianobservations.com/2018/07/14/bus-branching/
Here's something more substantive to chew on, about universality in transitions to chaos: [1]. Turns out that many chaotic systems 'descend' into chaos in the very same way. What does that really _mean_? I have no idea, but at least this discussion rigorously explains what this universality class is, instead of dousing you with feel good science-hoodoo-voodoo quotes.
[1] http://www.cns.gatech.edu/PHYS-4267/UFO.pdf
Explaining enough topology for a typical reader to get it is a hard task. As in really hard.
I don't know if it's poorly written or if my brain is deteriorating.