Learning Outcomes

• Consider an introductory problem

• Identify reasons for studying operations research

• Define “Mathematical Programming”

• Learn about different applications of the tools in this book

• Explore the different types of optimization models and what types we will see in this book

Imagine you’re starting a new clothing company and decide to sell shirts. You’ve opened a store in Roanoke and, based on market research, you estimate the demand for the upcoming weekend:

• Friday: 5 shirts

• Saturday: 10 shirts

• Sunday: 7 shirts

Defining the Problem

To tackle this challenge, you’ll need to think strategically about two main factors:

• Ordering Quantities: How many shirts to order on each day.

• Inventory Levels: How many shirts to keep in stock at the end of each day.

You can define these decisions using variables:

• Let the number of shirts you order on a specific day be a decision variable. For example, you could track the number of shirts ordered on Thursday, Friday, and Saturday.

• Define variables to represent the number of shirts you have in stock at the end of each day.

Your goal is to meet the projected demand while managing costs. Costs could include:

• The expense of ordering shirts.

• The cost of holding inventory.

• Penalties for running out of stock.

Refining the Scenario

As your business grows, additional complexities may arise. For instance:

• The cost of ordering shirts might vary by day due to supplier pricing.

• Holding inventory could incur storage costs.

• A budget might limit how much you can spend on orders.

• You might expand your product line to include pants and socks, each with its own demand and costs.

By clearly defining variables and constraints for these decisions, you can systematically approach the problem and develop an optimal strategy. This step-by-step process of defining the problem, incorporating real-world details, and refining the solution is a fundamental aspect of optimization.

This multi-stage example illustrates the iterative cycle of modeling:

1.

Initial Problem: Determine ordering quantities to meet demand.

2.

Modeling: Formulate an optimization model based on available information.

3.

Solution: Solve the model to find the optimal ordering plan.

4.

New Information: Incorporate additional real-world complexities (varying costs, inventory costs, budget constraints, additional products, fixed ordering costs).

5.

Refinement: Update the model to reflect new information and solve again.

Looking ahead, there are several ways to expand this scenario:

• Expanding to New Stores: Opening additional stores introduces location-based demand, transportation costs, and coordination of inventory across multiple sites.

• Hiring New Staff: Incorporate labor costs, scheduling constraints, and productivity rates into the model.

• Producing Clothing In-House: Transitioning to manufacturing involves modeling production processes, including purchasing raw materials, machine capacities, and processing times.

• Uncertain Demand: In reality, demand may be uncertain. Advanced models can incorporate stochastic elements or use probabilistic methods to handle randomness.

In this book, we will focus on deterministic models where all data is known and fixed. Building a strong foundation with these models will prepare us to tackle more complex problems involving uncertainty and randomness in future studies.

You already interact with optimization many times a day without noticing. The route your phone suggests, the price of your plane ticket, the fact that the store had what you wanted in stock, the schedule of your favorite sports league, and which kidney patients get matched with which donors: behind each one is an optimization model of the kind this book teaches. Even the AI assistants making headlines are trained by optimization; fitting a large language model is a nonlinear programming problem with billions of variables.

Operations Research (OR) is, in the words of the professional society INFORMS, a discipline that applies advanced analytical methods to help make better decisions. In a world where resources are limited and organizations face complex challenges, OR provides the tools and methodologies to model, analyze, and solve problems involving the optimal allocation of scarce resources. Studying OR equips individuals with a systematic and quantitative approach to decision-making, which is invaluable in industries such as logistics, finance, healthcare, and manufacturing.

By understanding OR, you gain the ability to construct mathematical models of real-world systems, allowing for the simulation and optimization of different scenarios. This leads to improved efficiency, reduced costs, and enhanced performance. The skills developed through studying OR, such as critical thinking, problem-solving, and data analysis, are highly transferable and sought after in today’s data-driven economy.

Operations Research also bridges the gap between theory and practice. It transforms abstract mathematical concepts into actionable strategies that can have a tangible impact on organizational success. Whether it’s optimizing supply chains, scheduling flights, or managing portfolios, the applications of OR are vast.

These are not hypothetical savings. A few documented examples:

