Solving a logic puzzle via mathematical programming

Mathematics and Computer Education, Fall 2002 by Saltzman, Robert M, Kohler, David

1. INTRODUCTION

In recent years, introductory courses in operations research and mathematical modeling have increasingly employed a spreadsheet environment to engage students and provide a solution framework for problems. Well-known proponents of using a spreadsheet approach, particularly Microsoft Excel, instead of specialized software for teaching students include Grossman [3], Moore and Weatherford [4], Ragsdale [6], Savage [7], and Winston and Albright [10].

In this article we explore the relative strengths and weaknesses of the spreadsheet approach versus specialized mathematical programming software for solving a particular logic puzzle. The puzzle itself is fun and can be solved manually, in perhaps half an hour or so. However, its formulation in Excel reveals a number of interesting techniques useful for solving other constraint satisfaction and combinatorial problems in this environment. A more parsimonious formulation in OPL Studio (ILOG [51) is easily extendable to larger problems and conveys some of the power of specialized mathematical programming software. An undergraduate majoring in operations research or decision sciences could benefit from seeing both approaches to solving a problem such as this.

2. PROBLEM STATEMENT

To illustrate our ideas we use the following logic puzzle, which we call "Who Owns the Fish?" Unfortunately, we do not know the puzzle's origin.

6. REFERENCES

1. Daniel Fylstra, Leon Lasdon, John Watson, and Allan Waren, "Design and Use of the Microsoft Excel Solver", Interfaces, Vol. 28, No. 5, pp. 29-55 (1998).

2. Saul I. Gass, David S. Hirshfeld, and Edward A. 28, No. 5, "Model World: 29-55 (1998). Spreadsheeting of OR/MS", Interfaces, David S. 30, No. 5, and Edward A. 72-81 "Model World: The 3. Thomas A. Grossman, "Teacher's Forum: Spreadsheet Modeling of OR/MS", Interfaces, Vol. 30, No. 5, pp. Simulation

3. Thomas A. Grossman, "Teachers Forum: Spreadsheet Modeling of Queues", Interfaces, Vol. 29, No. 3, pp. Simulation (1999).

4. Jeffrey H. Moore and Larry R. Weatherford, Decision Modeling with Microsoft Excel, 6h Edition, Prentice Hall, Upper Saddle River, NJ (2001).

5. ILOG, OPL Studio 3.0 User's Manual, Gentilly, France (2000).

6. Cliff T. Ragsdale, Spreadsheet Modeling and Decision Analysis: A Practical Introduction to Management Science, 3' Edition, South-Western, Cincinnati, OH (2001).

7. Sam L. Savage, Insight.xla: Business Analysis Software for Microsoft Excel, Brooks/Cole, Pacific Grove, CA (1998).

8. Christopher Skiscim, "Software Review: OPL Studio 3.1," OR/MS Today, Vol. 28, No. 2, pp. 70-72 (2001).

9. Pascal Van Hentenryck, The OPL Optimization Programming Language, MIT Press, Cambridge, MA (1999).

10. Wayne L. Winston and S. Christian Albright, Practical Management Science, 2' Edition, Brooks/Cole, Pacific Grove, CA (2001).

Robert M. Saltzman and David Kohler

Information Systems and Business Analysis Department College of Business

San Francisco State University 1600 Holloway Avenue

San Francisco, California 94132