Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Using OR-Tools CP-SAT for Scheduling Problems

atalaykutlay.com

Post reply on HN
Print view View original

21–30 of 31 posts

Re: Using OR-Tools CP-SAT for Scheduling Problems

#21

Post by cchianel »

LPisGood wrote: post #17
cchianel wrote: post #8

Although this post discusses Constraint Programming - Satisfiability (CP-SAT) Solvers and Mixed Integer Problem (MIP) Solvers, it does not discuss Metaheuristic Solvers. Metaheuristic solvers are different in that you don't need to model your problem as a mixed integer problem. Instead, all it cares about is having a function that returns something you can compare. This allows you to model your problem however you li…

I met some lovely Timefold folks at the Informs conference, and I appreciate the work you do. Any idea when a port is coming to new languages?

Currently, no language ports of Timefold Solver are planned. Unfortunately, FFI (foreign function interface) have a terrible performance penalty, and since we would be doing multiple FFI calls for moves, it can easily become 100x slower just from FFI overhead.

This basically means you have two choices:

1. Translate the constraints from the new language to Java bytecode at runtime. 2. Translate the entire solver to a new language.

We did (1) for a bit for CPython, but since CPython bytecode constantly change and break (and is so poorly documented) it was a nightmare to maintain. You can find a blog post of me explaining it a bit more here: https://timefold.ai/blog/java-vs-python-speed. The CPython port is no longer maintained, and has quite a few missing features.

That being said, we have a wide range of ready made models that you can access via an API, which might fit your use case (you can see a list at https://docs.timefold.ai/).

Re: Using OR-Tools CP-SAT for Scheduling Problems

#22

Post by IanCal »

LPisGood wrote: post #19
__MatrixMan__ wrote: post #14

I didn't consider SAT solvers to be AI, but searching for "ortools" points to https://developers.google.com/optimization which has a big "Google AI" indicator on it. Who cares, I thought. But certain managers are now very keen on making a lot of noise about just how effectively their teams are using AI. So I took my four python scripts which together form a pipeline that solves a scheduling problem with OR-Tools and…

SAT solving, constraint programming, and (integer) linear programming are absolutely AI. These are techniques that let computers make smart decisions. Maybe they’re not AI in the way you’ve heard marketing teams use it recently, but they are artificial intelligence nonetheless. If you open any AI textbook written before 2022 there is almost surely a chapter on these methods (c.f. Russel and Norvig’s Artificial Intell…

Strongly seconded (I studied this in 2005-2009).

I don’t think there’s a brilliantly defined line between AI and not AI but it’s relatively key that you define a problem and something else then figures out a solution. Lots of things like shortest path using a* is AI for example. You don’t even need to get to a fuzzy point to consider something AI.

I don’t think people appreciate just how general LLMs are, and how incredibly narrow even the broadest AI systems were really not that long ago.

Re: Using OR-Tools CP-SAT for Scheduling Problems

#23

Post by cchianel »

oulipo2 wrote: post #9
cchianel wrote: post #8

Although this post discusses Constraint Programming - Satisfiability (CP-SAT) Solvers and Mixed Integer Problem (MIP) Solvers, it does not discuss Metaheuristic Solvers. Metaheuristic solvers are different in that you don't need to model your problem as a mixed integer problem. Instead, all it cares about is having a function that returns something you can compare. This allows you to model your problem however you li…

Interesting! Could you give example of problems you're using this for, to get an idea of where they'd be best suited?

You can find a list of quickstarts at https://github.com/TimefoldAI/timefold-quickstarts.

Examples include:

- School Timetabling

- Employee Scheduling

- Conference Scheduling

- Flight Crew Scheduling

Metaheurstics are also very useful for puzzle games; you can quickly run a metaheuristic to generate a difficult but solvable puzzle in less than a second, while only being about 20 lines of code without libraries (but as your scale increases to hundreds of different pieces, you probably want a library so you can use their incremental calculation).

Re: Using OR-Tools CP-SAT for Scheduling Problems

#24

Post by asdfasgasdgasdg »

Filligree wrote: post #3
asdfasgasdgasdg wrote: post #2

In a past life we used OR-Tools for a problem of assigning data shards to serving tasks, where the data shards had heterogenous demands (e.g. some shards were low traffic but demanded sub millisecond latency targets and thus were served from RAM, others were higher traffic but could tolerate being served from flash, etc.). It's insane how expressive this thing is! But the problem got to be so large that we ended up h…

"Multiple minutes" doesn't sound like a lot. With millions of shards, do you really need to regenerate the assignment layout every couple of minutes?

It's important to get it done reasonably quickly because the disks at the time were ephemeral, so how quickly we could solve the problem effectively limited our rolling restart rate.

Re: Using OR-Tools CP-SAT for Scheduling Problems

#26

Post by thisisauserid »

When you have 50 technicians going to 500 sites, that is not a Traveling Salesman Problem. It might seem like a Vehicle Routing Problem but it isn't that either.

Batch a cheap process at night that runs CP-SAT solution. If someone calls in sick, be prepared to run it again with more horsepower so you can update it.

Re: Using OR-Tools CP-SAT for Scheduling Problems

#27

Post by aledem »

LPisGood wrote: post #19
__MatrixMan__ wrote: post #14

I didn't consider SAT solvers to be AI, but searching for "ortools" points to https://developers.google.com/optimization which has a big "Google AI" indicator on it. Who cares, I thought. But certain managers are now very keen on making a lot of noise about just how effectively their teams are using AI. So I took my four python scripts which together form a pipeline that solves a scheduling problem with OR-Tools and…

SAT solving, constraint programming, and (integer) linear programming are absolutely AI. These are techniques that let computers make smart decisions. Maybe they’re not AI in the way you’ve heard marketing teams use it recently, but they are artificial intelligence nonetheless. If you open any AI textbook written before 2022 there is almost surely a chapter on these methods (c.f. Russel and Norvig’s Artificial Intell…

Second that, because, moreover, strictly speaking, none of the technologies existing today is AI. So continuing marketing terms as they are today, all mentioned are totally AI.

Re: Using OR-Tools CP-SAT for Scheduling Problems

#28

Post by currymj »

__MatrixMan__ wrote: post #14

I didn't consider SAT solvers to be AI, but searching for "ortools" points to https://developers.google.com/optimization which has a big "Google AI" indicator on it. Who cares, I thought. But certain managers are now very keen on making a lot of noise about just how effectively their teams are using AI. So I took my four python scripts which together form a pipeline that solves a scheduling problem with OR-Tools and…

for a truly profound and powerful buzzword, you can even honestly and accurately call what you've done "neurosymbolic AI"

Re: Using OR-Tools CP-SAT for Scheduling Problems

#30

Post by jnwatson »

__MatrixMan__ wrote: post #14

I didn't consider SAT solvers to be AI, but searching for "ortools" points to https://developers.google.com/optimization which has a big "Google AI" indicator on it. Who cares, I thought. But certain managers are now very keen on making a lot of noise about just how effectively their teams are using AI. So I took my four python scripts which together form a pipeline that solves a scheduling problem with OR-Tools and…

The rule used to be if you used more than two JOIN clauses, it is AI.
Post reply on HN