4 ms·
Maybe it's just me, but I feel the same way about MIPS solvers as well. The amount of optimization that has gone into these solvers over decades, and the kind o
by shaklee3 8y ago
Maybe it's just me, but I feel the same way about MIPS solvers as well. The amount of optimization that has gone into these solvers over decades, and the kind of problems they're solving is staggering. Yet, you never hear about them since operations research is not as sexy as deep learning.
- StreakyCobra 8y agoI experimented with MIPS before, mainly for side projects, and I found them amazing for easily solving optimization problems. Reading this article, I felt the logic used for constructing the Sudoku solver is quite close to what I would have done for MIPS: one constraint for one number per row, one constraint for the columns, one constraint for the 3x3 boxes, etc… I am wondering if MIPS and SAT relate together somehow?
- shaklee3 8y agoYou can solve SAT problems using linear programming, I believe. I don't know if the free SAT solvers would compare to a commercial LP solver like gurobi or cplex.
- nhaehnle 8y agoInteger programming, not linear programming. Linear programming (without the integrality constraint) is in P, so you cannot use it to solve general SAT problems, which are NP-complete (unless a major and highly surprising theoretical breakthrough is found). The free SAT solvers are very good, and much better than commercial IP solvers at solving problems that are a natural fit for SAT. (Obviously, you can encode any IP as an SAT formula and vice versa, and the IP solvers are better at solving the problems where you actually have meaningful arithmetic.)
- shaklee3 8y agoThanks for clearing that up!
- nickpsecurity 8y agoI hadn't even heard of them before now. Mixed-Integer Programming Solvers is what I found looking up the term. What are the best free ones to check out? And anyone got good tutorials w/ examples? I'll start keeping an eye out for CompSci work on them if they're really useful.
- allenz 8y agoYou should use a modeling library which abstracts away from individual solvers, such as pyomo for Python: http://www.pyomo.org http://www.pyomo.org Gurobi is the fastest solver, and it's free for college students. SCIP, MIPCL, and CBC are the fastest free solvers, in that order. To learn how to formulate a problem as a linear program, you can read through the examples at https://people.eecs.berkeley.edu/~vazirani/algorithms/chap7.pdf https://people.eecs.berkeley.edu/~vazirani/algorithms/chap7....
- nickpsecurity 8y agoThanks! Edit: "Pyomo supports a wide range of problem types, including: Linear programming Quadratic programming Nonlinear programming Mixed-integer linear programming Mixed-integer quadratic programming Mixed-integer nonlinear programming Stochastic programming Generalized disjunctive programming Differential algebraic equations Bilevel programming Mathematical programs with equilibrium constraints" Love it when someone links to one thing that has a pile of links to other useful techniques to learn about. :)
- allenz 8y agoI recommend learning linear programming first. It's simple and useful, and makes it easier to understand quadratic programming, convex optimization, etc.
- cjhanks 8y agoYeah, way to provide some great references here. Thanks.
- aidos 8y ago