Solving an Urban Planning Puzzle with JuMP + Julia

http://iaindunning.com/2013/urban-planning.html

by idunning • 13 years ago

17 3 13 years ago

andrewcooke2• 13 years ago

i guess this is a series of posts on showing different uses for JuMP? because otherwise, wouldn't it make more sense to use a SAT solver, or ASP? are wrappers for any of those available in Julia?

(i'm not complaining; i'm learning about all this stuff - have recently been looking at potassco - and am trying to get clear what tool fits where).

idunning• 13 years ago

It is primarily to showcase JuMP, yes. I also hoped it'd introduce more people to MIP, something not often covered in CS education.

As for using other techniques, I don't think it necessarily makes more sense to use them. The natural statement of the problem is an optimization problem, not a constraint satisfaction problem, so using an optimization method seems reasonable to me. On problems that are highly constrained (few/one feasible solution[s]) it would probably make more sense to try a constraint programming approach, but this particular problem has many (too many?) feasible solutions so I don't think there is any reason to believe they'd be better.

One downside to MIP is the need to model the logical constraints as linear equations, which is perhaps less expressive than the way you can often express constraints in constraint programming languages.

andrewcooke2• 13 years ago

actually, i didn't read the problem fully (sorry) - i just saw that your article seemed to be mainly about embedding boolean variables in integer programming. now that i've gone back to read the problem i agree completely - i don't see how to do that (sanely) with boolean logic alone.

ps incidentally, with choco (the only CSP/CP solver i've used) you can use regular expressions that make scoring like this very easy (match 5 residential, score ...). http://www.emn.fr/z-info/choco-solver/ - unfortunately (for julia) it's implemented in java. if you're looking for other interesting puzzles, i had a lot of fun with choco and pipes - see items mentioning choco at http://isti.bitbucket.org/ or the original so post http://stackoverflow.com/questions/9689436/backtracking-solu...

Solving an Urban Planning Puzzle with JuMP + Julia

Related Stories