Resources for Math 381

Dr. Conroy's lecture materials

Videos

• Intro to LP
• More LP
• More LP: The Diet Problem
• Integer Programming
• More Integer Programming
• More IP: Graph Coloring
• More IP: Scheduling
• LP Logic
• The Small World Problem
• Traveling Salesperson Problem, I
• Traveling Salesperson Problem, II
• Stepwise methods
• Intro to Markov Chains
• More Markov Chains
• Monte Carlo Methods, I
• Monte Carlo Methods, II
• Monte Carlo: No Thanks game simulation
• Intro to Queuing Theory
• More Queuing Theory
• Random numbers
• Simulating queues
• Poisson processes
• Intro to multidimensional scaling
• More multidimesional scaling

Books

• Sara Billey, James Burke,Tim Chartier, Anne Greenbaum and Randy LeVeque, Discrete Mathematical Modeling, 2010. pdf.
• Applied Mathematical Programming by Bradley, Hax, and Magnanti (Addison-Wesley, 1977). pdf (20 meg)   pdf (chapter 9, Integer Programming, only)
• Basic Probability Theory, by Robert B. Ash. pdf chapters.

• F. S. Roberts, Applied Combinatorics, Prentice-Hall, Englewood Cliffs, N.J., 1984.
• F. S. Roberts, Discrete mathematical models, with applications to social, biological, and environmental problems, Prentice-Hall, Englewood Cliffs, N.J., 1976.
• D. P. Gaver and G. L. Thompson, Programming and probability models in operations research, Brooks/Cole Pub. Co., 1973.
• F. S. Hillier and G. J. Lieberman, Introduction to operations research, McGraw-Hill, New York, 1995.
• M. M. Meerschaert, Mathematical Modeling, Academic Press, San Diego, 1993.
• S. M. Ross, A Course in Simulation, Macmillan Publishing Company, New York, 1990.
• W. L. Winston, Operations Research; Applications and Algorithms, Brooks/Cole, 2004.

Blogs

• Punk Rock Operations Research

Software

• PARI/GP. Free, open source library and command-line front end computer algebra system. I use this all the time. Exact calculations are one of its strengths.
• Sage. Free, open source computer algebra system. Very powerful, can do anything Mathematica, Maple, Matlab, etc. can do, but it is free. Nice tools for studying graphs, good plotting tools, lots of great stuff.
• R. Free software environment for statistical computing and graphics. Can do LP, IP, MDS, and lots of other stuff.
• lpsolve. Free, open source LP solver. Easier to use for LPs than R.
• LaTeX. THE way to typeset mathematics and mathematical works. Totally free.

Examples and things to inspire project ideas

