Intro 1: Course Overview, Modeling, and Installing Julia

1. Course Overview

Operations Research (OR) is a discipline that involves the development and application of advanced analytical methods to aid complex decisions. This course will provide students with the skills to be able to apply a variety of analytical methods to a diverse set of applications. Focus will be on how to translate real-world problems into appropriate models and then how to apply computational procedures and data so that the models can be used as aids in making decisions. Applications will include improving the operation of a variety of different production and service systems, including healthcare delivery and transportation systems, and also how OR can be used to make better decisions in areas like sports, marketing, and project management. Prerequisites include undergraduate courses in single variable differential and integral calculus and an introductory course in probability.

Software: Will be using Julia and packages like JuMP and the Gurobi solver, all running in a Jupyter notebook envirnoment. Julia and JuMP are open source and Gurobi, although commercial, can be downloaded for free by students.

Prerequisites include undergraduate courses in single variable differential and integral calculus and an introductory course in probability. Don't need any background in programming since the course will only use Julia for scripting solutions using existing packages.

Textbook: No required textbook. All materials provided. Recommended references (not required, just provides some extra background):

• Robert Hildebrand, Editor, Mathematical Programming and Operations Research: Modeling, Algorithms, and Complexity with Examples in Python and Julia, 2020. Part of the Open Optimization project, current release: https://github.com/open-optimization/open-optimization-or-book/files/5745381/MathematicalProgrammingandOperationsResearch.pdf
• Changhyun Kwon, Julia Programming for Operations Research, 2nd Edition, 2019. Available to read online for free: https://www.softcover.io/read/7b8eb7d0/juliabook2.
• Allen Downey and Ben Lauwens, Think Julia: How to Think Like a Computer Scientist, 2018 is a good book-level intro to Julia, most introductory materials for Julia are videos. Available to read online for free: https://benlauwens.github.io/ThinkJulia.jl/latest/book.html.

Topics

1. Introduction
2. Nonlinear Optimization
3. Linear Programming
4. Network Models
   Exam 1 (take home)
5. Mixed-Integer Programming
6. Combinatorial Optimization
7. Machine Learning
   Exam 2 (take home)
8. Review for Final Exam
   Final Exam (2.5 hour proctored)

Grading

Exams 1 and 2 each represent 20% and the Final Exam 25% of your grade in this class. There will be a homework assignment for each topic that, in total, represents 30% of your grade. The remaining 5% of your grade will be based on your class participation.

2. Modeling

Analysis Triangle

Levels of Modeling

1. Guesstimation (order of magnitude)
2. Mean value analysis (linear, ±20%)
3. Nonlinear models (incl. variance, ±5%)
4. Simulation models (complex interactions)
5. Prototypes/pilot studies
6. Build/do and then tweak it (evolutionary approach)

Guesstimation

Geometric Mean

How many people can be crammed into a car? Certainly more than one and less than 100. The arithmetic mean or average (50) seems to be too high, but the geometric mean (10) is reasonable:

$ \quad\textrm{Geometric Mean: } X = \sqrt{L\!B\times{U\!B}} = \sqrt{1\times{100}} = 10 $

Often it is difficult to directly estimate input parameter $X$, but is easy to estimate reasonable lower and upper bounds ($L\!B$ and $U\!B$) for the parameter:

• Since the guessed $L\!B$ and $U\!B$ are usually orders of magnitude apart, use of the arithmetic mean would give too much weight to $U\!B$
• Geometric mean gives a more reasonable estimate because it is a logarithmic average of $L\!B$ and $U\!B$

Fermi Problems

Fermi Problems, named after the physicist Enrico Fermi, are inspired guesses about quantities that seem almost impossible to determine given the limited data that you have available. Solving a Fermi Problem involves guesstimation of the input parameters needed and back-of-the-envelope type approximations.

• The goal is to have an answer that is within an order of magnitude of the correct answer (or what is termed a zeroth-order approximation).
• It works because the over- and under-estimations of each parameter tend to cancel each other out as long as there is no consistent bias.

Ex 1: How many McDonald’s restaurants in U.S.?

# Parameters (note: orders includes in-store and drive-thru)
LB = 1; UB = 350         # Bounds on per capita demand (order/person-yr)
@show f = sqrt(LB*UB)    # Annual per capita demand (order/person-yr)
q = 3e8                  # U.S. population (person)
H = 16                   # Operating hours per day (hr/day)
r = 1                    # Orders per store per minute (order/store-min)
# Analysis
@show q*f                # Annual U.S. demand (order/yr)
@show q*f/365            # Daily U.S. demand (order/day)
@show H*60*r             # Daily demand per store (order/store-day)
(q*f/365)/(H*60*r)       # Est. number of U.S. stores (store)

