Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Constraint Programming

en.wikipedia.org

Post reply on HN
Print view View original

41–50 of 63 posts

Re: Constraint Programming

#41

Post by danielvaughn »

I'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
  }

Re: Constraint Programming

#42

Post by 7thaccount »

sterlind wrote: post #39
7thaccount wrote: post #23

Earlier quoted context omitted.

What are you using to build your GUROBI models? I think your only options are to feed it a .MPS or .LP file if you don't use the APIs for C#, C, C++, Python, Matlab, R...etc. Or did you use something like Mathematica to go from CAS to .MPS?

Mathematica, correct. But fun fact: Mathematica has no MPS exporter. So I had to write my own, which is somehow the perf bottleneck in my whole setup now. Even after wrestling with it for several days. Apparently string operations are not its forté.

I had to look that up as I couldn't believe they don't have that feature... especially since Import[] supports .MPS. I know they have plugin support for solvers like Mosek and I think GUROBI which I assume creates a .MPS and sends to the solver. Maybe it just does it all in memory. They really need to add that lol.

Re: Constraint Programming

#43

Post by sacado2 »

dragontamer wrote: post #32
sacado2 wrote: post #31

Earlier quoted context omitted.

SAT solvers are used a lot for NP-complete problems, but they don't use the 3-SAT representation of clauses. 3-SAT is only interesting from a theoretical POV. Nobody uses it in practice. There are also intermediate representations. For instance, pseudo-boolean retains most of the power of SAT solvers, while at the same time making problems much easier to express in terms of number of constraints needed. For instance,…

> For instance, your Alldifferent(X11, X12, X13, X14, X15, X16, X17, X18, X19) constraint would be written as "x11 + x12 + x13 + x14 + x15 + x16 + x17 + x18 + x19 = 1". Same expressive power, on this problem. I'm more comfortable with constraint-programming than 3SAT / SMT / etc. etc. So I'm probably getting something wrong here. I don't think you're correct on this issue? "x11 + x12 = 1" means that "x11 or x12 are 1…

> I don't think you're correct on this issue? "x11 + x12 = 1" means that "x11 or x12 are 1, and the other is zero".

and

> In most of the 3SAT / SMT solvers for Sudoku I've seen, you set up the variables as: "X111, X112, X113, X114...", which means "X11 == 1", and "X11 == 2", etc. etc. So you then do "X111 + X112 + X113... X119 == 1", meaning "X11 is either 1, 2, 3, 4, 5... 9".

Yes, I've been a bit to fast here. You're absolutely right.

> I've been told that "because everything is {0, 1}, more optimizations / inferences can be discovered" in 3SAT/SMT solvers compared to constraint programmers. Meanwhile, constraint programmers benefit from generic constraints that have a polynomial class subsolution (ie: using maximum flow, or other simpler algorithms to solve the subproblem).

Yes. SAT solvers very often outperform CSP solvers nowadays. But SAT solvers tend to lose the structure of the problem because they are so low-level. The most famous problem they fail to solve is the pigeonhole problem.

If you have, say, the problem "is there a way to put 4 pigeons into 3 different holes, knowing that there can be at most 1 pigeon per hole and at least 1 hole per pigeon?", the answer is obviously "no", but if you try to use a propositional logic representation (in other words, using a SAT solver), the solving track will grow exponentially (4 vs 3 workds well, but SAT solvers will struggle to solve 11 vs 10 in a reasonable amount of time). Pseudo-boolean solvers will be able to using "cutting-planes" strategies that work well for this specific set of problems, but these are slower in the general case.

Plus, modeling your problem in CNF to feed it to a SAT solver is usually incredibly complex and can lead to gigantic formulas if you're not careful. So most of the time, it really makes sense to first use a CSP representation, and fall back to a CNF representation if you're not satisfied with the results for some reason.

Re: Constraint Programming

#44

Post by hakank »

sterlind wrote: post #38
hakank wrote: post #11

Earlier quoted context omitted.

