The Snake Eggs Puzzle: Preparing Students for Benders Decomposition

[摘要] Logic puzzles are an effective way to introduce students to advanced solution techniques in operations research, such as Lagrangian relaxation, Dantzig-Wolfe decomposition, and Benders decomposition. The Snake Egg puzzle asks the player to draw a one-cell wide path, or “snake,” in a grid. The remaining cells should form a fixed number of separate, connected, discontiguous regions called “eggs.” We propose two solution approaches: a flowbased model and lazy constraints. Instead of providing the complete model at the outset, we will step through the puzzle in a manner suitable to the classroom, emphasizing the skills that are crucial to successfully implementing advanced techniques. The puzzle functions in particular as a prelude to Benders decomposition.

[学科分类] 数学（综合）

[关键词] integer programming;puzzles;lazy constraints;Benders decomposition