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

51–60 of 63 posts

Re: Constraint Programming

#51

Post by 7thaccount »

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

Earlier quoted context omitted.

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.

It's a good point that most people won't be using Mathematica for solving LP and MIP models as it just uses CBC as the backend anyway. I mean you could of course, but I think most folks would just use an API to call CBC more directly outside of Mathematica. I bet they could add this feature easily enough though.

Re: Constraint Programming

#52

Post by danielvaughn »

andsoitis wrote: post #47
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/

Yep, 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.

Re: Constraint Programming

#53

Post by mzl »

sterlind wrote: post #7
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

as 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…

I'm curious what you would have wanted MiniZinc to do?

In general, I think MiniZinc is great precisely because it is a structured way to generate a list of constraints, since this makes it possible to integrate into a variety of solvers. Sure, sometimes the generation and the interchange format can be a bit heavy and I would like better ways to manage that, but it is often still worth it IMHO.

The fact that the language is based on a relational semantics with the unfolding into a list of constraints as a model makes it possible to understand how predicates, nested Boolean contexts, reification, undefined expressions, and local variables all work in conjunction. It is a hard enough problem to solve as is, and I think adding semantic complexity on top of it would make it too hard to do.

Re: Constraint Programming

#54

Post by mzl »

philzook wrote: post #35

A very interesting application of constraint programming is the Unison compiler 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 sophisti…

VIBES 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.htm...). It is a good way to get your problems into the hands of solver developers.

Re: Constraint Programming

#55

Post by philzook »

mzl wrote: post #54
philzook wrote: post #35

A very interesting application of constraint programming is the Unison compiler 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 sophisti…

VIBES 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.htm... ). It is a good way to get your problems into the hands of solver developers.

Thanks 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/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.

Re: Constraint Programming

#56

Post by cerved »

dragontamer wrote: post #50

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…

Constraint 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

Re: Constraint Programming

#57

Post by gcanyon »

hakank wrote: post #5
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

Hi again Geoff. Here are some other constraint modelling implementations of this problem: http://hakank.org/common_cp_models/#einavpuzzle .

WOW 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 :-)

Re: Constraint Programming

#58

Post by btilly »

sterlind wrote: post #40
btilly wrote: post #37

Earlier quoted context omitted.

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

well 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 m…

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

Re: Constraint Programming

#59

Post by mzl »

philzook wrote: post #55
mzl wrote: post #54

Earlier quoted context omitted.

VIBES 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.htm... ). It is a good way to get your problems into the hands of solver developers.

Thanks 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/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 co…

Thanks, 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.

Re: Constraint Programming

#60

Post by wjnc »

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

Ha I just started the course in MiniZinc on Coursera and it is very nice and creative. One tidbit for someone with a mostly econometrics background that (for me, a starter in the language with some exposure to linear optimization in the past) it was hard getting it to perform operations that use floats. For me that took away most toy problems I am interested in. But it’s blazing fast for complex discrete optimization and very forgiving in the language, so at least it’s a great learn.
Post reply on HN