cchianel · HackerTrans

17 giờ trướcdiscuss

Look at it this way: I am arguing against "No Free Lunch theorem says an optimization algorithm cannot solve all problems because for some problems it performs worse than other algorithms"; I am arguing approximate solutions are good enough, and in practice a wide variety of optimization algorithms find good enough solutions despite being worse than others algorithms for the problem class. Moreover, some algorithms/solvers can be configured, which fundamentally change the direction the solving takes (for example, a custom phase that uses your domain knowledge of the particular problem to get a good enough initial solution to be improved upon) (Side note: I am NOT affiliated with this post/project; from the website I don't really see a value add for it, especially since the site is lacking so many details).

cchianel

20 giờ trướcdiscuss

I personally disagree with "no free lunch"; (for the uninitiated, "no free lunch" refer to the fact for any deterministic algorithm, there exist a problem that will force the algorithm to go through the entire solution space to find the optimal solution, with every single other possible algorithm beating it (https://en.wikipedia.org/wiki/No_free_lunch_theorem)). For many planning problems, finding a good enough solution is sufficient, and there are many optimization algorithms that work for a wide variety of problems and provide a good enough solution in reasonable time. Different algorithms are better for different problems (ex: Metaheuristic (ex: Late Acceptance) Solvers beats MIP Solvers on vehicle routing, whereas MIP Solvers beat Metaheuristic Solvers on Employee Scheduling and Bin Packing. But both Metaheuristic and MIP Solvers provider good enough solutions for both vehicle routing and bin packing.

cchianel

20 giờ trướcdiscuss

It seems to just be a wrapper over or-tools and other solvers from their landing page, with the difference being it run on their servers versus your hardware. Their website does not mention what hardware is allocated per model (which determine speed of solving) nor any limit on model size.

cchianel

13 ngày trướcdiscuss

Think of WASM as a kinda universal library target. You can compile C, Rust, C#, Java to WASM, and then you can use it in a different language from the source. This way, Java can run C or Rust code without going through a FFI (foreign function interface). From the article, one example is porting tree-sitter (a C library) to Java by first compiling it to WASM, then use Endive to access its function.

As an example of how it can be used, you can look at https://github.com/Christopher-Chianelli/timefold-wasm-servi... and https://github.com/Christopher-Chianelli/timefold-wasm-c-cli..., which was an experiment I did to try using C code inside Timefold Solver (a Java library that can be used to solve constraint problems like Employee Scheduling and Vehicle Routing).

cchianel

2 tháng trướcdiscuss

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

cchianel

2 tháng trướcdiscuss

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/).

cchianel

2 tháng trướcdiscuss

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 like. Some metaheurstic techniques include Simulated Annealing, Late Acceptance Local Search, and Tabu Search.

Metaheuristic solvers may not generate optimal solutions (after all, by their nature, they don't know the structure of the problem), but they generate "good enough" and "close to optimal" solutions. Metaheurstic solvers tends to beat MIP and CP-SAT for VRP, whereas MIP and CP-SAT are better for bin packing.

If you want to try using a Metaheuristic solver, I can recommend Timefold, which allows you to define your constraints using your domain objects in an incremental matter (it has SQL/Java-Streams like syntax, which in my opinion, is more readable than formulas) (disclosure: I work for Timefold).

cchianel

7 tháng trướcdiscuss

I haven't; from a quick reading, InfoBax is for when you have an expensive function and want to do limited evaluations. Timefold works with cheap functions and does many evaluations. Timefold does this via Constraint Streams, so a function like:

    var score = 0;
    for (var shiftA : solution.getShifts()) {
        for (var shiftB : solution.getShifts()) {
            if (shiftA != shiftB && shiftA.getEmployee() == shiftB.getEmployee() && shiftA.overlaps(shiftB)) {
                score -= 1;
            }
        }
    }
    return score

usually takes shift * shift evaluations of overlaps, we only check the shifts affected by the change (changing it from O(N^2) to O(1) usually).

That being said, it might be useful for a move selector. I need to give it a more in depth reading.

cchianel

7 tháng trướcdiscuss

I thought "No Free Lunch Theorem" was a joke from its name (although I should know better since "Hairy Ball Theorem" exists).

So if I understand correct, it states that all optimization algorithm must choose an order to evaluate solutions, and the faster it evaluates the "best" solution, the "better" the algorithm.

For example, say the search space is {"a", "b", "c"} and the best solution is "c". Then there are 3! (6) ways to evaluate all solutions:

"a", "b", "c"

"a", "c", "b"

"b", "a", "c"

"b", "c", "a"

"c", "a", "b"

"c", "b", "a"

(of course, in a real problem, the search space is much, MUCH larger).

The way Timefold tackles this is move selectors. In particular, you can design custom moves that uses knowledge of your particular problem which in turn affect when certain solutions are evaluated. Additionally, you can design custom phases that runs your own algorithm and then pass the solution found to local search. One of the projects we are working on currently is the neighborhood API, to make it much easier to write your own custom moves. That being said, for most problems that humans deal with, you don't need to configure Timefold and just work with the defaults (which is best-fit followed by a late acceptance local search with change and swap moves).

For what it's worth: metaheuristics solvers tend to be better than linear solvers for shift scheduling and vehicle routing, but worse for bin packing. But it still works, and is still fast.

cchianel

7 tháng trướcdiscuss

By 1% of optimal, I was giving an example percentage to clarify there are solutions that exists, that are almost as good as optimal, that can be found in reasonable amount of time.

There cannot be a guarantee to find a solution to a given percentage worse than optimal for a fully general problem, since you would need to know optimal to give such a guarantee (and since the problem fully general, you cannot use the structure of the problem to reduce it).

Most constraint problems have many feasible solutions, and have a way to judge how much worse or better one solution is to another.

There are good and bad way to write constraints.

One bad way to write constraints is score traps, where between one clearly better solution has the same score as a clearly worse solution.

For example, for shift scheduling, a solution with only 1 overlapping shift with the same employee is better than a solution with 2 overlapping shifts with the same employee.

A bad score function would penalize both solutions by 1, meaning a solver have no idea which of the two solutions are better.

A good score function would penalize the schedule with 1 overlapping shift with the same employee by 1, and the schedule with 2 overlapping shifts with the same employee by 2.

The class of problems I am talking about is the class of problems where you can assign a score to a possible solution, with limited score traps.

Timefold has no guarantees about finding a solution in reasonable time (but unless you done something terribly wrong or have a truly massive dataset, it finds a good solution really quickly 99.99% of the time). Instead, you set the termination condition of the solver; it could be time-based (say 60 minutes), unimproved time spent (solve until no new better solutions are found after 60 minutes), or the first feasible solution (there are other termination conditions that can be set).

cchianel

7 tháng trướcdiscuss

That depends; do you want the optimal solution?

If so, I agree it is impossible for a fully general problem solver to find the optimal solution to a problem in a reasonable amount of time (unless P = NP, which is unlikely).

However, if a "good enough" solution that is only 1% worse than optimal works, then a fully general solver can do the job in a reasonable amount of time.

One such example of a fully general solver is Timefold; you express your constraints using plain old Java objects, so you can in theory do whatever you want in your constraint functions (you can even do network calls, but that is extremely ill-advised since that will drastically slow down score calculation speeds).

Disclosure: I work for Timefold.

cchianel

7 tháng trướcdiscuss

Some additional optimization resources (for metaheuristics, where you only have the objective/score function and no derivative):

- "Essentials of Metaheuristics" by Sean Luke https://cs.gmu.edu/~sean/book/metaheuristics/

- "Clever Algorithms" by Jason Brownlee https://cleveralgorithms.com/

Timefold uses the metaheuristic algorithms in these books (Tabu Search, Late Acceptance, Simulated Annealing, etc.) to find near-optimal solutions quickly from a score function (typically defined in a Java stream-like/SQL-like syntax so score calculation can be done incrementally to improve score calculation speed).

You can see simplified diagrams of these algorithms in action in Timefold's docs: https://docs.timefold.ai/timefold-solver/latest/optimization....

Disclosure: I work for Timefold.

comments