3 ms·

I used MiniZinc on the capacitated vehicle routing problem in a combinatorial optimization project course a couple of years ago, and really enjoyed it. The swe

by jlgray 9y ago

I used MiniZinc on the capacitated vehicle routing problem in a combinatorial optimization project course a couple of years ago, and really enjoyed it. The sweet spot for MiniZinc is in investigating a problem and prototyping a solution. I would say it takes 10-20 hours to get a workable understanding of the language and paradigm, plus or minus your previous experience. However, MiniZinc is built on backtracking, which scales poorly to real world instances of np-hard problems.

gjem97 9y ago
My understanding was that there are many solvers that you can use. Do they all backtrack?
- jsjolen 9y ago
  The goal of a constraint solver is to bind (constrain) all of the defined variables to a single value which satisfies the constraints put upon that variable. This is in essence traversing through a search tree (through DFS) and finding a valid end-node. This means that when we find an invalid end-node (for example by running out of possible values for a variable) then we must in some way go back up the search tree. There are several different ways of doing this. Short answer: Yes, we must backtrack somehow.
- CJefferson 9y ago
  In some vague sense, any solver for an NP-complete problem, must either backtrack, or keep accumulating information and possibly exhaust memory. In practice every practical solver I know of for NP-complete problems backtracks. Now, they often do all kinds of other clever things on top (learning, restarts, parallelisation, heuristics), but when the going gets tough, there is a lot of backtracking.
lambdadmitry 9y ago
You can always use MiniZinc (or any other CP solver) to make a "large neighborhood search" where you do local optimization over subproblems, feeding subproblems into the constraint solver. As far as I know, this is one of the most successful approaches for big problems.

by jlgray 9y ago

gjem97 9y ago

My understanding was that there are many solvers that you can use. Do they all backtrack?

jsjolen 9y ago
The goal of a constraint solver is to bind (constrain) all of the defined variables to a single value which satisfies the constraints put upon that variable. This is in essence traversing through a search tree (through DFS) and finding a valid end-node. This means that when we find an invalid end-node (for example by running out of possible values for a variable) then we must in some way go back up the search tree. There are several different ways of doing this. Short answer: Yes, we must backtrack somehow.
CJefferson 9y ago
In some vague sense, any solver for an NP-complete problem, must either backtrack, or keep accumulating information and possibly exhaust memory. In practice every practical solver I know of for NP-complete problems backtracks. Now, they often do all kinds of other clever things on top (learning, restarts, parallelisation, heuristics), but when the going gets tough, there is a lot of backtracking.

lambdadmitry 9y ago

You can always use MiniZinc (or any other CP solver) to make a "large neighborhood search" where you do local optimization over subproblems, feeding subproblems into the constraint solver. As far as I know, this is one of the most successful approaches for big problems.