Hacker News Reader

Comment by shaklee3 | Hacker News Reader

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.

View on HN

I 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?

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

Integer 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.)

Thanks for clearing that up!

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

You should use a modeling library which abstracts away from individual solvers, such as pyomo for Python: 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....

We use SCIP in our system and it’s brilliant. They have proper python bindings so the call overhead is low. We reduced what was previously a complex hand optimised algorithm to a handful of equations a weight function. Highly recommended.

https://github.com/SCIP-Interfaces/PySCIPOpt

Thanks!

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

I recommend learning linear programming first. It's simple and useful, and makes it easier to understand quadratic programming, convex optimization, etc.

Yeah, way to provide some great references here. Thanks.

Reply on news.ycombinator.com