Hacker News Reader

I would also add that Constraint Programming has a small but very dedicated community, and the amount of innovation in the space is incredible given how niche it is. Some things I find amazing:

* Dozens of solvers with hundreds of search methodologies

* Intermediate Language specifications (FlatZinc) to allow solvers written in one language to interact with completely different languages via a common intermediate language.

* Entire catalogs of useful constraints https://sofdem.github.io/gccat/

* Solver Competitions https://www.minizinc.org/challenge.html

* Peer Reviewed journals https://www.springer.com/journal/10601

Geoffrey de Smet, Optaplanner, and Constraint Programming (CP) are all amazing indeed. If we're talking about underhyped tech that actually works wonders in practical business problems, I would also take advantage of the limelight to include the whole CP field (including other solvers like Gecode), SAT solvers (MiniSat, Lingeling, Glucose, Chaff, ...) and SMT software (MiniZinc, Z3, ...), and Operations Research / mixed-integer programming (MIP) in which unfortunately open source software lags behind the stat of the art (Gurobi, Fico XPress).

I wish, SMT-solvers, in particular, were easier to approach. I have a number of problems that are solved once-per-month, that I wouldn’t mind throwing a couple of weeks of compute at to get absolute tip-top results.

Posing SMT-problems though … that’s an art. There’s not enough resources for “problems at scale” for me to just dip my tie into…

Strong recommendation to take a look at MiniZinc. It’s a modeling language for combinatorial optimization problems, and is often quite easy to model problems in it. The cool thing is that one can then solve the problem using many different solver technologies.

Is there an intro you can recommend? I’ve never heard of CP, would love to read about it.

There are a couple of very good coursera courses on modeling with MiniZinc, the first one being https://www.coursera.org/learn/basic-modeling

Signed up. Much appreciated.

I recently got super interested in constraint problems after reading Classical Computer Science Problems in Java. They were really fascinating (along with all the problems in the book).

Thank you very much for the recommdation, looks like an amazing resource. Hopefully i'll be able to schedule time work through this. Would have loved to study CS but awesome/time consuming events in my life prevented it, which is totally fine.

The author also wrote the book for Python or Swift if you’re not into Java.

Author here... thanks really appreciate the shoutout! The Java version is the most recent and probably the best version if you know multiple of the languages and have to choose between them. The Python and Java versions cover all of the same problems. The Swift version (the oldest) is missing a couple. You can find out more about all three, including links to translations in 9 languages, here: https://classicproblems.com/

Thank you very much for writing it. Lucky me, i'm most proficient in Java even though i used all three. May do it in Kotlin, we'll see. You deserve way more than a shoutout, submitted it <edit> so Pythonistas and Swift developers may discover it too</edit>.

If you're interested in this topic, we're building a tool for building cluster manager components (like policy-based container schedulers) using constraint programming, where constraints are specified using SQL.

Paper: https://www.usenix.org/system/files/osdi20-suresh.pdf

Code: https://github.com/vmware/declarative-cluster-management/

Holy smokes, this is one of the coolest thing I've ever seen.

This lets you use data from standard, JDBC-supported SQL databases and write constraints as plain SQL-like queries?! This reminds me of an idea I had about embedding a solver API in Postgres using it's extension functionality and being able to make SQL "VIEWS" that represent solver results, like a delivery route or employee roster.

  CREATE VIEW todays_employee_schedule AS
    SELECT ... 
    CHECK row_satisfies_constraints(...)

If I'm understanding this properly, this seems like this could be applied to general-purpose problems as well -- not just the one you're targeting right?

        // Create an in-memory database and get a JOOQ connection to it
        final DSLContext conn = DSL.using("jdbc:h2:mem:");

        // A table representing some machines
        conn.execute("create table machines(id integer)");

        // A table representing tasks, that need to be assigned to machines by DCM.
        // To do so, create a variable column (prefixed by controllable__).
        conn.execute("create table tasks(task_id integer, controllable__worker_id integer, " +
                "foreign key (controllable__worker_id) references machines(id))");

        // Add four machines
        conn.execute("insert into machines values(1)");
        ...

        // Add two tasks
        conn.execute("insert into tasks values(1, null)");
        ...

        // Time to specify a constraint! Just for fun, let's assign tasks to machines such that the machine IDs sum up to 6.
        final String constraint = "create constraint example_constraint as " +
                "select * from tasks check sum(controllable__worker_id) = 6";

        // Create a DCM model using the database connection and the above constraint
        final Model model = Model.build(conn, List.of(constraint));

        // Solve and return the tasks table. The controllable__worker_id column will either be [1, 5] or [5, 1]
        final List<Integer> column = model.solve("TASKS").map(e -> e.get("CONTROLLABLE__WORKER_ID", Integer.class));

Thank you for the kind words!

Yes it could be applied to general problems as well. In fact, we used it once to plan a program committee meeting. The library (DCM) has no idea what problem setting its being used for, and has no semantic info about the problem other than the schema and constraints we tell it about.

That said, the current focus is on things like incremental computation, debuggability, automatically subsetting the relevant state from the DB, and scalability to really large cluster sizes (O(50K) nodes), which are more useful in the cluster management context than general-purpose constraint programming tasks.

Edit: Also worth mentioning is that your intuition is spot on. The earlier versions of the library went with a CREATE VIEW syntax as you wrote it out. Now that we have a customizable parser, we have since changed it to CREATE CONSTRAINT for clarity.

He’s also a fairly good manager of PRs in my experience. He’s sort of blunt which can be hard to deal with if you’re used to more Anglo pleasantries but you can tell he’s ultimately being helpful.

Thank you for the kind words gavinray :)

OptaPlanner is a team and community effort. Credit goes as much to each of them (see team page) as it does to me. And we're standing on the shoulders of giants (other open source projects).

Hi, cool to see you here. Currently working on a large scale (operating costs in the billions) optimization problem and I'm currently testing out Optaplanner along with some commercial solvers. I really like how the problems are modeled using annotated POJOs, as opposed to some of the more contrived array-based modeling languages out there. And the ConstraintStreams concept is really awesome (if a bit hard to grok at first).

Is there a convenient way to reach out to you or your team with questions? Do you accept outside pull requests?

Of course we accept pull request :) Do start with something small - big changesets are hard to get through the first review. We're on kie.zulipchat.com channel #optaplanner [1] if you want talk about such PR ideas.

As for community questions, the best place for public questions is stackoverflow [1]. For private questions and enterprise-grade support, contact my employer (Red Hat) about our paid support subscription, which pays 99% of the optaplanner's development work.

[1] https://www.optaplanner.org/community/getHelp.html