• Finalist projects for the INFORMS Franz Edelman Award, the field’s top prize for applied work, have documented cumulative benefits exceeding $446 billion since 1972 [?].

• UPS’s ORION system optimizes delivery routes for tens of thousands of drivers; it cuts roughly 100 million miles of driving per year, worth $300–400 million annually, and about 100,000 metric tons of CO${}_2$ [?].

• American Airlines’ yield-management system, an early large-scale optimization success, generated an estimated $1.4 billion over three years in the early 1990s [?].

• Netherlands Railways rebuilt its national timetable with optimization, with a projected additional annual profit of about 40 million euros, and won the 2008 Edelman Award for it [?].

Every one of these is, at its mathematical center, the kind of model you will learn to build in this book.

Mathematical Programming is a core area within Operations Research that focuses on the formulation and solution of optimization problems. It involves creating mathematical models that represent the decision-making process of a system, where the goal is to find the best possible outcome under given constraints. The term “programming” in this context refers to planning or scheduling, not computer programming.

At the heart of Mathematical Programming is the objective function: a mathematical expression that defines the criterion to be optimized, such as minimizing costs or maximizing profits. The decision variables represent the choices available, and the constraints reflect the limitations or requirements of the problem, such as resource capacities or regulatory conditions.

There are various types of mathematical programming, each suited to different kinds of problems:

• Linear Programming (LP): Deals with problems where both the objective function and constraints are linear.

• Integer Programming (IP): Involves decision variables that must take on integer values.

• Nonlinear Programming (NLP): Handles problems with nonlinear objective functions or constraints.

• Dynamic Programming (DP): Breaks down problems into simpler subproblems and is particularly useful for multistage decision processes.

Mathematical Programming provides a powerful framework for optimizing complex systems and making informed decisions. It combines elements of mathematics, economics, and computer science to develop solutions that are both efficient and effective.

Operations Research and Mathematical Programming have a wide range of applications across various industries and sectors:

• Transportation and Logistics: Optimizing routing and scheduling for delivery vehicles, reducing transportation costs, and improving supply chain efficiency.

• Manufacturing: Streamlining production processes, managing inventory levels, and scheduling machinery to maximize productivity and minimize waste.

• Finance: Portfolio optimization, risk assessment, and capital budgeting to enhance financial performance and manage uncertainties.

• Healthcare: Allocating resources such as staff and equipment, scheduling surgeries, and managing patient flow to improve service quality and reduce wait times.

• Energy Sector: Optimizing power generation and distribution, planning for renewable energy integration, and managing energy consumption.

• Telecommunications: Network design and optimization, bandwidth allocation, and improving the reliability and efficiency of communication systems.

• Agriculture: Planning crop rotations, optimizing the use of fertilizers and water, and managing supply chains for agricultural products.

• Public Sector: Urban planning, emergency response logistics, and policy analysis to enhance public services and resource utilization.

• Artificial Intelligence: Training machine learning models, including the large language models behind ChatGPT and Claude, by minimizing loss functions with nonlinear programming techniques.

We will state the main general problem classes to be associated with in these notes. These are Linear Programming (LP), Mixed-Integer Linear Programming (MILP), Non-Linear Programming (NLP), and Mixed-Integer Non-Linear Programming (MINLP).

Along with each problem class, we will associate a complexity class for the general version of the problem. Complexity classes are discussed in a later portion of the book. Although we will often state that input data for a problem comes from $ℝ$ (as a real number), when we discuss complexity of such a problem, we actually mean that the data is rational, i.e., from $\mathbb{Q}$ (rational numbers that are encoded in the computer typically), and is given in binary encoding.

Warning

In the following subsections, we will use advanced notation that may be unfamiliar at this point. These mathematical notations will be developed throughout the book.

Also, don’t be too concerned about the specific definitions of the complexity classes at this point. For now, you can read that Polynomial time (P) means it should be relatively easy to solve, while the other classes might be much more difficult to solve.

Some linear programming background, theory, and examples will be provided in Part I of this book.

Linear Programming (LP)

Polynomial time (P)

Given a matrix $A\in {ℝ}^{m\times n}$, vector $b\in {ℝ}^m$ and vector $c\in {ℝ}^n$, the linear programming problem is