• General
• Sabermetrics (mathematics applied to baseball) course at Williams College link.
• Linear programming
• Gerald G. Brown and Robert F. Dell, Formulating Integer Linear Programs: A Rogues' Gallery. pdf.
• Bradley, Hax and Magnani, Applied Mathematical Programming, Chapter 8. pdf.
• Software
• lpsolve - this is perhaps the best free LP solver; you can find a version that will run on most any machine
• Sourceforge page
• lp-format
• options when running lpsolve
• Professor Burke has a large list of problems that can be formulated as LPs here.
• Diet problem
• "The Diet Problem", George B. Dantzig,Interfaces,Vol. 20, No. 4, The Practice of Mathematical Programming (Jul. - Aug., 1990), pp. 43-47
• Wikipedia page for Stigler_diet
• Transportation problem
• Shun-Chen Liu, "The Transportation Problem: LP Formulations"
• Knapsack problem
• Silvano Martello and Paolo Toth, Knapsack Problems. See Chapter 2, especially.
• Cellular automata
• Robert A. Bosch, Integer Programming and Conway's Game of Life, SIAM Review, 41(1), pp.594-604, pdf
• Chess-related
• L.R. Foulds and D.G. Johnston, An Application of Graph Theory and Integer Programming: Chessboard Non-attacking puzzles, Mathematics Magazine, Vol. 57, No. 2, (Mar. 1994), pp. 95-104. link.
• Martin J. Chlond, (2010) Puzzle-Knight Domination of 2-D Surfaces: A Spreadsheet Approach. INFORMS Transactions on Education 10(2):98-101.pdf
• Puzzles
• Fumika Kino and Yushi Uno, An Integer Programming Approach to Solving Tantrix on Fixed Boards, Algorithms, 2012, 5, 158-175.pdf.
• Andrew C. Bartlett et al, An Integer Programming Model for the Sudoku Problem. pdf.
• W. J. M. Meuffels and D. den Hertog, Solving the Battleship Puzzle as an Integer Programming Problem, Informs: Transactions on Education, Vol. 10, No. 3, May 2010, pp. 156-162. pdf.
• J. M. Wilson, Crossword Compilation Using Integer Programming, 1989. pdf.
• Scheduling
• Caleb White, et al, Creating Weekly Timetables to Maximize Employee Preferences. pdf.
• Lorraine Trilling, Alain Guinet, Dominique Le Magny, Nurse scheduling using integer linear programming and constraint programming, 12th IFAC Symposium on Information Control Problems in Manufacturing INCOM 2006, Sep 2007, Saint-Etienne, France. Elsevier, 3, pp.651-656, 2006. link.
• Music
• Iannis Xenakis, Formalized Music: Thought and Mathematics in Computation, 1992, Pendragon Press [see chapter IV]. pdf
• Tsubasa Tanaka and Koichi Fujii, Describing Global Musical Structures by Integer Programming on Musical Patterns, in Mathematics and Computation in Music, Volume 9110, pp. 52-63. link
• Manufacturing
• Carina Pimentel et al, A Scheduling Model For A Knitting Planning Problem, Manufacturing Fundamentals: Necessity and Sufficiency, Chapter 16. pdf.
• Sports
• Charles Fleurent and Jacques A. Ferland, Allocating Games for the NHL Using Integer Programming, Operations Research, Vol. 41, No. 4, pp.649-654 JSTOR
• George L. Nemhauser and Michael A. Trick, Scheduling a Major College Basketball Conference, Operations Research, Vol. 46, No. 1 pdf
• Optimally Resting NBA Players blog post
• Game Theory
• John G. Kemeny, J. Laurie Snell, and Gerald L. Thompson, Linear Programming and the Theory of Games, chapter 7 in Introduction to Finite Mathematics pdf
• Other
• Diane Perez, How Do Restaurants Use Linear Programming for Menu Planning? (This is not well written, but it might give you some ideas.)
• A blog post connecting linear programming and World of Warcraft. link.
• Paying off debt efficiently (StackExchange question). link.
• Davi Tozoni, Pedro de Rezende, Cid de Souza, A Practical Iterative Algorithm for the Art Gallery Problem using Integer Linear Programming pdf
• Dynamic linear programming
• C. D. Throsby, Some Notes On Dynamic Linear Programming, Review of Marketing and Agricultural Economics, 01/1962, 30(02)
• Graph theory
• Awesome wikipedia page of named graphs
• Big list of what Sage can do with graphs
• graph coloring
• Graph coloring at Wikipedia
• Mathematics of Sudoku
• traveling salesperson problem (TSP)
• TSP at Wikipedia
• From Donald Davendra (Ed.), "Traveling Salesman Problem, Theory and Applications", Chapter 1: Rajesh Matai, Surya Prakash Singh and Murari Lal Mittal, Traveling Salesman Problem: An Overview of Applications, Formulations, and Solution Approaches.pdf.
• Gabor Pataki, "The bad and the good-and-ugly: formulations for the traveling salesman problem" (a quick description and comparison of two popular subtour exclusion methods)
• Approximating algorithms
• Birsen Irem Selamoglu and Abdellah Salhi, The Strip Algorithm Revisited, International Conference on Metaheuristics and Nature Inspired Computing (2014). pdf.
• Applications
• Welding
• Andras Kovacs, Task Sequencing for Remote Laser Welding in the Automotive Industry, Proceedings of the 23rd International Conference on Automated Planning and Scheduling, pp 457-461. pdf.
• Surgery
• JL Falcon, X Chen, GG, Hamad, The traveling salesman problem in surgery: economy of motion for the FLS Peg Transfer task, Surg Endosc 2013 May:27(5):1636-41. link.
• small-world networks
• Wikipedia links:
• small-world networks
• small-world experiment
• clustering coefficient
• average shortest path
• Watts-Strogatz model
• Jeffrey Travers and Stanley Milgram, An Experimental Study of the Small World Problem, Sociometry, Vol. 32, No. 4, (Dec. 1969), pp. 425-443. pdf.
• NY Times article about Facebook small world calculation. link.
• Information about the Erdos number graph. link.
• Duncan J. Watts and Steven H. Strogatz, Collective Dynamics of 'small-world' Networks, Nature, Vol. 393, June 1998. pdf.
• Collaboration in artistic performance
• Brian Uzzi and Jarrett Spiro, Collaboration and Creativity: The Small World Problem, American Journal of Sociology, 111(2) (September 2005): 447-504. pdf.
• centrality measures
• Graphs and Game of Thrones
• Markov chains
• References
• Sara Billey, James Burke,Tim Chartier, Anne Greenbaum and Randy LeVeque, Discrete Mathematical Modeling, 2010, Chapter 5. pdf
• Brian Hayes, First Links in the Markov Chain, American Scientist web page
• Applications
• General
• Philipp Von Hilgers and Amy N. Langville, The Five Greatest Applications of Markov Chains. pdf.
• Biology/Chemistry/Medicine
• Elise F. Zipkin, Christopher S. Jennelle, and Evan G. Cooch, A primer on the application of Markov chains to the study of wildlife disease dynamics, Methods in Ecology & Evolution 2010,1, 192-198. link.
• S. Lee, J. Ko, Xi Tan, Isha Patel, R. Balkrishnan, and J. Chang, Markov Chain Modeling Analysis of HIV/AIDS Progression: A Race-based Forecast in the United States, Indian Journal of Pharmacological Science,web page
• Sonnenberg FA, Beck JR. Markov models in medical decision making: a practical guide. Med Decis Making. 1993 Oct-Dec;13(4):322-38. doi: 10.1177/0272989X9301300409. PMID: 8246705., pubmed
• Li Z, Derksen H, Gryak J, Hooshmand M, Wood A, Ghanbari H, Gunaratne P, Najarian K. Markov Models for Detection of Ventricular Arrhythmia. Annu Int Conf IEEE Eng Med Biol Soc. 2019 Jul;2019:1488-1491. doi: 10.1109/EMBC.2019.8856504. PMID: 31946175; PMCID: PMC7364610. pubmed
• Tighe et al, Markov chain evaluation of acute postoperative pain transition states, Pain, 2016 Mar 157(3), 717-728. nih link
• B. Kemp and H. Kamphuisen, Simulation of human hypnograms using a Markov chain model, Sleep, 9(3): 405-414. pdf
• Social mobility
• Valentino Dardanoni, Measuring Social Mobility, Journal of Economic Theory, 61, 372-394 (1993). pdf
• Games
• Jason A. Osborne, Markov Chains for the RISK Board Game Revisited, Mathematics Magazine 76 (2003) 129-135. pdf.
• Robert B. Ash and Richard L. Bishop, Monopoly as a Markov Process. pdf.
• Linguistics
• Dmitri V. Khmelev and Fiona J. Tweedie, Using Markov Chains for Identification of Writers, Literary and Linguistic Computing, 2001, vol. 16, no. 4, 299-307. pdf.
• Chapter 8 (Probabilistic Language Models) from Michael Hammond, Introduction to the Mathematics of Language (unpublished?).pdf.
• Tony Fischetti, How to fake a sophisticated knowledge of wine with Markov chains. blog post.
• Brian Hayes, Computer Recreations: A progress report on the fine art of turning literature into drivel, Scientific American, Vol. 249, No. 5 (November 1983), pp. 18-31. pdf.(includes amuusingly dated magazine ads from the 1980s!)
• Music
• Dima Volchenkov and Jean Rene Dawin, Musical Markov Chains, International Journal of Modern Physics: Conference Series, Vol. 16 (2012), 116-135, pdf
• The music section of the Markov chain Wikipedia page.
• Roman Klinger and Gunter Rudolph, Automatic Composition of Music with Methods of Computational Intelligence, WSEAS TRANS. on INFORMATION SCIENCE & APPLICATIONS Issue 3, Volume 4, March 2007. pdf.
• Chris Caulfield, Cooperation between Top-Down and Low-level Markov chains for Generating Rock Drumming, Computer Science Honors Thesis at University of Albany, State University of New York. pdf.
• Sports
• Baseball as a Markov Chain, Mark D. Pankin web page
• Other
• R. Hlavaty and L. Domeova, Students' Progress Through Examination Process as a Markov Chain, International Education Studies, Vol 7, No. 12; 2014 pdf
• Monte Carlo simulation
• Wikipedia article Monte Carlo method
• Especially see the extensive Applications section of that article Applications
• Charles J. Mode (editor), Applications Of Monte Carlo Methods In Biology, Medicine And Other Fields Of Science, Intech. link.
• Shaul Mordechai (editor), Applications of Monte Carlo Method in Science and Engineering, Intech. link.
• Blog post regarding monte carlo simulation and fantasy football leagues. blog.
• Jiri Lahvicka, Using Monte Carlo simulation to calculate match importance: the case of English Premier League. link.
• Ludwig Lauwers, et al, A Monte Carlo model for simulating insufficiently remunerating risk premium: case of market failure in organic farming pdf
• Dr. Kaiju Kahn's Introduction to Monte Carlo Methods in Chemistry, link
• Multidimensional scaling (MDS)
• General reading
• Patrick J. F. Groenen and Ingwer Borg, 2013. "The Past, Present, and Future of Multidimensional Scaling," Econometric Institute Research Papers EI 2013-07, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute. pdf
• Gale Young and A. S. Householder, Discussion of a set of points in terms of their mutual distances, Psychometrika, Vol. 3, No. 1, March 1938. pdf.
• Applications
• Psychology
• Megan H. Papesh and Stephen D. Goldinger, A multidimensional scaling analysis of own- and cross-race face space, Cognition, Volume 116, Issue 2, August 2010, Pages 283-288.link.
• Marta L. Axelson, et al, An Analysis of the Four Food Groups Using Multidimensional Scaling, Journal of Nutrition Education, Vol 18 Issue 6, Dec. 1986, pp. 265-273.link.
• Marc L. Carter, et al, Perception of Sports Photographs: A Multidimensional Scaling Analysis, Perceptual and Motor Skills, 2001, 92, 643-652. pdf.
• Michael H. Hall, Perception of sports activities: a multidimensional scaling analysis link.
• Susan S. Schiffman and Charles Dackis, Taste of nutrients: Amino acids, vitamins and fatty acids, Perception & Psychophysics, 1975, Vol. 17(2), 140-146. pdf
• Food
• (Blog post) Seeing India through Food - An Experiment in Multidimensional Scaling. blog post.
• Timbre
• Paul Iverson and Carol L. Krumhansl, Isolating the dynamic attributes of musical timbre, J. Acoust. Soc. Am. 94 (5), November 1993.pdf.
• John M. Grey, Multidimensional perceptual scaling of musical timbres, J. Acoust. Soc. Am. 61 (5), May 1977. pdf.