IDEAS home Printed from https://ideas.repec.org/a/inm/orited/v23y2023i3p210-217.html
   My bibliography  Save this article

The Snake Eggs Puzzle: Preparing Students for Benders Decomposition

Author

Listed:
  • 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)

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.

Suggested Citation

  • Mitchell Harris & Michael Forbes, 2023. "The Snake Eggs Puzzle: Preparing Students for Benders Decomposition," INFORMS Transactions on Education, INFORMS, vol. 23(3), pages 210-217, May.
    • Handle: RePEc:inm:orited:v:23:y:2023:i:3:p:210-217
    DOI: 10.1287/ited.2023.0281
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ited.2023.0281
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ited.2023.0281?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. G. Dantzig & R. Fulkerson & S. Johnson, 1954. "Solution of a Large-Scale Traveling-Salesman Problem," Operations Research, INFORMS, vol. 2(4), pages 393-410, November.
    2. Robin H. Pearce & Michael A. Forbes, 2017. "Puzzle—The Fillomino Puzzle," INFORMS Transactions on Education, INFORMS, vol. 17(2), pages 85-89, January.
    3. SönkeHartmann, 2018. "Puzzle—Solving Smartphone Puzzle Apps by Mathematical Programming," INFORMS Transactions on Education, INFORMS, vol. 18(2), pages 127-141, January.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Sascha Wörz, 2017. "On global integer extrema of real-valued box-constrained multivariate quadratic functions," Journal of Combinatorial Optimization, Springer, vol. 34(3), pages 964-986, October.
    2. Maria Michela Dickson & Yves Tillé, 2016. "Ordered spatial sampling by means of the traveling salesman problem," Computational Statistics, Springer, vol. 31(4), pages 1359-1372, December.
    3. Manfred Padberg, 2005. "Classical Cuts for Mixed-Integer Programming and Branch-and-Cut," Annals of Operations Research, Springer, vol. 139(1), pages 321-352, October.
    4. Schulz, Arne & Pfeiffer, Christian, 2024. "Using fixed paths to improve branch-and-cut algorithms for precedence-constrained routing problems," European Journal of Operational Research, Elsevier, vol. 312(2), pages 456-472.
    5. Letchford, Adam N. & Nasiri, Saeideh D. & Theis, Dirk Oliver, 2013. "Compact formulations of the Steiner Traveling Salesman Problem and related problems," European Journal of Operational Research, Elsevier, vol. 228(1), pages 83-92.
    6. Pamela J. Palomo-Martínez & M. Angélica Salazar-Aguilar & Víctor M. Albornoz, 2017. "Formulations for the orienteering problem with additional constraints," Annals of Operations Research, Springer, vol. 258(2), pages 503-545, November.
    7. Gianpaolo Ghiani & Gilbert Laporte & Frédéric Semet, 2006. "The Black and White Traveling Salesman Problem," Operations Research, INFORMS, vol. 54(2), pages 366-378, April.
    8. Balma, Ali & Salem, Safa Ben & Mrad, Mehdi & Ladhari, Talel, 2018. "Strong multi-commodity flow formulations for the asymmetric traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 271(1), pages 72-79.
    9. Roel G. van Anholt & Leandro C. Coelho & Gilbert Laporte & Iris F. A. Vis, 2016. "An Inventory-Routing Problem with Pickups and Deliveries Arising in the Replenishment of Automated Teller Machines," Transportation Science, INFORMS, vol. 50(3), pages 1077-1091, August.
    10. Könnyű, Nóra & Tóth, Sándor F., 2013. "A cutting plane method for solving harvest scheduling models with area restrictions," European Journal of Operational Research, Elsevier, vol. 228(1), pages 236-248.
    11. Jiachen Zhang & Youcef Magnouche & Pierre Bauguion & Sebastien Martin & J. Christopher Beck, 2024. "Computing Bipath Multicommodity Flows with Constraint Programming–Based Branch-and-Price-and-Cut," INFORMS Journal on Computing, INFORMS, vol. 36(6), pages 1634-1653, December.
    12. Jovanović, Predrag & Pavlović, Norbert & Belošević, Ivan & Milinković, Sanjin, 2020. "Graph coloring-based approach for railway station design analysis and capacity determination," European Journal of Operational Research, Elsevier, vol. 287(1), pages 348-360.
    13. Koç, Çağrı & Bektaş, Tolga & Jabali, Ola & Laporte, Gilbert, 2016. "The fleet size and mix location-routing problem with time windows: Formulations and a heuristic algorithm," European Journal of Operational Research, Elsevier, vol. 248(1), pages 33-51.
    14. Lisa K. Fleischer & Adam N. Letchford & Andrea Lodi, 2006. "Polynomial-Time Separation of a Superclass of Simple Comb Inequalities," Mathematics of Operations Research, INFORMS, vol. 31(4), pages 696-713, November.
    15. Oruc, Buse Eylul & Kara, Bahar Yetis, 2018. "Post-disaster assessment routing problem," Transportation Research Part B: Methodological, Elsevier, vol. 116(C), pages 76-102.
    16. Briant, Olivier & Cambazard, Hadrien & Cattaruzza, Diego & Catusse, Nicolas & Ladier, Anne-Laure & Ogier, Maxime, 2020. "An efficient and general approach for the joint order batching and picker routing problem," European Journal of Operational Research, Elsevier, vol. 285(2), pages 497-512.
    17. Pang Du & Christopher F. Parmeter & Jeffrey S. Racine, 2012. "Nonparametric Kernel Regression with Multiple Predictors and Multiple Shape Constraints," Department of Economics Working Papers 2012-08, McMaster University.
    18. De la Fuente, Rodrigo & Aguayo, Maichel M. & Contreras-Bolton, Carlos, 2024. "An optimization-based approach for an integrated forest fire monitoring system with multiple technologies and surveillance drones," European Journal of Operational Research, Elsevier, vol. 313(2), pages 435-451.
    19. Dahlbeck, Mirko & Fischer, Anja & Fischer, Frank, 2020. "Decorous combinatorial lower bounds for row layout problems," European Journal of Operational Research, Elsevier, vol. 286(3), pages 929-944.
    20. Rey, David & Almi’ani, Khaled & Nair, Divya J., 2018. "Exact and heuristic algorithms for finding envy-free allocations in food rescue pickup and delivery logistics," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 112(C), pages 19-46.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:orited:v:23:y:2023:i:3:p:210-217. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.