The Snake Eggs Puzzle: Preparing Students for Benders Decomposition

Mitchell Harris () and Michael Forbes ()
Additional contact information
Mitchell Harris: School of Mathematics and Physics, The University of Queensland, Brisbane, St Lucia, QLD 4072, Australia
Michael Forbes: School of Mathematics and Physics, The University of Queensland, Brisbane, St Lucia, QLD 4072, Australia

INFORMS Transactions on Education, 2023, vol. 23, issue 3, 210-217

Abstract: 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 flow-based 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.

Keywords: integer programming; puzzles; lazy constraints; Benders decomposition (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ited.2023.0281 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orited:v:23:y:2023:i:3:p:210-217

Access Statistics for this article

More articles in INFORMS Transactions on Education from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().