Hacker News Reader

Comment by pg_bot | Hacker News Reader

Based on my knowledge of operations research, there is likely no AI involved in solving any of these problems. This is just a pure math problem, one that someone who knows excel really well could solve. While you may not understand the math involved, that doesn't mean that this is a black box.

This type of work has been put into practice for longer than the author has been alive. I don't think we need to reflect upon the changes it will bring to society since it's already old hat. I will admit that "What the Boston School Bus Schedule Can Teach us About Junior year Undergraduate Mathematics" doesn't have the same ring to it.

View on HN

Scheduling with constraints is a significantly more difficult problem than you suggest - well beyond junior year and the really general stuff holds open research problems.

You are right about the popular (and, increasingly, technical also) mis-use of the term "AI" but that ship sailed a long time ago.

I am speaking from personal experience. Bus scheduling with constraints was literally the textbook problem I was solving in my Operations Research class during my Junior year in undergrad. I would not classify myself as a genius, did not go to an Ivy league school, and I could do it then. It was on the harder end of the spectrum for my classes, but approachable to any undergrad studying mathematics. If you can pass a linear algebra class, you can learn how to solve these types of problems.

Only for certain types of constraints, however.

I am also speaking from experience. It's not my area of mathematics but I have a passing familiarity.

There are simplified problems that can be presented to undergrads, sure - just like most areas. Intro courses often use a toy version of this to show integer programming and the like. But there is as reason these are "toy" version - some of the general variants are NP-hard and have connections to interesting and open problems. Many real world variants are not trivial to undertake.

On a general note - if you hear someone who is even slightly plausibly qualified say "Problem X is hard" and you think "Huh, I solved problem X in undergrad" - the overwhelmingly most likely reason is that you aren't, in fact, talking about the same "problem X". This can of course be due to the method of communication (e.g. science journalism)

I agree, solving for the optimal solution is generally an NP hard problem when dealing with real world constraints. The real world is not a word problem in a math textbook.

In practice you can often get away with improving an existing system instead of finding the "best" solution to the problem. This is what pragmatic people do, and it is often a lot easier than we think it is.

If you frame the problem as "finding the best possible solution to the bus routing problem factoring in all the needs of the populace", I would agree that's a very hard problem. If you frame the problem as "can we improve the existing Boston bus routing system", it will likely be a lot easier. Always remember that perfect is the enemy of done.

You, like the other poster, seem to be assuming that nobody has tried "can we improve the existing ..." using the obvious tools. I find this attitude both puzzling and patronizing of the people involved. Without specific knowledge, is seems far more likely the obvious things have been tried by reasonably intelligent people.

As you say, it's what pragmatic people do (and it's usually still more complicated than the intro textbook versions)

Now I have no specific knowledge of this particular problem, but the article does suggest it is something that has been tried before (rescheduling) and failed for various reasons. I'll give them the benefit of the doubt, why won't you?

Really I'm objecting to the idea that "if only we could have found a math undergrad, this would have been improved years ago". That's a particularly naive view.

It is my opinion that these initiatives fail for political reasons rather than on their merit. There are perverse incentives for all interested parties to avoid changing the status quo. Anytime you find a cause with diffuse costs and concentrated benefits it's going to be an uphill battle to get things implemented. As indicated by the article, math was not the barrier to implementing better scheduling. We are able to do the math.

That's quite a different issue, but I agree that this is a common failure mode.

i agree the word “AI” ought not be used to describe this.

the thing that makes these sorts of problems not quite so simple is that there are fairness constraints, not just constraints on routes and schedules. there may also be a requirement that the solution should be chosen in such a way that a rational agent has no incentive to lie about their true preferences. the best way to achieve these many conflicting goals is definitely not settled.

Sure, an inclusive headline is "What the Boston School Bus Schedule Can Teach us About letting algorithms decide". Because AI or upper division math, the decision was consigned to a process that is opaque to the average parent. And the opaqueness more or less conceals basic tradeoffs.

