HNHacker News
TopNewBestAskShowJobs

mzl

1,920 karma · joined April 27, 2010

submissionscomments
mzl··on Nonograms - Japanese Crosswords
See chapter 17 in https://www.gecode.org/doc-latest/MPG.pdf for a description on how to solve it with regular expression constraints using CP.
mzl··on Game Jam 2 Results
> There are HFT systems using Java, few were on HN even.

The HFT systems I know about in Java are mostly not recognizable as Java to most Java programmers. They use static allocation of all data making sure that there is no risk of a GC interrupt and have a fixed set of threads that have assigned cores.

It is sometimes a reasonable way to build a system, but very seldom.

mzl··on Constraint Programming
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.

mzl··on Constraint Programming
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.

mzl··on Constraint Programming
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.

mzl··on Constraint Programming
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.

mzl··on Constraint Programming
Most 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.
mzl··on Is there a language/framework can describe a model and generate checking rules?
As understood it, finding a solution that satisfies all the constraints is not trivial, and for that external libraries are the right kind of tool.
mzl··on Is there a language/framework can describe a model and generate checking rules?
As others have said, using a combinatorial solver like Z3 (SMT solver) or MiniZinc (which is a modelling language and can interface to different types of solvers, including several constraint programming and mixed integer programming solvers, can be driven via minizicn-python) is probably the way to go. CPMpy is a new Python modelling framework that might also be of interest that interfaces to different solvers

If you have a lot of constraints that are on the bit representation, then it is more likely that an SMT solver is a better solution. If on the other hand more of your constraints are arithmetic and perhaps some structural constraints, then it might be interesting to look into other types of solvers. It all depends on the specifics of your problem instances.

