JuMP --> Cbc infeasibility due to too many (valid) constraints?



I’m solving a numeric crosswords (something like this), and I run into an odd issue. I’m using integer programming and Cbc solver. If I type in all the constraints resulting from the given clues (sums of digits in all given groups), I receive following error:

WARNING: Not solved to optimality, status: Infeasible
WARNING: Infeasibility ray (Farkas proof) not available
WARNING: Variable value not defined for x. Check that the model was properly solved.

If I remove a few clues randomly, then the problem gets solved correctly. Some clues are more sensitive than others. I found a single clue, which can be omitted and solution is found. If I add that specific clue, I need to remove about 5 other clues in order to don’t have the above quoted error. All the clues are perfectly valid and not contradicting themselves. Even typing a few obvious hints, like “put 4 in this cell”, which theoretically should simplify the problem, causes above error.

Question: what exactly the error means and how can I get better insight into what is actually wrong? Or is it Cbc bug?



It wouldn’t be surprising if Cbc incorrectly declared the problem infeasible. Try another solver like GLPK to debug.


Yes, I figured I’d try GLPK. Just running it now, but it seems to be much slower. Cbc took max 1 minute, whereas GLPK is running already ~30 minutes and still didn’t finish. Not sure if it will finish in reasonable time at all. The good point is, that it didn’t claim “infeasible” till now.


*** UPDATE ***
GLPK solved correctly without errors. The only issue is, that it took 80 minutes for him, vs 1 minute from Cbc.


Well, anyone can give you an incorrect answer quickly…


You might want to give a CP solver a try, these solvers are idea for combinatorial puzzles like the one you mention. MiniZinc is an easy way to get started with such solvers.


MiniZinc looks interesting. It provides conditional constraints out of the box and takes care of translating it into regular set of linear equations. Thank you for this tip.