Linear programming can come in several forms, whether we are maximizing or minimizing, or if the constraints are $\le ,=$ or $\ge$. One form commonly used is Standard Form given as

Linear Programming (LP) Standard Form

Polynomial time (P)

Given a matrix $A\in {ℝ}^{m\times n}$, vector $b\in {ℝ}^m$ and vector $c\in {ℝ}^n$, the linear programming problem in standard form is

Integer Linear Programming (ILP)

NP-complete

Given a matrix $A\in {ℝ}^{m\times n}$, vector $b\in {ℝ}^m$ and vector $c\in {ℝ}^n$, the integer linear programming problem is

An even more general class is Mixed-Integer Linear Programming (MILP). This is where we have $n$ integer variables $x_1,\dots ,x_n\in \mathbb{Z}$ and $d$ continuous variables $x_{n+1},\dots ,x_{n+d}\in ℝ$. Succinctly, we can write this as $x\in {\mathbb{Z}}^n\times {ℝ}^d$, where $\times$ stands for the cross-product between two spaces.

Below, the matrix $A$ now has $n+d$ columns, that is, $A\in {ℝ}^{m\times (n+d)}$. Also note that we have not explicitly enforced non-negativity on the variables. If there are non-negativity restrictions, this can be assumed to be a part of the inequality description $Ax\le b$.

Mixed-Integer Linear Programming (MILP)

NP-complete

Given a matrix $A\in {ℝ}^{m\times (n+d)}$, vector $b\in {ℝ}^m$ and vector $c\in {ℝ}^{n+d}$, the mixed-integer linear programming problem is

NLP

NP-hard

Given a function $f(x):{ℝ}^d\to ℝ$ and other functions $f_i(x):{ℝ}^d\to ℝ$ for $i=1,\dots ,m$, the nonlinear programming problem is

Nonlinear programming can be separated into convex programming and non-convex programming. These two are very different beasts and it is important to distinguish between the two.

Here the functions are all convex!

Convex Programming

Polynomial time (P)  (typically)

Given a convex function $f(x):{ℝ}^d\to ℝ$ and convex functions $f_i(x):{ℝ}^d\to ℝ$ for $i=1,\dots ,m$, the convex programming problem is

Observe that convex programming is a generalization of linear programming. This can be seen by letting $f(x)=c^{\top }x$ and $f_i(x)=A_{i}x-b_i$.

When the function $f$ or functions $f_i$ are non-convex, this becomes a non-convex nonlinear programming problem. There are a few complexity issues with this.

has exactly two solutions: $x=0,x=1$. Thus, quadratic constraints can be used to model binary constraints.

Binary Integer programming (BIP) as a NLP

NP-hard

Given a matrix $A\in {ℝ}^{m\times n}$, vector $b\in {ℝ}^m$ and vector $c\in {ℝ}^n$, the binary integer programming problem is

Alternatively, consider the transformation where $x_i\in \{-1,1\}$.

This can be reformulated with a single nonconvex constraint as

Machine learning is, at its mathematical center, learning functions from data. Instead of a person writing down the rule, we choose a family of functions $f(x;𝜃)$ with tunable parameters $𝜃$ and let an optimization algorithm pick the parameters that fit the data best. The learned function might categorize data (is this email spam? does this scan show a tumor?), predict a number (tomorrow’s demand, a house price), or group similar things together without labels (customer segments, related news articles).

This is why machine learning belongs in an optimization book: training a model is solving an optimization problem, usually a continuous and often nonconvex one. The same recipe runs everywhere:

• Spam filtering and fraud detection: classify a message or transaction as legitimate or not.

• Demand forecasting: predict next month’s sales from history, weather, and promotions.

• Image recognition: label the content of a photo, from unlocking your phone to reading medical scans.

• Recommendations: predict which movie, song, or product a user will like next.

• Large language models: systems like ChatGPT and Claude are trained by minimizing a loss function over billions of parameters, using nonlinear programming techniques (variants of gradient descent) run at enormous scale. The mathematics of training the most talked-about technology of the decade is the mathematics of this book’s nonlinear programming chapters.

Below are the two most common mathematical shapes these problems take. We will see both in greater detail later in the book.

