Live data from Hacker News

Planner programming blows my mind

hillelwayne.com

11–20 of 75 posts

Re: Planner programming blows my mind

#11
My first thought was, this looks like a type system, except you need to solve it yourself. In Typesecript, naively:

    const main = ([a_, b_, c_]: [a, b, c, a]) => {
      type SomeTuple = [a, b, c, a];
      const X: a = a_;
      const Y: Exclude // = 
      console.log(X, Y);
    }
Except nothing solves this because a, b, and c can all be the same. After trying to express this correctly, I ended up with something that appears useable (but that still uses assertions and doesn't really express the type of Y correctly).

    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 -> 6
      - ValOfTupleExceptFor -> 1
    */
    type ValOfTupleExceptFor = Tup extends [infer First, ...(infer Rest extends Narrowable[])]
      ? First extends Val
        ? Rest extends []
          ? never
          : ValOfTupleExceptFor
        : First
      : never;
    
    const NO_SOLUTION: unique symbol = Symbol('NO_SOLUTION')
    const getValOfTupleExcluding = (tup: readonly Narrowable[], val: (typeof tup)[number]): ValOfTupleExceptFor => {
      const [first, ...rest] = tup;
      if (!first) {
        return NO_SOLUTION as never;
      }
      if (first === val) {
        return getValOfTupleExcluding(rest, val);
      }
      return first as ValOfTupleExceptFor;
    }
    
    const main = ([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 = getValOfTupleExcluding(someTuple, a_);
      console.log(X, Y);
    }
Which really highlights how powerful the 'planner' style program is in terms of simplicity and conciseness. I guess Typescript isn't even powerful enough to express this kind of constraint.

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

Re: Planner programming blows my mind

#12
I'm a little confused about how planning is different from vector reachability, which, from what I understand, has Ackermann complexity rather than EXPTIME. Can anyone help me out with the constraints on "planning" that allow it to be solved in a sane amount of time?

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

Re: Planner programming blows my mind

#13
post #3

I've actually used Picat's planning mode at work! 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 machin…

There are plenty of commercial solvers out there that beat the pants off the open source options in terms of performance and in terms of depleting one's wallet :) 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 mor…

Yup. & when you get a model that works matched up with an industrial scale decision problem that's valuable to solve, arguably it's only of academic interest if you can solve it "optimally". The problem is only a simplified model of reality anyway -- it's often better to get a quick close-enough approximate solution to a problem that's a good approximation of the situation than an exact optimal solution to a simpler problem that's a poorer approximation.

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.

Re: Planner programming blows my mind

#14
post #3

I've actually used Picat's planning mode at work! 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 machin…

There are plenty of commercial solvers out there that beat the pants off the open source options in terms of performance and in terms of depleting one's wallet :) 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 mor…

> There are plenty of commercial solvers out there that beat the pants off the open source options in terms of performance and in terms of depleting one's wallet :)

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

Re: Planner programming blows my mind

#15
post #12

I'm a little confused about how planning is different from vector reachability, which, from what I understand, has Ackermann complexity rather than EXPTIME. Can anyone help me out with the constraints on "planning" that allow it to be solved in a sane amount of time? https://www.quantamagazine.org/an-easy-sounding-problem-yiel...

We normally pick up stuff like that in papers, blog posts, etc. The only heuristics book I remember was How to Solve It. I also found a survey paper on heuristics. Here they are in case they help:

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

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

Re: Planner programming blows my mind

#16

Earlier quoted context omitted.

There are plenty of commercial solvers out there that beat the pants off the open source options in terms of performance and in terms of depleting one's wallet :) 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 mor…

> There are plenty of commercial solvers out there that beat the pants off the open source options in terms of performance and in terms of depleting one's wallet :) 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…

If feasibility is your goal then cp/sat solvers/heuristics should be your tool of choice.

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

Re: Planner programming blows my mind

#17
post #3

I've actually used Picat's planning mode at work! 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 machin…

There are plenty of commercial solvers out there that beat the pants off the open source options in terms of performance and in terms of depleting one's wallet :) 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 mor…

Are the commercial offerings you mentioned better than TimeFold? [0] (formerly known as OptaPlanner before the main developers forked it)

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/

Re: Planner programming blows my mind

#18
post #6

Looks Prolog-ish. Interesting, thanks for sharing.

AFAICT Picat is a direct descendant of B-Prolog and shares a lot of idioms (like tabling) with it. https://en.wikipedia.org/wiki/B-Prolog

THX for the reference. I used Prolog a fair amount in the 90s, but didn't know about B-Prolog. Now I do.

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

Re: Planner programming blows my mind

#20
post #3

I've actually used Picat's planning mode at work! 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 machin…

There are plenty of commercial solvers out there that beat the pants off the open source options in terms of performance and in terms of depleting one's wallet :) 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 mor…

What about this one:

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?

Post reply on HN