Scheduling a Bridge Club (A Case Study in Discrete Optimization)
Bruce S. Elenbogen, Bruce R. Maxim · Mathematics Magazine · 1992
Introduction Interesting mathematics problems arise from a wide variety of sources in everyday life. This paper explores a scheduling problem that was presented to one of the authors by a local bridge club. Although the problem appears simple on the surface, analysis uncovers a complexity that is often present in simply stated discrete optimization problems, and illustrates pitfalls that can arise from naively applying brute force techniques on the computer. The paper first defines the problem and explores the meaning of arn optimal solution. Next an analytical solution is sought based on the classification of the problem, and finally the paper considers four increasingly sophisticated techniques of discrete optimization. Historically, optimization problems have arisen in a variety of applications including electrical engineering, operations research, computer science, and communication. Although a variety of techniques for solving linear and non-linear optimization problems with continuous variables has been well known for 25 years [2, 4, 15], it is only recently that progress has been made in solving optimization problems involving discrete variables [9, 101. This paper examines a variety of these discrete techniques in the context of solving one specific scheduling problem.