1,920 karma · joined April 27, 2010
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.
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.
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.
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.
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.
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.
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.
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.
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.
* 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.
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.
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.
The most annoying bug was that one could only have around 4-5 tabs open before something went wrong and everything stopped updating.
I have a strong bias for the practical side of constraint programming systems, as may have come through.
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.
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.
As a comparison, see this model solving crosswords using constraint programming. https://github.com/Gecode/gecode/blob/develop/examples/cross...
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