f = sqrt(LB * UB) = 18.708286933869708
q * f = 5.6124860801609125e9
(q * f) / 365 = 1.5376674192221679e7
H * 60 * r = 960

16017.368950230915

“Reasonable” guesstimates can be made for all of the parameters needed to make the estimation except for customer demand; as a result, the geometric mean of the estimated lower and upper bounds on demand is used as the estimate. The actual number of McDonald’s restaurants in the U.S. as of 2013 is 14,267, which is around 10% below the estimate. A key assumption in the analysis is that the number of McDonald’s restaurants in the U.S. has reached market saturation, allowing the entire U.S. population to be used as the customer base.

System Performance Estimation

Often easy to estimate performance of a new system if can assume either perfect (LB) or no control (practical UB), as opposed trying to develop a more detailed model of performance.

Ex 2: Estimate the waiting time for a bus If, during the morning rush, there are five buses operating on Wolfline Route 13 and it takes them 40 minutes, on average, to complete one circuit of the route, what is the estimated waiting time for a student who does not use TransLoc for real-time bus tracking?

• $ \frac{40}{5} = 8 $ min. avg. time (aka “headway”) between buses
• Customers arrive at random (assuming no web-based bus tracking)
• Perfect control (LB): wait time = half of headway = 8/2
• No control (practical UB): wait time = headway = 8
  • Assuming buses arrive at random (Poisson process)
  • Bad control can result in higher values than no control

headway = 8
LB = headway/2       # perfect control
UB = headway
Estimated_wait_time = sqrt(LB*UB)  # (min)

5.656854249492381

Ex 3: Amount spent per grocery trip
Estimate the average amount spent per trip to a grocery store. Total U.S. supermarket sales were recently determined to be \$649,087,000,000, but it is not clear whether this number refers to annual sales, or monthly, or weekly sales.

@show 6.5e11/3e8               # ($/person-yr)
LB = 1; UB = 5                 # (trips/wk)
@show sqrt(LB*UB)
(6.5e11/3e8)/(sqrt(LB*UB)*52)  # ($/person-trip) => Likely annual sales

6.5e11 / 3.0e8 = 2166.6666666666665
sqrt(LB * UB) = 2.23606797749979

18.633899812498246

Why is the estimate so much less than the reported value?

@show no_customers = (6.5e11/27.3)/(sqrt(LB*UB)*52)
100*no_customers/3e8   # Customers as percent of total population

no_customers = (6.5e11 / 27.3) / (sqrt(LB * UB) * 52) = 2.04768129807673e8

68.25604326922434

Ex 4: House construction time
The table below shows the activities associated with the construction of a house. Listed for each activity are the activities that must immediately precede the start of the activity and the time required to complete the activity (in working days). Estimate how many days will be required to construct the house.

t = [2,4,10,4,6,7,5,7,8,9,4,5,2,6];
@show LB = maximum(t)
@show UB = sum(t)
sqrt(LB*UB)

LB = maximum(t) = 10
UB = sum(t) = 79

28.106938645110393

3. Installing Julia

The latest release of Julia (1.6.2) can be downloaded at https://julialang.org/downloads/ Julia is available for Windows, macOS, and Linux. Windows will be used for the demonstrations in class, but Mac and Linux should work with no complications for all of the assignments in class (see https://julialang.org/downloads/platform/ for detailed download instructions for each platform). Using the 64-bit (installer) for Windows, download and run the executable file julia-1.6.2-win64.exe and accept all of the defaults (note: if an earlier version of Julia in on your computer, first uninstall the earlier version).

After starting Julia using the desktop icon, the Julia window will open. Type ] at the command prompt to switch to package manager mode and then add IJulia (note: it can take quite a while to add and to load a package) and then build IJulia. When finished, use the Backspace key to return to the Julia command prompt. Type using IJulia, then jupyterlab(), and then y to install Jupyter via Conda (note: if you have Anaconda installed on your computer, Jupyter should already be installed and this step is not necessary). JupyterLab will launch in your default browser.

Using the File Browser on the left of the JupyterLab window, select/create a new folder where you can save the notebooks that will be used for this class (e.g., select Documents and then create and then select a new folder OR501). In the Lancher tab of the browser window, select the Julia 1.6.2 icon under Notebook and a new notebook named Untitled.ipynb will be created. At the prompt in the first cell, type "Hello world" and then Cntl+Enter to print it below in a new output cell. After saving your notebook, the easiest way to close and exit JupyterLab and Julia is to close each of their windows.

To open the notebook at a later time, start Julia and at the command prompt and type using IJulia, then jupyterlab(), and the notebook will open in your browser. To create a new notebook, under the File menu in JupyterLab, select New and then Notebook and then in the Select Kernel pop-up window select Julia 1.6.2.

"Hello world"

"Hello world"