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

Specific Domains Optimization (Mathematical)
1

Hello,

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?

Regards
Rafal

2

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

3

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.

4

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

5

Well, anyone can give you an incorrect answer quickly…

4 Likes
6

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.

2 Likes
7

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.