7 ms·
Constraint Programming
- btilly 4y agoThese techniques are usable in every language, and not just in special ones like Prolog. For example https://norvig.com/sudoku.html https://norvig.com/sudoku.html uses constraint propagation to solve sudoku puzzles in Python.
- sterlind 4y agoIn the sense that Turing-complete languages are all equivalent, yes. But in most imperative and functional languages, you'll end up implementing your own solver (as Norvig did), and a DSL to model your problem. Why reinvent the wheel?
- 7thaccount 4y agoI think a lot of folks have figured out it's easier to do these problems using a DSL inside a general purpose language than to try to use something like Prolog to do both. For example, to optimize the grid, you might have a Python app that imports the GUROBI solver module and tells GUROBI to optimize. The advantage is all the file IO, directory, and database stuff gets to be handled with Python (easy easy).
- mzl 4y agoMost constraint programming applications are written in traditional imperative languages using solver libraries like OR-Tools, Gecode, IBM CP Optimizer, and others. This is both because that works best in the larger context of most applications, but also because solver libraries are generally better than the specific solvers integrated into Prolog systems. Sure, it is possible to use Prolog to solve problems using CP, but in my experience that is a vary small part of the total usage.
- btilly 4y agoWhy reinvent the wheel? If you give me a choice between implementing a solver in an imperative language or a website in Prolog, I'll choose writing the solver. Every time. Problems in the context of a programming environment where you're already using other languages. Introducing a specialized one does not necessarily make much sense.
- sterlind 4y agowell of course, but why not write the solver in Prolog and the website in Python? why are people so allergic to mixing languages? if the problem is simple to describe, then sure, write a solver or use a binding. I'm just used to the problems being pretty intense and sophisticated. I've found having a REPL in a symbolic (term-rewriting) language to be invaluable, and can't imagine going back to for-loops and endless maps of symbol tables chugging out text files for debugging.
- btilly 4y agoLet me turn it around. Why would I use an external language instead of a library in my existing language? It really isn't as hard as you indicate.
- gcanyon 4y agoMiniZinc is a fairly simple-to-understand and open source constraint language: https://www.minizinc.org https://www.minizinc.org I learned about it when a friend gave me a programming challenge: https://gcanyon.wordpress.com/2009/10/28/a-programming-puzzle-from-einav/ https://gcanyon.wordpress.com/2009/10/28/a-programming-puzzl... She was going to work in PHP, I wrote a solution in J, and a commenter solved it in MiniZinc. Here is their solution in MiniZinc: http://www.hakank.org/minizinc/einav_puzzle.mzn http://www.hakank.org/minizinc/einav_puzzle.mzn
- hakank 4y agoHi again Geoff. Here are some other constraint modelling implementations of this problem: http://hakank.org/common_cp_models/#einavpuzzle http://hakank.org/common_cp_models/#einavpuzzle .
- gcanyon 4y agoWOW it surely is a small world — at least our corner of it. I was very glad your page with the MiniZinc solution was still up! Edit to add: holy moses, all those solutions! I need to reach out to Einav to let her know she is famous :-)
- sterlind 4y agoas a note, I've tried MiniZinc for modeling a problem in the past, and the language/ecosystem simply wasn't up to my task. iirc, function calls in MiniZinc are expanded/unrolled when the model is generated, rather than the function definition and its callers being symbolically translated into the model. this is no fault of MiniZinc, I simply thought that an SMT solver would be sufficient and it wasn't. I need a mixed-integer or non-linear program solver, and ended up approaching it with a computer algebra system to generate my models and passing it to Gurobi or HiGHS. tl;dr there's different types of hard, and SMT solvers are only good at some types of hard.
- hakank 4y agoOne interesting development in the latter years is the mix of Constraint programming and SAT solvers. For example Google OR-tools (https://developers.google.com/optimization/ https://developers.google.com/optimization/ ) which mixes CP, SAT and MIP. It has won most of the MiniZinc Challenge categories (https://www.minizinc.org/challenge.html https://www.minizinc.org/challenge.html ) several years now. The Chuffed solver is another solver mixing CP and SAT.
- mattnewport 4y agoThere's a good course on Coursera on using MiniZinc to express constraints for solvers: https://www.coursera.org/learn/basic-modeling https://www.coursera.org/learn/basic-modeling
- rhn_mk1 4y agoDoes Prolog naturally support optimizing for an objective function?
- rad_gruchalski 4y agoIn Prolog, the predicate order matters. So, if I understand your question correctly, no. It's up to the dev to order predicates in such a way that the amount of backtracking is kept to minimal.
- hakank 4y agoWell, most Prolog support clp(fd) (Constraint Logic Programming, Finite Domain) which mostly include support for minimizing/maximizing objectives.
- rad_gruchalski 4y agoBy unification, which will only match the arity, not the rules inside of a predicate. I could be wrong, though. Still learning all ins and outs.
- bjorka 4y ago
- bjorka 4y ago
- bjorka 4y ago
- bjorka 4y ago
- sva_ 4y agoThere's also a Python library for constraint programming. Very easy to get started. https://github.com/python-constraint/python-constraint https://github.com/python-constraint/python-constraint
- amitprayal 4y agoPicat Language which is designed to be more main stream than Prolog supports CP out of the box , also has a planning module
- hakank 4y agoHere's a link to Picat's main site: http://picat-lang.org/ http://picat-lang.org/ . My Picat page have quite a few examples of CP/SAT models (also non-CP programs): http://www.hakank.org/picat/ http://www.hakank.org/picat/ .
- Jenk 4y agoI feel like this is something I may understand the solution to but the problem it solves leaves me dumbfounded. Any recommendations on a "this but for dribbling primates" introduction?
- hosteur 4y agoI think this can be applied to much the same domains as simplex or similar algorithms. So optimization problems/OR. See https://en.wikipedia.org/wiki/Operations_research https://en.wikipedia.org/wiki/Operations_research
- dragontamer 4y agoConstraint Programming is NP-complete (non-polynomial bounds, likely exponential complexity). Simplex is provably within the polynomial bounds of complexity, ie: simplex is a so called "easy" problem in complexity theory. -------- You're right that simplex is applied to optimization problems. Constraint programming could be seen as a "more generic" optimizer, in that it can handle integer-optimization (simplex cannot handle integer optimization at all). Of course, integer-optimization is NP complete, which means that constraint programming is innately "inefficient" or "hard" in terms of complexity.
- aaplok 4y agoNot quite. Simplex is an algorithm to solve linear programming problems. Linear programming is (weakly) polynomial. The simplex algorithm itself has exponential worst case [0]. Whether there exist a polynomial-time variant of the simplex algorithm is an open problem. Constraint programming is very broad — it encompasses many types of problems. Some of them are in P, some (most?) are in NP. In principle you can use the simplex algorithm for solving certain constraint programming problems, but mostly when people talk about constraint programming they refer to different techniques. [0] https://en.wikipedia.org/wiki/Klee%E2%80%93Minty_cube https://en.wikipedia.org/wiki/Klee%E2%80%93Minty_cube
- dragontamer 4y agoConstraint Programming is "on the same complexity" as any of your NP-completeness set of problems. IE: Knapsack problem, Traveling Salesman, etc. etc. Today, it seems more popular to use "3-SAT Solvers". But constraint programming is "more logical" for some problems to get converted into rather than 3-SAT. Consider 3-SAT and Constraint Programming to be two different "assembly languages" that you can compile your problem into, and then have a generic solver into. ----------- For example: Sudoku can be "compiled" into the 3SAT problem: https://www.mit.edu/~6.005/sp12/psets/ps2/ps2.html https://www.mit.edu/~6.005/sp12/psets/ps2/ps2.html But it also can be "compiled" into the Constraint-problem, which then gets solved by a constraint solver. https://sonalake.com/latest/constraint-programming-solving-sudoku-with-choco-solver-library/ https://sonalake.com/latest/constraint-programming-solving-s... ------------ Personally speaking, I think that the constraint solver problem is "easier to compile into" rather than the 3SAT problem, especially when you consider generic constraints that have very efficient solutions. For example, it is difficult to think of the optimal alldifferent constraint within 3SAT, but in a constraint-solver framework, its just... well... alldifferent. So you can describe Sudoku as the following: Domain = {1 2 3 4 5 6 7 8 9} Alldifferent(X11, X12, X13, X14, X15, X16, X17, X18, X19) Alldifferent(X21, X22, X23, X24, X25, X26, X27, X28, X29) Alldifferent(X31, X32, X33, X34, X35, X36, X37, X38, X39) ... Alldifferent(X91, X92, X93, X94, X95, X96, X97, X98, X99) ------------------------------------------------------------------------ Alldifferent(X11, X21, X31, X41, X51, X61, X71, X81, X91) Alldifferent(X12, X22, X32, X42, X52, X62, X72, X82, X92) Alldifferent(X13, X23, X33, X43, X53, X63, X73, X83, X93) ... Alldifferent(X19, X29, X39, X49, X59, X69, X79, X89, X99) ------------------------------------------------------------------------ Alldifferent(X11, X12, X13, X21, X22, X23, X31, X32, X33) ... Alldifferent(X77, X78, X79, X87, X88, X89, X97, X98, X99) That is: numbers are 1 through 9, and constrain the problem such that each row is alldifferent, and each column is all different, and each "3x3 square" is all different. ---------- IIRC, the Alldifferent constraint can be efficiently solved using maximum flow. So you write a specialized solver for alldifferent using maximum flow (faster than 3SAT / NP Completeness), and this maximum-flow local solution can be "plugged into" the rest of the constraint solver problem, and integrates cleanly with the rest of the solver's NP-completeness search.
- jhoechtl 4y agoOne underrated CS book is devoting a larger part on constraint programing https://www.amazon.de/-/en/HARIDI-SEIF/dp/8120326857 https://www.amazon.de/-/en/HARIDI-SEIF/dp/8120326857 It is using a back then and even more so today obscure programing language Oz with it' sole implementation Mozart http://mozart2.org/ http://mozart2.org/
- philzook 4y agoA very interesting application of constraint programming is the Unison compiler https://unison-code.github.io/ https://unison-code.github.io/, which uses constraint models to solve compiler backend problems for llvm. As a simple example, register allocation can be modeled as a graph coloring problem for which there is an edge between every variable which must be live at the same time and colors represent registers, but he unison model is sophisticated beyond this. We use a simpler related model in our project VIBES https://github.com/draperlaboratory/VIBES https://github.com/draperlaboratory/VIBES which is a micropatching compiler (it uses the constraints to compile code in such a way it can fit in place, has the right stuff in the right registers, etc.)
- mzl 4y agoVIBES seems like a very cool project. Do you have any example MiniZinc files that show how the generated problems look? Also, I would encourage you to generate some interesting instances and submit to the MiniZinc challenge (last years call for problems: https://www.minizinc.org/challenge2022/call_for_problems.html https://www.minizinc.org/challenge2022/call_for_problems.htm...). It is a good way to get your problems into the hands of solver developers.
- philzook 4y agoThanks for the suggestion! I've known we should be submitting our verification problems to smtcomp, but hadn't thought about minizinc challenges Our current model is here https://github.com/draperlaboratory/VIBES/blob/main/resources/minizinc/model.mzn https://github.com/draperlaboratory/VIBES/blob/main/resource... We don't have any parameter files committed to the repo, they are generated by the compiler. It has been on my todo list for a while to completely refactor this model. Currently, the constraint solve can take 10s on our hardest problems so far, which would be nice to get down, but not our biggest blocker.
- mzl 4y agoThanks, and nice to see! Even if 10 seconds is often fast enough for solving a problem, I can imagine that it would be good to get down. From the code I guess that you use Chuffed, have you also tested other solvers? OR-Tools with parallel solving feels like the standard thing to try. I can also imagine that the time will start to go up significantly if larger patches are specified, but perhaps that is not a very common use-case. Having some example instances for ease of testing would be fun, and make it easier for a drive-by constraint programmer to try it out. Hoping to see it in the competition next year. Problems that are mostly reasonably fast to solve can still be interesting IMHO, especially when they are probably only fast because some solvers (Chuffed/OR-Tools) have very good automatic heuristics.
- binkHN 4y agoI used this to solve some complicated calendar scheduling routines for an app I wrote in Kotlin. Originally, I used some brute force/search methods to handle this, but the approach outlined here provided far better results, and it took less time too.
- danielvaughn 4y agoI've been fascinated by constraints ever since I did some work on iOS, using UIKit. The layout constraint mechanism was super cool. I've been trying to build a programming language for UI designers, and one of the goals is to let designers describe layouts using constraint-based code that reads as close to natural language as possible. Something like: // "the blue box is directly beneath the red box" BlueBox { top: @RedBox.bottom } // "the red box is 10 pixels to the right of the blue box RedBox { left: @BlueBox.right + 10 }
- andsoitis 4y agoYou may be interested in Cassowary https://constraints.cs.washington.edu/cassowary/ https://constraints.cs.washington.edu/cassowary/
- danielvaughn 4y agoYep, looked into Cassowary after digging into AutoLayout (which is apparently based loosely on Cassowary). I struggle with the math since I'm not formally trained.
- WoodenChair 4y agoWe cover constraint satisfaction problems in Chapter 3 of the Classic Computer Science Problems series [0] including a very simple backtracking solver and several examples. Most of the chapter from the Python book is available for free, but it's also covered in the Java and Swift books. [1] I created a short introductory video to the code as well. [2] Backtracking solvers for constraint satisfaction problems (CSPs) are a subset of the world of constraint programming, as described in the linked Wikipedia article. 0: https://classicproblems.com https://classicproblems.com 1: https://freecontent.manning.com/constraint-satisfaction-problems-in-python/ https://freecontent.manning.com/constraint-satisfaction-prob... 2: https://youtu.be/_DAjDZXQfNE https://youtu.be/_DAjDZXQfNE
- dragontamer 4y agoThe entire space of "NP-complete techniques" is very interesting to me. At some point, you will come across an NP-complete problem, and your only choices are to either give up, or try your best to solve the problem anyway. Constraint Programming "clicks" for me a lot more than SAT solvers, which feel more mystical. BDDs and MDDs also deserve a mention, as BDDs kinda solve the #P-complete problem (counting-NP complete problem: not only finding one valid solution, but the count of all valid solutions to an NP complete situation. Many optimization problems are #P complete, as you want to iterate over all of the valid solutions and find the best one.
- cerved 4y agoConstraint programming is very elegant but metaheuristic approaches often scale much better than a traditional CP approach. Constraint based Lucas search, CBLS, is an interesting fusion