I prototyped a system to orchestrate maintenance on fleets of devices. The idea was that, rather than telling the system how to do it (e.g. workflows to roll out an update), you'd tell the system what you wanted (e.g. up to date machines), what actions were available (e.g. pull a machine from rotation, apply an update), and what constraints to obey (e.g. X of Y machines must be online, don't work in more than two regions simultaneously.)

I modeled a few scenarios like that in Picat and had it generate optimal plans. It worked swimmingly for pet problems, but predictably fell over scaling to cattle sizes. Planning is EXPTIME after all (e.g. Towers of Hanoi).*

Picat does have an escape hatch - you can define heuristics - so I built a random forest of state predicates and trained a naive Bayes classifier to predict fruitful paths. But even with that, and symmetry breaking constraints, and even some hierarchical planning, I couldn't make it work without too much handholding.

It's still AI winter for the classic GOFAI problem domains, apparently. :/

* maybe not, actually, if you reformulate the planning problem as returning a polynomial-time generator of a potentially exponentially long plan

CPLEX, Xpress, GUROBI, and Hexaly all come to mind. Hexaly is really good for scheduling problems and things like vehicle routing. You typically access these via an API they offer you for the popular industry languages. This approach seems to make a lot more sense to me than having a dedicated solver language that isn't as good for all the general purpose stuff. Calling GUROBI from Python is a breeze as is all the standard stuff in Python. Mosek is a lot cheaper than GUROBI, but both of it's APIs are extremely low level and the performance isn't as good as GUROBI either.

If you're lucky enough to get a problem that's basically stable over time, where the problem structure doesn't change, then maybe you can get improved solutions rapidly at industrial scale replacing use of a black-box MIP solver like Gurobi/CPLEX with a decomposition that exploits the problem structure, where sub-problems can be solved by some specialized graph algorithm or heuristic or brute force (if they all have bounded size), and the general purpose MIP/LP solver can be left with the job of figuring out how to deal with the shared resources and constraints that bind the subproblems together. The downside to a highly specialised custom solver is that it usually isn't flexible to changing requirements (unless you get very lucky) -- a slight change in business rule can break the problem structure that underpins the entire solution approach.

While this is generally true, there are some exceptions. I recently compared the performance of CP-SAT vs CPLEX for a problem (linear constraints and objective). For large instances where proving optimality in a reasonable time was out of the question, CP-SAT had much faster convergence to near-optimal solutions than CPLEX when the time limit was small enough (~30s to a few minutes). This is with the CPLEX solver tuned towards improving the upper bound as much as possible (it was a minimization problem).

I you have optimality requirements (aka from the feasible solutions find the absolutely best) then optimization is the way to go

My advice is if you are on the clock, just use whatever works best out of the box.

Now if you plan to solve this problem thousands of times daily, then I would invest in writing custom callbacks in CPLEX to inject feasible solutions during the search since its heuristics are suffering in your problem case.

Also very permissive license with unlimited deployment and cores!

But your intuition is right, this is roughly how IP optimizers work. They relax the problem to a continuous one (aka convert the {0,1} to [0,1]), solve this super easy linear problem and try to find integral solutions close this linear optimum. If not, start branching on the integers and solve smaller and smaller linear problems until you prove optimality.

https://highs.dev/

TimeFold's heuristics-based approach makes fast solutions to even highly-complex scenarios within the reach of anyone who can write Java or Python expressions that evaluate to true when constraints are satisfied.

[0] https://timefold.ai/

Anyways, I wish the best for Timefold team, hopefully they can find success independently. With all the money sloshing around for all sorts of dumb AI projects, I think Timefold definitely deserves a portion too.

> All OptaPlanner features are part of Community Edition, except for Multithreaded Solving

Of course, because why not. If you can take features away from an existing thing to make more money.

I 'd love to understand this better, so we can improve it in Timefold Community. To help deal with new problems, we're creating out-of-the-box quickstarts for common use cases: https://github.com/TimefoldAI/timefold-quickstarts

As for the Community/Enterprise split - we want to continue the open source project, but we need to eat too :)

Geoffrey (Timefold co-founder / OptaPlanner creator)

> As for the Community/Enterprise split - we want to continue the open source project, but we need to eat too :)

Yeah, I don’t begrudge you that. It’s just that when I see that multithreading is locked away I just know that the moment I start using the product I’ll find out my toy problems are enterprise scale. Sort of like murpheys law, but for software features.

