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

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

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

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

    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

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

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.

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

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.

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

Archipelago GitHub: https://github.com/ArchipelagoMW/Archipelago

[1] https://stackoverflow.com/a/13109557

[2] https://solver.timefold.ai/

- In Python 3.10, jumps changed from absolute indices to relative indices

- In Python 3.11, cell variables index is calculated differently for cell variables corresponding to parameters and cell variables corresponding to local variables

- In Python 3.11, MAKE_FUNCTION has the code object at the TOS instead of the qualified name of the function

For what it's worth, I created a detailed behaviour of each opcode (along with example Python sources) here: https://github.com/TimefoldAI/timefold-solver/blob/main/pyth... (for up to Python 3.11).

- The vast majority of code generation would have to be dynamic dispatches, which would not be too different from CPython's bytecode.

- Types are dynamic; the methods on a type can change at runtime due to monkey patching. As a result, the compiler must be able to "recompile" a type at runtime (and thus, you cannot ship optimized target files).

- There are multiple ways every single operation in Python might be called; for instance `a.b` either does a __dict__ lookup or a descriptor lookup, and you don't know which method is used unless you know the type (and if that type is monkeypatched, then the method that called might change).

A JIT compiler might be able to optimize some of these cases (observing what is the actual type used), but a JIT compiler can use the source file/be included in the CPython interpreter.

- CPython Bytecode is far from stable; it changes every version, sometimes changing the behaviour of existing bytecodes. As a result, you are pinned to a specific version of Python unless you make multiple translators.

- CPython Bytecode is poorly documented, with some descriptions being misleading/incorrect.

- CPython Bytecode requires restoring the stack on exception, since it keeps a loop iterator on the stack instead of in a local variable.

I recommend instead doing CPython AST → PySM Assembly. CPython AST is significantly more stable.

- In OR Tools, you need to write your constraints as mathematical equations. You can only provide your own function in a few scenarios, such as calculating the distance between two points. This allows OR Tools to eliminate symmetries and calculate gradients to improve its solution search. In Timefold, your constraints are treated like a black box, so your constraints can use any function and call any library you like (although you shouldn't do things like IO in them). However, since said constraints are a black box, Timefold is unable to eliminate symmetries or calculate gradients.

- In OR Tools, you have very little control in how it does its search. At most, you can select what algorithm/strategy it uses. In Timefold, you have a ton of control in how it does its search: from what moves its tries to adding your own custom phases. If none are configured, it will use sensible defaults. That being said, certain problems strongly benefit from custom moves.

- In OR Tools, you do not need to create custom classes; you create variables using methods on their domain model classes. In Timefold, you need to define your domain model by creating your own classes. This adds initial complexity, but it makes the code more readable: instead of your variable being an int, it is an Employee or a Visit. That being said, it can be difficult for someone to design an initial model, since it requires an understanding of the problem they are solving.

All in all, when using Timefold, you need to think in a more declarative approach (think Prolog, SQL, etc). For example, let say you have a room assignment problem where a teacher can only teach at a single room at once, and minimize room changes. In Timefold, it may look like this:

    # Typically would be stored in a parameterization object, but a global var
    # is used for brevity
    teacher_count = 3
    
    @planning_entity
    @dataclass
    class Room:
        id: Annotated[int, PlanningId]
        date: int
        name: str
        # This can also be a Teacher object, but str is used for brevity here
        teacher: Annotated[str, PlanningVariable] = field(default=None)
    
    
    @planning_solution
    @dataclass
    class Timetable:
        rooms: Annotated[list[Room], PlanningEntityCollectionProperty]
        teachers: Annotated[list[str], ValueRangeProvider]
        score: Annotated[HardSoftScore, PlanningScore] = field(default=None)


    @constraint_provider
    def timetable_constraints(cf: ConstraintFactory):
        return [
            cf.for_each_unique_pair(Room, Joiners.equal(lambda room: room.date), Joiners.equal(lambda room: room.teacher))
              .penalize(HardSoftScore.ONE_HARD)
              .as_constraint('Teacher time conflict'),
            cf.for_each_unique_pair(Room, Joiners.equal(lambda room: room.teacher))
              .filter(lambda a, b: a.name != b.name)
              .penalize(HardSoftScore.ONE_SOFT)
              .as_constraint('Minimize room change')
        ]


    solver_config = SolverConfig(
        solution_class=Timetable,
        entity_class_list=[Room],
        score_director_factory_config=ScoreDirectorFactoryConfig(
            constraint_provider_function=timetable_constraints
        ),
        termination_config=TerminationConfig(
            spent_limit=Duration(seconds=5)
        )
    )

    solver_factory = SolverFactory.create(solver_config)
    solver = solver_factory.build_solver()
    problem: Timetable = build_problem()
    solver.solve(problem)

    teacher_count = 3
    problem: Timetable = build_problem()
    model = cp_model.CpModel()
    objective = []
    room_vars = [cp_model.model.new_int_var(0, teacher_count - 1, f'room_assignment_{i}' for i in range(len(problem.rooms)))]
    room_vars_by_date = {date: [room_vars[i] for i in range(len(problem.rooms)) if problem.rooms[i].date == date] for date in {room.date for room in problem.rooms}}
    room_vars_by_name = {name: [room_vars[i] for i in range(len(problem.rooms)) if problem.rooms[i].name == name] for name in {room.name for room in problem.rooms}}
    for date, date_vars in room_vars_by_date.items():
        model.AddAllDifferent(date_vars)
    for name, name_vars in room_vars_by_name.items():
        for assignment_1 in names_vars:
            for assignment_2 in names_vars:
                if assignment_1 is not assignment_2:
                    objective.add(assignment_1 != assignment_2)
    
    model.minimize(sum(objective))
    solver = cp_model.CpSolver()
    status = solver.solve(model)

Using IPC for all internal calls would probably take significant overhead; the user functions are typically small (think `lambda shift: shift.date in employee.unavailable_dates` or `lambda lesson: lesson.teacher`). Depending on how many constraints you have and how complicated your domain model is, there could be potentially hundreds of context switches for a single score calculation. It might be worth prototyping though.