The school has figured out that starting HS late-ish and letting all student out before dark provides the best situation for students.

But if all school levels start at the same time, the district has would have to have a bunch of school buses and drivers that wouldn't be used other times.

To avoid all this "waste", the district has to decide which schools to shove into some other, worse schedule. They thus came up with a algorithm to minimize the amount of bad-scheduling but which maintains the existence of bad-schedules. And when it sent an entirely different group than before into the bad-scheduled situation, naturally that group complained - it didn't help these were wealthier, whiter groups with influence.

Sure, you thus have more affluent people saying they didn't want to be the one sacrificed here. But you also ask, why sacrifice anyone? Why not bite the bullet and have a good, standard schedule for all schools? You'd offending the modern god of efficiency but you'd actually be aiming for a greater good.

The article talks about Trolley Car Problems a bit and how people relate to algorithms "solving" these. The thing is instead of saying "that there are sacrifices is given, now we must decide who", which guarantees divisiveness, one could say "let us make choices as a society which mean that no person a priori need be sacrificed."

"that there are sacrifices is given, now we must decide who", which guarantees divisiveness, one could say "let us make choices as a society which mean that no person a priori need be sacrificed."

Your first quote describes reality, your second is nonsense. If there were an outcome where everyone's needs are met and nothing need be sacrificed, there would be no opposition to the changes. Every decision comes at a cost, we don't have unlimited resources so we should reach for tools that attempt to maximize what we are willing to spend. If you believe that no one needs to sacrifice in order to solve society's problems, you are living in a fantasy.

Your first quote describes reality, your second is nonsense. If there were an outcome where everyone's needs are met and nothing need be sacrificed, there would be no opposition to the changes.

Basic income is system that would approximately guarantee all people's basic needs are met yet there is certainly opposition to it.

Your proposals sound to me like someone going to a casino with a surefire winning strategy assuming they have more money than the house.

Please explain (or cite a source that does) how you roll out a basic income in a way that doesn't create new schemes that leave more money on the table to be hoovered up by the oligarchic corporations. I strongly biased to believe that if you add resources arbitrarily to a human society, then a segment of the population will, will, find a way to capture them.

I am not even a proponent of basic income.

The point is that in policy today, "everyone's needs will be met" isn't an automatically a winning argument.

Off topic, but as long as I trust the state, I trust basic income.

I put different amount of faith in different states, but not very much in any state. Not in the long run. The problem is, the state is going to dictate more and more conditions for receiving that income. Couple it with oligarchic interests and no good can come of it.

Problem is, I don't see much good coming from our current systems either, subverted as we speak.

It is true that such problems /can/ be solved via mathematical linear programming (for those coming outside math circles, please note that the term programming here has nothing to do with coding) and this is how they are usually presented in academia. However, in practice, it is not something one would be advised to do. Usually, the complexities of the real world routing and scheduling make it impossible to solve these models of practical size. Therefore, numerous heuristic and metaheuristic algorithms have been proposed and are usually used in practical applications. These usually are sound familiar to those that have some experience with "old" AI: genetic algorithms, ant colony systems, simulated annealing, and even neural networks have been succesfully applied to provide "good enough" solutions to these problems.

I do machine learning and stats for a living. You could describe practically all of what's called AI by the popular press in the same way. Mostly "complex algorithms that classify/predict/optimize/decide between things." The lesson is still there and is still applicable to those things.

I am extremely interested how to solve routing problem with Excel. Can you share few links or articles?

Bus routing is just a variant of the vehicle routing problem (VRP), which itself is a generalization of traveling salesman problem (TSP) but with multiple salespersons doing the traveling.

There is an Excel sheet for solving such problems, and if one wishes to go further, the basic heuristic and metaheuristic algorithms are not that hard to implement either. http://people.bath.ac.uk/ge277/index.php/vrp-spreadsheet-sol...

With these keywords you are welcome to fall into this rabbit hole as deep as you wish. I promise to greet you on my way up (currently finishing my PhD on the topic).

Thanks!

Reply on news.ycombinator.com