We're still figuring out a good, clear, honest pricing model for Enterprise that works well across company sizes (small - big), industries (healthcare vs telecom vs ...) and usage frequency (strategic vs operational planning).

We're happy to send you our pricing table version 1 (use contact us form on Timefold website), but we need your feedback if it fits your business model, deployment model, usage model, etc to validate our pricing model.

It would cost less to pay Timefold whatever price they quote.

I've never worked with any of these, but that's what I would expect as well. API documentation that describes how to solve each kind of mathematical optimization problem.

Do you have an example of an optimization solver with API documentation for business SMEs?

m.addConstr(x+y<=limit);

Where m is a model object, x & y are decision variables and limit is a constant.

The above is a no brainer for any business expert. Some solvers are a LOT more low level though and you have to think of the problem in matrix form and specify row/column stuff and it's a lot more involved and assumes significantly more knowledge of the user than the former.

https://www.cvxpy.org/

If you can convert your problem into a convex one (which I believe is often possible if you’re clever about how you express it), that would seem to be a pretty good option, no?

It does make it very easy to format problems in Python but you still need a solver like Gurobi on the backend. You can use a variety of solvers on the same problem though, which is nice:

https://www.cvxpy.org/tutorial/advanced/index.html#choosing-...

My understanding is that Gurobi the best -- but also the most expensive.

I will definitely bookmark them for the future.

The old planners would include meta-rules, or heuristics, that decided which rules to apply. That would cut the search space. Some split the problem into different representations with specialized, automated solvers. Jahob Analysis System and Cyc come to mind.

Far as for real-world use, the neatest design I remember from classic A.I. was the Procedural Reasoning System. I've always wanted to see a version of it rebuilt with modern methods supplementing its weaknesses. Just for kicks and to see what it could do.

https://en.wikipedia.org/wiki/Procedural_reasoning_system

Besides that MiniZinc is a phenomenal interface to a whole range of solvers specialised to various purposes which are more likely to get you where you want to go if you're not an expert. In the Prolog case -- for all its benefits -- the amount of "mechanical sympathy" required to make it perform well can become substantial very quickly.

Finally, once you've written something in Picat, have a think about how you'd write it in some other language. I think you'll find .. for these toy problems, its easy in other languages too. After all, its a handful of lines to write Dijkstra or A* in most functional programming languages, and defining a state space for a search algorithm is essentially all you're ever doing.

