5 ms·
The article series Modern SAT Solvers: Fast, Neat, and Underused[1] argues that we don't use generic problem solvers enough in our daily engineering work. A ge
by kqr 6y ago
The article series Modern SAT Solvers: Fast, Neat, and Underused[1] argues that we don't use generic problem solvers enough in our daily engineering work.
A generic solution won't beat a hand-optimised specific solution, but if you're good at phrasing your problem in the right way, you can get 80 % of the way there with 20 % of the effort by using a generic solver.
Z3, being an even more generic SMT solver rather than "just" a SAT solver, should allow you to do even more with less.
I've long wanted to integrate this type of solver into my workflow more, because I think that if I can make it into more of a habit, it would provide insane leverage for prototyping. Does anyone have experience using these techniques for that?
[1]: https://codingnest.com/modern-sat-solvers-fast-neat-underused-part-1-of-n/ https://codingnest.com/modern-sat-solvers-fast-neat-underuse...
- eru 6y ago> A generic solution won't beat a hand-optimised specific solution, but if you're good at phrasing your problem in the right way, you can get 80 % of the way there with 20 % of the effort by using a generic solver. Using generic solvers is especially useful, because when the problem slightly changes, you don't need to re-write your hand-optimised specific solution from scratch. Generic solvers also naturally make you separate the specification of your solution from your method of finding that solution. With hand-crafted approaches, almost always the implementation (of the solver) becomes the de-facto specification. And it's hard to tell which accidental behaviours of the solver are now being relied on by other parts of the system or by users. I have more experience with (Mixed) Integer Programming, but the same principle applies.
- Karrot_Kream 6y ago> I've long wanted to integrate this type of solver into my workflow more, because I think that if I can make it into more of a habit, it would provide insane leverage for prototyping. Does anyone have experience using these techniques for that? In my experience (and I'd love alternate viewpoints here, just because I want to use solvers more!), there are a limited set of areas where SAT, SMT, and MILP solvers are a reasonable choice, but in these situations they really shine. Any time you need to model and reason about something in terms of rules and constraints (business logic validation perhaps, schedules, layout engines, etc) solvers will help you cleanly solve the problem. Of course, then there's the additional problem that large models take large amounts of time to converge, so large problems may require more creative approaches. I've used MILP solvers in the past to determine optimal (given a model) average thread pool sizes, and average batch job wait times as well, but usually operating conditions change so frequently that models often provide poor performance. One of my favorite uses of Z3 though is ZetZ[1] a language that adds a verification layer atop C.
- kqr 6y agoYou're probably not wrong, because what you're saying seems to be conventional wisdom. However, there's a part of me that can't help thinking, "...but that's only because we're not used to thinking of our problems in terms of rules and constraints. If we got into the habit of doing it, we'd soon find out that more and more of our problems are of the rules-and-constraints kind, if only looked at the right way." There's also an argument that you can turn any problem into rules and constraints, but doing so might not help you. I'm taking the stance here that maybe for a larger class of problems than we think it is actually helpful to think of them as rules and constraints. And then it's a small step to apply a generic solver as the first, baseline approach. So my argument is not really that "we should apply solvers wherever they are currently immediately obviously useful" but more that "there might be a high-potential paradigm shift hidden here where we as a profession can adapt a new way of thinking based on off-the-shelf solvers for generic problems, if only we learn to view the world that way, and this might turn out to be a better way to think of the lower level components of software engineering."
- 112233 6y agoHave a look at github.com/Shelwien/sudoku-cbmc for a “neat hack” that abuses the C bounded model checker to, basically, run a sat solver on a problem written in C.
- ritter2a 6y agoI would say that the benefits you get from a habit of using SMT solvers depends a lot on the kind of problems you are working on. If your problem is rather small and self-contained, you can really win a lot with these solvers. E.g. I used an ILP solver to fairly distribute tasks to a group of people based on a heuristic of familiarity between each person and the tasks. That's only a few constraints in the solver that saved me a lot of manual or suboptimal coding work. Similarly, it was easy enough to quickly check whether two graphs satisfy a custom condition that is close to (but not quite) isomorphism that I wanted to give a try. If you are thinking of bigger, more complex tasks, the efficiency gains you get might vary more. If your problem produces many large solver queries, the chances are good that you will wait a long time for results. Without much practice, adjusting/augmenting your specification (and specifically in the case of ILP solvers: tuning the solver parameters) to reduce your solving times is a very non-trivial task. Either way, the solver probably won't bring you to 80% of the execution speed of a custom solution: I once sped up a task by 100-200x by replacing a Gurobi LP with a dumb, theoretically exponential, but easy to optimize custom implementation (the solver was however helpful for testing that the implementation was correct). Lastly, in my experience, once a constraint system/model reaches a certain complexity, it is a lot more difficult to debug than code in a programming language. There are useful techniques and tricks for debugging solver models, but the tooling and the sequential execution of real code make debugging of traditional code less of a head ache.
- whatever1 6y agoBig disadvantage of custom implementations is the fact that they are custom. If you change the constraints / requirements then suddenly they do not work. Tailored implementations are great for problems that you have to solve frequently with no changes to the structure. In reality, requirements frequently change breaking many of previously valid assumptions for efficiently filtering the feasible space.
- bjackman 6y ago> if you're good at phrasing your problem in the right way Check out https://sentient-lang.org/ https://sentient-lang.org/, it's a whole programming language for expressing problems as SAT!
- deleted 6y ago[deleted]