In supervised learning, this objective is typically a loss function $L$ that quantifies the discrepancy between the predictions of a model and the true data labels. The aim is to adjust the parameters $𝜃$ of the model to minimize this loss. Mathematically, this can be represented as:

where $N$ is the number of data points, $l$ is a per-data-point loss (e.g., squared error for regression or cross-entropy for classification), $y_i$ is the true label for the i-th data point, and $f(x_i;𝜃)$ is the model’s prediction for the i-th data point with parameters $𝜃$.

Clustering, on the other hand, learns structure with no labels at all: group the data so that points in the same group are similar and points in different groups are not. A retailer might cluster customers into segments for targeted offers; a biologist might cluster genes by expression pattern. One popular method is the k-means clustering algorithm. The objective of k-means is to partition the data into $k$ clusters by minimizing the within-cluster sum of squares (WCSS). The mathematical formulation can be given as:

where $C_j$ represents the j-th cluster and $c_j$ is the centroid of that cluster.

This encapsulation presents a glimpse into how ML problems are framed mathematically. In practice, numerous algorithms, constraints, and regularizations add complexity to these basic formulations.

MINLP

NP-hard

Mixed Integer Nonlinear Programming (MINLP) combines elements of integer programming and nonlinear programming. In MINLP, some or all of the decision variables are constrained to be integers, and the objective function or constraints are nonlinear. A general MINLP problem can be formulated as:

where $f$ is the objective function, $g_i$ and $h_j$ are constraint functions, $x$ is a vector of continuous variables, and $y$ is a vector of integer variables.

MINLP is particularly challenging due to the nonlinearity in the objective and/or constraints and the discrete nature of some decision variables. It finds applications in various fields such as industry for process optimization, computational geometry, and machine learning for hyperparameter tuning.

In the convex case, both the objective function and the constraints are convex functions. This subclass is easier to solve compared to its non-convex counterpart.

Convex MINLP

NP-hard, but Polynomial time (P) in fixed dimension (typically)

For a convex MINLP, the problem is defined as:

Convex MINLPs, while still challenging, are typically more tractable due to the properties of convexity, which allow for more efficient solution methods.

Non-convex MINLPs are significantly harder due to the presence of non-convex functions, which can lead to multiple local minima.

Non-Convex MINLP

NP-hard(in fact, undecidable)

The non-convex MINLP problem is formulated as:

Non-convex MINLPs pose significant computational challenges due to the possibility of multiple local optima and the inherent complexity of integer constraints. These problems are common in real-world applications where decisions are discrete, and the system behavior is non-linear and complex.

MINLP problems are known for their computational complexity, primarily due to the combination of non-linearity and integrality. The non-convex variants, in particular, are NP-hard, making them some of the most challenging problems in optimization.

In practice, MINLP models find extensive applications across various domains. In industry, they are used for complex decision-making processes like supply chain optimization and production planning. In computational geometry, MINLP techniques help in solving problems like optimal packing or layout design. In machine learning, MINLPs are used for tasks like feature selection and hyperparameter optimization where discrete choices and nonlinear relationships are involved.

The versatility of MINLP models, combined with their inherent complexity, makes them an important area of study in optimization.

Optimization problems often involve uncertainty in their parameters, whether due to measurement errors, variability in input data, or unpredictable future events. Addressing uncertainty is crucial for developing solutions that are effective in real-world settings. Two primary approaches to optimization under uncertainty are stochastic optimization and robust optimization.

Stochastic optimization deals with problems where some parameters are uncertain but can be described probabilistically. In this framework, the optimization process incorporates the expected values, variances, or other statistical characteristics of uncertain parameters. Solutions are often evaluated based on their performance over a distribution of possible scenarios.

For example, in supply chain management, uncertain demand can be modeled using probability distributions. A company may aim to minimize costs while ensuring a high service level under varying demand conditions. Similarly, in finance, portfolio optimization often accounts for uncertain future returns by maximizing expected returns while managing risk.

Robust optimization, on the other hand, focuses on creating solutions that perform well across the worst-case realizations of uncertainty. Rather than assuming a specific probability distribution, robust optimization works with uncertainty sets, which define the range of possible values that uncertain parameters can take. The goal is to find solutions that are feasible and effective for all possible scenarios within the uncertainty set.