- The [Firebase technical screen](https://startupandrew.com/posts/how-firebase-interviewed-sof...) would have been much easier with something like this, as it was Just Another Optimization Problem™. Part of me wants to try it again with Picat!

- He's doing other very interesting things with programming languages, e.g.: https://github.com/obi1kenobi/trustfall

    const main = <a extends any, b extends any, c extends any>([a_, b_, c_]: [a, b, c, a]) => {
      type SomeTuple = [a, b, c, a];
      const X: a = a_;
      const Y: Exclude<SomeTuple, a> // = <put solved value here, get a type error if the value does not satisfy the constraints>
      console.log(X, Y);
    }

    type Narrowable = string | number | bigint | boolean;
    /*
      Express the type of a value in a tuple that is not the type of the second parameter
      For example:
      - ValOfTupleExceptFor<[1,1,6,2,3], 1> -> 6
      - ValOfTupleExceptFor<[1,1,6,2,3], 6> -> 1
    */
    type ValOfTupleExceptFor<
      Tup extends readonly Narrowable[],
      Val extends Tup[number]
    > = Tup extends [infer First, ...(infer Rest extends Narrowable[])]
      ? First extends Val
        ? Rest extends []
          ? never
          : ValOfTupleExceptFor<Rest, Val>
        : First
      : never;
    
    const NO_SOLUTION: unique symbol = Symbol('NO_SOLUTION')
    const getValOfTupleExcluding = (tup: readonly Narrowable[], val: (typeof tup)[number]): ValOfTupleExceptFor<typeof tup, typeof val> => {
      const [first, ...rest] = tup;
      if (!first) {
        return NO_SOLUTION as never;
      }
      if (first === val) {
        return getValOfTupleExcluding(rest, val);
      }
      return first as ValOfTupleExceptFor<typeof tup, typeof val>;
    }
    
    const main = <a extends Narrowable, b extends Narrowable, c extends Narrowable>([a_, b_, c_]: [a, b, c, a]) => {
      const someTuple = [a_, b_, c_, a_] as const;
      const X: a = a_;
      // This still resolves to type 'never'
      const Y: ValOfTupleExceptFor<typeof someTuple, a> = getValOfTupleExcluding(someTuple, a_);
      console.log(X, Y);
    }

edit: TS playground link with some experiments if anyone's interested: http://tinyurl.com/3p2pzdtn

It so sad that as an industry we seemed locked into really bad tools.

For some example of the available predicates in the bp module, see my http://hakank.org/picat/v3_utils.pi . Also, see http://hakank.org/picat/#v3 for some examples of ported Prolog programs.

And I came here to make @rad_gruchalski's comment. So... thx for making that comment so I don't have to.

The comments about video game at the end of the article makes me wonder: the planner feature allows solving problems very easily by writing few lines of clear code. However, how does the performance compares against an algorithm written in imperative programming?

Picat seems to be fairly efficient compared to similar languages [1] but I don't find a comparison against "standard" languages.

[1]: https://arxiv.org/abs/1405.2538

It might be interesting to someone but I used A* to do code generation to go from one state to target state. I'm not experienced with the planning community or solvers except for playing around naively with ortools.

I generate assembly instructions to move between states.

  start_state = {
    "memory": [0, 0, 0, 0],
    "rax": 0,
    "rbx": 1,
    "rcx": 2,
    "rdx": 3,
    "rsp": -1,
    "rdi": -1,
    "rbp": -1
  }

  end_state = {
    "memory": [3, 1, 2, -1],
    "rax": 3,
    "rbx": 2,
    "rcx": 1,
    "rdx": 0,
    "rsp": 6,
    "rdi": -1,
    "rbp": -1
  }

  [start, mov %rax, (%rdx), mov %rbx, (%rbx), mov %rcx, (%rcx), mov %rdx, (%rsp), mov %rax, %rsp, mov %rdx, %rax, mov %rsp, %rdx, mov %rcx, %rsp, mov %rbx, %rcx, mov %rsp, %rbx, call minus1(rdi=-1) -> rsp=4, call fourtofive(rsp=4) -> rsp=5, call fivetosix(rsp=5) -> rsp=6]

I also run it in parallel to speed up search using python multiprocessing and do dynamic neighbour generation because neighbour generation is different between threads and I couldn't parallelise A* with my original attempts without sharding this.

The dream of my experimentation is that you tell the computer what you have and what you want it works out the correct traversals for you.

For my personal intuition programming is logistics like factorio or a factory. This is why it's called "sliding puzzle", it's a puzzle where you have to move things around to see the correct picture.

Github repo with some notes: https://github.com/samsquire/sliding-puzzle-codegen-memory

Replit: https://replit.com/@Chronological/SlidingPuzzle3

...but actually they're really different!

ASP isn't Turing-complete - it's a lot more like an SMT solver. crucially, there's a grounding stage, where the set of every expressible term in the model (its Herbrand universe) is explicitly written down. so if you have e.g. `f(a;b). g(X,Y) :- f(X),f(Y).` then it will write out every expansion of g during pre-processing.

this makes ASP very powerful, and very fast even at complex problems, but it dooms the solver if the universe is large.

in contrast, Picat is basically a souped up Prolog. it's a full programming language, and it doesn't require grounding so infinite state spaces are okay. it leverages its tabling mechanism to memo-ize predicates evaluation, and it automatically manages the time/space tradeoff with search, which is nifty. but at the end of the day it's brute force, not deep witchcraft like Z3.

Here is an actual description: https://z3prover.github.io/papers/programmingz3.html#sec-int...

https://www.quantamagazine.org/an-easy-sounding-problem-yiel...

Really bad worst case times aren't necessarily bad in practice, if most instances you actually encounter can be solved quickly (especially if you are happy to be satisfied with worse than proven-optimal solutions.)

Compare how Hindley-Milner type inference, which forms the basis of Rust's or Haskell's type systems, is double-exponential in the worst case (or something like that), but typically fast in practice.

https://www.amazon.com/How-Solve-Heuristics-Zbigniew-Michale...

https://www.jsoftware.us/vol7/jsw0709-23.pdf

I'm not familiar with picat, but the arithmetic operations used in the blog post suggest to me that the size of the state space is not necessarily bounded by the input. I believe the mention of EXPTIME in the post was removed.

This is Prolog nuggets.

So rude. Why would I want to run WINE just for that?