TY - GEN

T1 - A novel linear milp model to solve kakuro puzzles

AU - Fonseca, José Barahona da

AU - DEE Group Author

N1 - This work has been considered by the reviewers as an important contribution to the optimization and artificial intelligence fields

PY - 2012/1/1

Y1 - 2012/1/1

N2 - : It is shown that a Kakuro puzzle is a NP-Hard problem and very nonlinear since it implies the comparison of segment sums with their desired values, and humans have a lot of difficulty to solve Kakuro puzzles. By the contrary our mixed integer linear programming (MILP) model, using the Cplex solver, solves very hard puzzles in a fraction of a second. We begin to explain why humans have a so great difficulty to solve Kakuro puzzles, even for low level of difficulty ones. Then we review briefly our previous work where we describe linearization techniques that allow solving any nonlinear problem with a MILP model. Next we describe the constraints and their implementation with the GAMS software and finally we compare the runtimes of our MILP model with previous MILP models using a black belt Kakuro puzzle.

AB - : It is shown that a Kakuro puzzle is a NP-Hard problem and very nonlinear since it implies the comparison of segment sums with their desired values, and humans have a lot of difficulty to solve Kakuro puzzles. By the contrary our mixed integer linear programming (MILP) model, using the Cplex solver, solves very hard puzzles in a fraction of a second. We begin to explain why humans have a so great difficulty to solve Kakuro puzzles, even for low level of difficulty ones. Then we review briefly our previous work where we describe linearization techniques that allow solving any nonlinear problem with a MILP model. Next we describe the constraints and their implementation with the GAMS software and finally we compare the runtimes of our MILP model with previous MILP models using a black belt Kakuro puzzle.

KW - Optimization problems

KW - Mathematical programming

KW - Operations research

KW - Linear programming

KW - Artificial intelligence

M3 - Conference contribution

SP - 54

EP - 60

BT - Proceedings of Controlo 2012 Conference

T2 - Controlo 2012

Y2 - 1 January 2012

ER -