A novel linear milp model to solve kakuro puzzles

José Barahona da Fonseca; DEE Group Author

A novel linear milp model to solve kakuro puzzles

José Barahona da Fonseca, DEE Group Author

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

: 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.

Original language	Unknown
Title of host publication	Proceedings of Controlo 2012 Conference
Pages	54-60
Publication status	Published - 1 Jan 2012
Event	Controlo 2012 - Duration: 1 Jan 2012 → …

Conference

Conference	Controlo 2012
Period	1/01/12 → …

Cite this

@inproceedings{901599d83cbe48dcabd31ee94c4479ff,

title = "A novel linear milp model to solve kakuro puzzles",

abstract = ": 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.",

keywords = "Optimization problems, Mathematical programming, Operations research, Linear programming, Artificial intelligence",

author = "Fonseca, {Jos{\'e} Barahona da} and {DEE Group Author}",

note = "This work has been considered by the reviewers as an important contribution to the optimization and artificial intelligence fields; Controlo 2012 ; Conference date: 01-01-2012",

year = "2012",

month = jan,

day = "1",

language = "Unknown",

pages = "54--60",

booktitle = "Proceedings of Controlo 2012 Conference",

}

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 -