Applications of robust optimization include power grid operations, where uncertainties in demand and renewable energy generation need to be managed, and scheduling problems, such as airline crew scheduling, where disruptions must be minimized under varying operational conditions.

Optimization under uncertainty has a wide array of applications across industries:

• Healthcare: Designing vaccination strategies to minimize the spread of diseases while accounting for uncertain infection rates and patient behaviors.

• Transportation: Managing traffic flow or public transit schedules under uncertain demand and travel times.

• Energy: Planning renewable energy investments and operations under uncertain weather conditions and energy prices.

• Manufacturing: Ensuring production schedules are resilient to supply chain disruptions and variability in raw material quality.

Addressing the complexity of uncertain data typically makes these problems much harder than their deterministic counterparts. While these methods are powerful and applicable to a wide range of real-world scenarios, we will not focus on optimization under uncertainty in this textbook.

Exercise 1.1: Classify It: Production Plan

$\star$  A juice company decides how many liters of apple juice $x_1$ and orange juice $x_2$ to produce. Each liter of apple juice earns $2 and each liter of orange juice earns $3. Pressing capacity gives $x_1+2x_2\le 800$, bottling capacity gives $x_1+x_2\le 600$, and both quantities are non-negative. The company maximizes earnings. Classify this model as LP, ILP/BIP, MILP, NLP, or MINLP. Point to the two features of the model (type of functions, type of variables) that justify your answer.

Exercise 1.2: Classify It: Choosing Projects

$\star$  A city can fund any subset of five park projects. Project $i$ costs $a_i$ dollars and benefits $c_i$ residents, and the budget is $b$ dollars. Let $x_i=1$ if project $i$ is funded and $x_i=0$ otherwise, and consider

Classify this model as LP, ILP/BIP, MILP, NLP, or MINLP, and justify your answer. What changes about the classification if the city can also fund a fraction of a project?

Exercise 1.3: Classify It: Fitting a Line

$\star$  Given data points $(t_1,y_1),\dots ,(t_N,y_N)$, we choose slope $m$ and intercept $q$ to minimize

with $m,q\in ℝ$ unrestricted. Classify this model as LP, ILP/BIP, MILP, NLP, or MINLP, and justify your answer. Is the objective function linear in the decision variables $m$ and $q$?

Exercise 1.4: Classify It: Warehouses with Congestion

$\star$  A retailer decides which of $k$ candidate warehouses to open ($y_j\in \{0,1\}$) and how much product $x_j\ge 0$ to route through each open warehouse. Handling cost at warehouse $j$ grows quadratically with volume, so the objective includes terms $x_j^2$, and product can flow through warehouse $j$ only if $y_j=1$. Classify this model as LP, ILP/BIP, MILP, NLP, or MINLP, and justify your answer by naming which ingredient rules out each simpler class.

Exercise 1.5: Shirt Store: Variables and One Constraint

Exercise 1.6: Spot the Pieces: Food Truck

$\star \star$  A food truck owner must decide how many tacos and how many burritos to prepare tomorrow. Each taco uses 0.1 kg of meat and each burrito uses 0.25 kg, and only 30 kg of meat will be available. Prep labor is limited to 10 hours. Tacos earn $2 profit and burritos $3.50. Without writing the full model, identify in words: the decision variables, the objective function, and each constraint. State the units of every quantity you name.

Exercise 1.7: Spot the Pieces: Tutoring Center

Exercise 1.8: Half a Bus

$\star \star$  A school district’s model says the optimal fleet is 12.5 buses. A shirt store’s model says the optimal order is 2361.4 shirts.

1.

In which of the two cases is rounding the LP answer to a nearby integer likely acceptable, and why?

2.

Explain what the divisibility issue means for choosing between the LP and MILP problem classes, and what price we pay (in computational difficulty) for insisting on integer variables.

Exercise 1.9: Why “Programming”?

$\star \star$  The word “programming” in mathematical programming predates modern software. Explain in one or two sentences what the term refers to in this subject, and why “linear programming” does not mean writing computer code in a linear fashion.

Exercise 1.10: Reading a Success Story

Exercise 1.11: Shirt Store: The Full Model

Solution