Yes, OR-tools has a lot of solvers. The solver I talked about is the CP-SAT solver. It's described ( https://www.minizinc.org/challenge2022/description_or-tools_... ) as: """ CP-SAT is a discrete optimization solver built on top of a SAT engine. It is available within the OR-Tools open-source repository (website: https://developers.google.com/optimization , github repository: https://github.com/google/or-tools ). It…

wow. that is impressive.. but surely this CP-SAT solver can't compete with the commercial offerings like Gurobi and CPLEX right? it'd be huge news if so... but I haven't seen it rank at all on the LP-focused benchmarks I've been looking at.

I haven't seen a comparison on LP-focused benchmarks with OR-tools CP-SAT. In the 2022 MiniZinc Challenge (https://www.minizinc.org/challenge2022/results2022.html ) both Gurobi, CPLEX (as well and SCIP and HiGHS) participated: CP-SAT was the best in all the categories it participated in.

Re: Constraint Programming

#45

Post by WoodenChair »

We 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

1: https://freecontent.manning.com/constraint-satisfaction-prob...

2: https://youtu.be/_DAjDZXQfNE

Re: Constraint Programming

#46

Post by ceceron »

gcanyon wrote: post #3

MiniZinc is a fairly simple-to-understand and open source constraint language: 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-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

I totally agree. MiniZinc is a great tool to prototype solvers for combinatorial optimization problems. It's mature (but still growing) and has support for many different solvers, not only from the Constraint Programming/SAT family. You can easily switch to MIP solvers (like Gurobi) or even try some local search approaches.

It has very good documentation, reasonable IDE and AFAIK three great courses on Coursera for beginners. I have been teaching it myself[1] and all my students were amazed how quickly one can develop a working prototype for real-life industrial problems.

[1] https://gitlab.com/agh-courses/2021-2022/constraint-programm...

Re: Constraint Programming

#47

Post by andsoitis »

danielvaughn wrote: post #41

I'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: @…

You may be interested in Cassowary https://constraints.cs.washington.edu/cassowary/

Re: Constraint Programming

#48

Post by sterlind »

7thaccount wrote: post #42
sterlind wrote: post #39

Earlier quoted context omitted.

Mathematica, correct. But fun fact: Mathematica has no MPS exporter. So I had to write my own, which is somehow the perf bottleneck in my whole setup now. Even after wrestling with it for several days. Apparently string operations are not its forté.

I had to look that up as I couldn't believe they don't have that feature... especially since Import[] supports .MPS. I know they have plugin support for solvers like Mosek and I think GUROBI which I assume creates a .MPS and sends to the solver. Maybe it just does it all in memory. They really need to add that lol.

it's so bizarre! why would they only do it halfway? and import is the least useful direction for them to implement.. how often are you building models outside of Mathematica to solve inside?

I can't use the Gurobi support, sadly, since my Gurobi instance is on another box (where I don't have MMA), and I needed to benchmark against HiGHS, CBC etc.

Re: Constraint Programming

#49

Post by mzl »

sterlind wrote: post #38
hakank wrote: post #11

Earlier quoted context omitted.

Yes, OR-tools has a lot of solvers. The solver I talked about is the CP-SAT solver. It's described ( https://www.minizinc.org/challenge2022/description_or-tools_... ) as: """ CP-SAT is a discrete optimization solver built on top of a SAT engine. It is available within the OR-Tools open-source repository (website: https://developers.google.com/optimization , github repository: https://github.com/google/or-tools ). It…

wow. that is impressive.. but surely this CP-SAT solver can't compete with the commercial offerings like Gurobi and CPLEX right? it'd be huge news if so... but I haven't seen it rank at all on the LP-focused benchmarks I've been looking at.

It depends a lot on the problem to solve and how it is modeled. For some things OR-tools and/or other CP-style solvers are clearly better than MIP solvers. For others, vice verse.

A really nice thing with MiniZinc is that the same model can be used with both CP silvers like OR-Tools and MIP solvers like CPLEX and Gurobi.

Re: Constraint Programming

#50

Post by dragontamer »

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

Post reply on HN