There are a couple of Coursera courses for modelling with MiniZinc that are quite nice (https://www.coursera.org/learn/basic-modeling is the first one) that are useful if you want to learn more about how to think when doing combinatorial modelling. These are usefule even if you end up using some other tool or technology, as the mindset is similar.

mzl··on Ask HN: Do you use an optimization solver? Which one? Do you like it?
Sounds like you have a good solution for your problem. Whatever solves the problem and is already done is naturally a good solution!

From my experience, the most important thing to get right in any local search algorithm is the state representation and the moves generated. If those work well, then any combination of metheuristics like simulated annealing, tabu search, population based search, restarts, parallel exploration, portfolio methods, and so on. Quite often the literature focuses only on the meta heuristic, but not so much on the representation, which IMHO can be an issue.

As an example, for some problems that I have solved with local search, the most impact in improving performance of the algorithms have been in improving the base. Making moves and score updates fast, and making the moves generated meaningful in the context.

mzl··on Ask HN: Do you use an optimization solver? Which one? Do you like it?
Not OP either, but there are many different aspects to solvers that make them useful in different situations.

For example, I would perhaps not use the same solver for a best-effort problem where I can program strong heuristics, vs a problem that must be optimized and no natural heuristics exist. Sometimes problems have a natural type of formulation, and it is best to use a solver for that type of problem (linear programming, mixed integer programming, SAT, pseudo boolean, constraint programming, ...).

Choosing a solver also very much depends on the deployment situation; how should a model be used and what operational concerns are there.

mzl··on Ask HN: Do you use an optimization solver? Which one? Do you like it?
Fun problem. When solving with Gecode, you might want to add the annotation `:: domain_propagation` to the `all_different` constraint (https://www.minizinc.org/doc-2.6.2/en/lib-stdlib-annotations...). Sometimes a good idea, sometimes not.

If you can extract some instances you could send in your problem to the MiniZinc challenge (https://www.minizinc.org/challenge2022/challenge.html), preferably with several instances with varying complexity. The benefit for you is that it is a good way to ensure that your particular problem is tested for a lot of solvers, and may be used for improvments of solvers in the future. The deadline for this years challenge problem submission is 6th of May.

mzl··on Ask HN: Do you use an optimization solver? Which one? Do you like it?
I use different solvers for different things, depending on the type of problem to solve and the goal of solving the problem.

* MiniZinc is my favourite tool for prototyping models. Looking into the feasibility of using it in a roduction environment as well. Typically models are small to medium sized. Also using it for recreational problem solving (e.g., Advent of Code).

* Gecode is my go-to solver for writing applications where I need more control over the solving process or I want to write a custom propagator or heuristic. Used it for scheduling, planning, and configuration.

* When in the JVM ecosystem, I've used Choco.

* I've used OR-tools some, but would like to be better at it. Mainly because OR-tools has a nice set-up with a lazy clause generation solver, good automatic heuristics, and a nice portfolio solver for parallel work.

* Quite often, a custom optimization heuristic is also the right tool for the job.

I've tried to use Gurobi sometimes, but for the problems I've tried, it has either been to hard to model effectively or was not a good fit. The licensing cost is a limiting factor as well.

mzl··on C Isn't a Programming Language Anymore
As noted very clearly in the article, the problem with using underspecified versions of C as the ABI is _also_ a problem for C the language, as it limits the possible evolution of C.
mzl··on Wordle-solving state of the art: all optimality results so far
I agree with the recommendation to start with a modelling language in a sibling comment. On the MiniZinc homepage, there are Coursera courses linked that are quite nice as an introduction into combinatorial modelling.

Apart from that, it is worth noting that the solver used in the article, OR-Tools, is not strictly a SAT solver. I would rather describe it as a hybrid portfolio solver, since it combines constraint programming, SAT, MIP, and local search in a single solver. It is also possible to use that solver as a back-end when solving a model written in MiniZinc.

mzl··on Ask HN: Solving problems by mapping to other problems that we know how to solve
And similarly relevant, using a solver independent modelling language like [MiniZinc](https://www.minizinc.org/) means that it is possible to write a model, and then translate it formats suitable for use with MIP, CP, and SAT solvers.
mzl··on Non-Transitive Dice
I've previously written a model that generates sets of non-transitive dice using MiniZinc. It can be seen in this Gist: https://gist.github.com/zayenz/4fa2d5ca8f96f7ce939275be25bdd...
mzl··on Scryer Prolog: A modern Prolog implementation written mostly in Rust
There are techniques that are purely academic, but there are lots of cases where constraint modeling turns up and is useful. In my experience, the area where constraint programming is used the most is in applications that do things like scheduling and rostering.
mzl··on Scryer Prolog: A modern Prolog implementation written mostly in Rust
Personally, I would not choose to solve a constraint programming problem in Prolog, unless I really needed to use a specific global constraint that is only available in some Prolog engine (such as the geost constraint in SICStus Prolog).

When I need to solve a CP problem, I typically do one of the following

* Write a simple model in MiniZinc. This is great for experimentation and testing different solvers to see which kind of solver might be suitable (different CP solvers, MIP solvers, etc)

* For some cases or if I need to integrate with a larger system I write my code using a library directly, such as Gecode, Choco, or or-tools. Using a system directly has the benefit that it is possible to program a custom search heuristic, which I find is often very useful for solving problems in practice.

* Write a custom algorithm. Sometimes the right answer is to just write some code solving the problem directly.

I find models written in a modeling language such as MiniZinc or in a traditional Programming language such as C++, Java, or Python to be easier to read and reason about than Prolog programs that solve constraint problems. That is a personal preference, and varies depending on familiarity.

mzl··on How much faster is Java 17?
There are a couple of very good coursera courses on modeling with MiniZinc, the first one being https://www.coursera.org/learn/basic-modeling
mzl··on How much faster is Java 17?
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.
mzl··on US Cybercom says mass exploitation of Atlassian Confluence vulnerability ongoing
I've had to use Azure DevOps recently, and it made me long for the speed, simplicity, and stability of Jira...

The most annoying bug was that one could only have around 4-5 tabs open before something went wrong and everything stopped updating.

mzl··on Send+more=money and how to use forward-checking in search
Yeah, it’s a suboptimal terminology, at least in my opinion.

I have a strong bias for the practical side of constraint programming systems, as may have come through.

mzl··on Send+more=money and how to use forward-checking in search
Guess-and-check is usually another term for generate-and-test, which explicitly does not do propagation.
mzl··on Send+more=money and how to use forward-checking in search
Arc consistency is not really a good term to use, since it was originally defined for 2-ary constraints only, but is sometimes used for n-ary constraints. That is why I use the term domain consistency consistently :-)

Given a propagator for circuit that reaches domain consistency (note, for the whole n-ary constraint), that is equivalent to a checker of there is a Hamiltonian path and that will most likely never be a polynomial algorithm (unless P=NP). I can’t say that I’m interested in any particular property of the decomposition of the constraint into 2-ary parts, it is not that interesting of a structure. The cool filterings that circuit propagators do are based on global analysis of the whole graph, not on any local property. For example by finding ordering a of strongly connected components in the current graph.

Almost all propagators need to be reasonably fast to be usable, that is sort of a given in this area. An exponential propagator is almost always a bad idea. For all_different there is a O(n^2.5) algorithm for domain consistency which is really cool and important. In practice, the simple value propagation (remove assigned values from the other variables) is often better for finding solutions quickly.

mzl··on Send+more=money and how to use forward-checking in search
For many constraints there are propagators that can reach domain consistency (all remaining values for all variables are part of some solution to the constraint, sometimes called generalized arc consistency). For some constraints the best propagator in practice is a much weaker one, as propagating to domain consistency is in itself NP-hard. Many times there is no actual formal consistency level definable. A great example of this is the circuit constraint that holds if a set of variables forms a Hamiltonian path in a graph. Hamiltonian paths is a classic NP-complete problem. The propagators for it make smart inferences, but not as a consistency level.

Crucially, propagators are for a single constraint only. For a constraint problem, you run all the propagators to a fix point. There is no single global “algorithm” here, and there are no higher level consistencies.

mzl··on Send+more=money and how to use forward-checking in search
You are missing the crucial role of propagation - looking at the current state and making inferences based on that. Admittedly, DPLL is pretty weak on that with “just” unit propagation, but it is still _very_ important.
mzl··on Send+more=money and how to use forward-checking in search
All of CP, SAT, and ILP are much more advanced than guess and check, although there are never any guarantees.
mzl··on Send+more=money and how to use forward-checking in search
Sure, there are lots but I think it should be doable. Will probably try sometime. Easiest is to make a model that fixes the lengths of the words, and just run it for different word lengths.

As a comparison, see this model solving crosswords using constraint programming. https://github.com/Gecode/gecode/blob/develop/examples/cross...

mzl··on Send+more=money and how to use forward-checking in search
In general, modern constraint programming solvers runs the propagators for the constraints until fixpoint. The level of propagation for a constraint is typically chosen by the modeler, and is typically one of domain consistency, bounds consistency, or simple value propagation. No real world competitive CP solvers use the types of algorithms you mention for the whole problem, since constraints are given in intention (a+b<=c, all_different(x1, …, xn), …), not extension (list of valid tuples).

With that said, sometimes shaving (also called singleton arc consistency) is used, by testing all literal assignments and pruning those that directly give failure. See https://www.inf.tu-dresden.de/content/institutes/ki/cl/study... for an application of this to Sudoku

← PreviousPage 5 of 14Next →