Learning Outcomes

• Review summation notation

• Work on Sets, Parameters, Variables, and Model

• Write compact formulations for linear programs

The models of the previous chapters fit on an index card: two or three variables, a handful of constraints, every coefficient written out by hand. Now imagine your client is a grocery chain: 40,000 products, 200 stores, 52 weeks of demand. Nobody, however patient, writes out that objective function term by term. And when next year’s data arrive, nobody wants to retype the model. The notation of this chapter (sets, parameters, and summations) is how one page of mathematics describes a million-variable model, and how the same page describes it again next year when every number has changed.

Summation notation is a concise way to express the addition of a series of terms. It is commonly written as

where $i$ is the index of summation, $m$ is the starting index, and $n$ is the ending index.

1. Sum of $x_i$:

In vector terminology, if we let $x$ be an $n$-dimensional vector,

then ${\sum }_{i=1}^n{x}_i$ represents the sum of all components of $x$.

2. Sum of $a_i{x}_i$:

This expression is the dot product (or inner product) of two $n$-dimensional vectors $a$ and $x$, where

In vector notation, the dot product is written as:

This product yields a scalar value that combines the corresponding components of the two vectors.

When modeling with compact notation, sets help organize the problem and clearly indicate which indices appear in sums and constraints.

Example 4.1: Summing over a set

Let $I$ be the set of months in the year:

We can write a sum over all months in two equivalent ways:

Multiple Sets and Multiple Indices. Sometimes, variables are indexed over two or more sets. For example, let:

and suppose we have a variable $y_{ij}$ indexed by both $i\in I$ (months) and $j\in J$ (colors).

If, for each color $j$, the sum of $y_{ij}$ over all months must equal 1, we write:

This single compact expression actually represents three constraints—one for each color—where in each case, 12 monthly variables are summed to equal 1.

Important Rule: Every Index Must Be Defined. In any mathematical expression, every index must appear either:

1.

in a summation, or

2.

in a “for all” ($\forall$) quantifier.

In the above example, $y_{ij}$ uses both indices $i$ and $j$.

• The summation ${\sum }_{i\in I}$ defines $i$.

• The “for all” statement $\forall j\in J$ defines $j$.

Learning Checkpoint 4.0.1

Consider the incorrect formulation:

Write down what is missing from this statement to make it mathematically complete. Which index is undefined, and how should it be introduced?

Sets:

• $t\in \{1,2,\dots ,T\}$: Periods in the planning horizon.

Parameters:

• $c_t^{prod}$: Production cost per unit in period $t$ (for $t=1,\dots ,T$).

• $c^{inv}$: Inventory holding cost per unit carried from one period to the next.

• $d_t$: Demand in period $t$.

• $s_0$: Initial inventory available at the start of period 1.

Variables:

• $x_t$: Number of units produced in period $t$.

• $s_t$: Inventory level at the end of period $t$.

Model:

Example 4.2: Production Planning with 10 Periods ($T=10$)

Inventory Holding Cost:

Variables:

• $x_t$: Number of units produced in period $t$.

• $s_t$: Inventory level at the end of period $t$.

Model:

A manufacturing firm seeks to optimize its production schedule over a $T$-day planning horizon to meet daily demand while minimizing costs. The firm starts with an initial inventory of $s_0$ units. Production can be carried out during regular time and via overtime. The costs are as follows:

• Regular production cost: $c_t^{prod}$ dollars per unit on day $t$.

• Overtime production cost: $c_t^{over}$ dollars per unit on day $t$.

• Inventory cost: $c^{inv}$ dollars per unit carried over from one day to the next.

The goal is to determine the number of units to produce during regular time and overtime on each day, and the inventory levels, in order to minimize the total cost while satisfying daily demand.

Sets:

• Days of production $=\{1,2,\dots ,T\}$.

Parameters:

• $c_t^{prod}$: Regular production cost per unit on day $t$ (for $t=1,\dots ,T$).

• $c_t^{over}$: Overtime production cost per unit on day $t$ (for $t=1,\dots ,T$).

• $c^{inv}$: Inventory holding cost per unit carried to the next day.

• $d_t$: Demand on day $t$.

• $s_0$: Initial inventory at the start of day 1.

Variables:

• $x_t$: Number of units produced in regular time on day $t$.

• $y_t$: Number of units produced in overtime on day $t$.

• $s_t$: Inventory at the end of day $t$.

Model:

Example 4.3: Production Planning with Overtime ($T=10$)

The assignment problem is a fundamental optimization problem in combinatorial optimization. It involves assigning a set of $n$ agents (or workers) to $n$ tasks (or jobs) such that each agent is assigned exactly one task, and each task is assigned to exactly one agent. The goal is to minimize the total assignment cost.

• $I$ – Set of agents (or workers), indexed by $i$.

• $J$ – Set of tasks (or jobs), indexed by $j$.

Parameters:

• $c_{ij}$ – Cost associated with assigning agent $i\in I$ to task $j\in J$.

Variables:

• $x_{ij}$ – Binary decision variable, where:

  $$x_{ij}=\{\begin{array}{cc}1,\hfill & \text{if agent }i\text{ is assigned to task }j,\hfill \\ 0,\hfill & \text{otherwise}.\hfill \end{array}$$

Model:

Explanation:

Example 4.4: Machine Assignment

Example 4.5: School Bus Routing Problem

Sets:

• $i$ - Index for schools, $i\in I$

• $j$ - Index for buses, $j\in J$

Parameters:

• $c_{ij}$ - Fuel cost for bus $j$ to serve school $i$.

Variables:

• $x_{ij}$ - 1 if bus $j$ is assigned to school $i$, 0 otherwise.

Model:

Example 4.6: Hiring for tasks

Both teams prefer Project 2.

If we remove the binary restriction on the $x$-variable, the values can range between 0 and 1. For the original assignment problem, the optimal solution has $z=2$, and fractional $x$-values do not improve $z$.

For the min-max assignment problem, however, this is not the case. The optimal solution has $z=1.5$, occurring when each team is assigned half of each project (i.e., for Team 1, we have $x_{11}=0.5$ and $x_{21}=0.5$). By fractionalizing assignments, the worst-case project cost is minimized.

Case Study: Preference-Based Housing Assignment in Uruguayan Cooperatives

Housing cooperatives in Uruguay play a crucial role in providing affordable housing to their members. Traditionally, once a new cooperative building was completed, the assignment of individual housing units was conducted through a random draw. This method, while simple, ignored individual preferences such as sunlight orientation, floor level, and proximity to shared facilities. Recognizing the potential for improved member satisfaction, researchers developed an alternative assignment method based on mixed-integer programming (MIP).

In Uruguayan housing cooperatives, every member is entitled to a housing unit. Since the assignment process happens only once per building, it is crucial to ensure fairness while maximizing overall satisfaction. The existing lottery-based system failed to account for members’ preferences, sometimes leading to dissatisfaction and informal exchanges of units after the assignment. The challenge was to develop a new assignment process that:

• Ensured fairness among all members,

• Incorporated individual preferences,

• Was easy to explain and implement,

• Could be executed in real time during cooperative meetings.

A team of researchers proposed a two-stage mixed-integer programming (MIP) model to address these concerns. The assignment problem was formulated with the following structure:

Stage 1 – Ensuring Fairness: The model maximizes the satisfaction of the least satisfied member. This ensures that no one is assigned an extremely undesirable unit.

Stage 2 – Optimizing Global Satisfaction: Given the fairness constraints from Stage 1, the model then seeks to optimize the total satisfaction across all cooperative members.

The assignment process was implemented using a software tool called MTAV (Mejor Tecnología de Asignación de Viviendas – A Better Technology for Housing Assignment), designed to be transparent and user-friendly.

The first real-world test of the model occurred in 2016 with the Virazón housing cooperative, consisting of 50 members. Before deployment, the cooperative members reviewed and voted to approve the new method. Their individual housing preferences were collected and input into the system.

On the day of the assignment:

• The housing allocation was carried out in real-time during a cooperative meeting.

• The results were projected on a large screen for transparency.

• A notary was present to certify the fairness of the process.

• The optimization model took only a few seconds to compute the assignments.

The outcomes were striking:

• Four-bedroom apartments: Both members received their first-choice units.

• Three-bedroom apartments: More than 37% of members received their first-choice unit, and the average satisfaction ranking was significantly better than a random assignment.

• Two-bedroom apartments: Over half of the members received one of their top four choices, with all assignments being significantly better than expected under a random draw.

The cooperative members overwhelmingly supported the new system, reporting higher satisfaction compared to previous assignment methods.

Since the successful implementation at Virazón, over 30 housing cooperatives in Uruguay have adopted the model. Further developments have included:

• The introduction of a graphical user interface to make data input more intuitive.

• Support for partial order preferences, allowing members to indicate that they have no strong preference between certain units.

• Exploration of additional fairness criteria and trade-offs between individual and collective satisfaction.

Beyond its technical achievements, this case study highlights how operations research techniques can be applied to solve real-world social challenges. By integrating mathematical optimization with participatory decision-making, the project has significantly improved the way housing is assigned in cooperative communities, setting a precedent for future applications in housing policy and beyond.

The optimization model required the following input parameters and variables:

Sets:

• $I$: Set of cooperative members needing housing assignments.

• $J$: Set of available housing units.

Parameters:

• $p_{ij}$: Preference score of member $i$ for housing unit $j$, where lower values indicate higher preference (e.g., $1$ = most preferred).

• Some versions of the model supported partial order preferences, allowing members to express equal preference for multiple units.

Variables:

• $x_{ij}\in \{0,1\}$: Binary variable indicating whether member $i$ is assigned to unit $j$:

  $$x_{ij}=\{\begin{array}{cc}1,\hfill & \text{if member }i\text{ is assigned to unit }j\hfill \\ 0,\hfill & \text{otherwise}\hfill \end{array}$$

Stage 1: Ensuring Fairness

• Define $S$ as the satisfaction level of the least satisfied member:

  $$S=\underset{i\in I}{\max }\sum _{j\in J}{p}_{ij}{x}_{ij}$$

• Ensure each member is assigned exactly one unit and each unit is assigned to exactly one member.

This is achieved by the model

Stage 2: Optimizing Global Satisfaction

• Given the fairness threshold $S$ from Stage 1, optimize total satisfaction:

  $$\min \sum _{i\in I}\sum _{j\in J}{p}_{ij}{x}_{ij}$$

• Subject to the fairness constraint:

  $$\sum _{j\in J}{p}_{ij}{x}_{ij}\le S,\forall i\in I$$

• Ensures that no member receives a unit less desirable than the worst outcome allowed by Stage 1.

This is achieved by the model

• The model was formulated as a mixed-integer programming (MIP) model.

• The assignment was computed in real-time during cooperative meetings.

• The MTAV software was used to collect user preferences and compute assignments efficiently.

• The system ensured transparency, allowing cooperative members to verify their preferences before the final optimization.

When the constraints could be general, we will write $x\in X$ to define general constraints. For instance, we could have $X=\{x\in {ℝ}^n:Ax\le b\}$ or $X=\{x\in {ℝ}^n:Ax\le b,x\in {\mathbb{Z}}^n\}$ or many other possibilities.

Consider the problem

Example 4.7: Minimizing an Absolute Value

Network flow models are used to optimize the movement of commodities, resources, or information through a network while satisfying capacity and demand constraints. These models have a broad range of applications in various fields:

• Transportation and Logistics: Optimizing the movement of goods through a supply chain while minimizing transportation costs.

• Telecommunications: Managing data traffic flow in networks to minimize congestion and latency.

• Water and Energy Distribution: Balancing water flow in pipeline systems or optimizing power grid distribution to minimize energy loss.

• Project Scheduling: Allocating tasks to workers while minimizing delays and costs.

• Assignment and Matching Problems: Assigning resources to tasks, such as employees to projects or students to schools, in an optimal manner.

To begin a discussion on Network flow, we first need to discuss graphs.

Definition 4.8

A (undirected) graph $G=(V,E)$ is defined by a set of vertices $V$ and a set of edges $E$ that contains pairs of vertices.

For example, the following graph $G$ can be described by:

• the vertex set $V=\{1,2,3,4,5,6\}$ and

• the edge set $E=\{(4,6),(4,5),(5,1),(1,2),(2,5),(2,3),(3,4)\}$.

In an undirected graph, we do not distinguish the direction of the edge. That is, for two vertices $i,j\in V$, we can equivalently write $(i,j)$ or $(j,i)$ to represent the edge.

Definition 4.9

A directed graph (or di-graph for short) is denoted as $G=(V,A)$ where $V$ is a set of vertices and $A$ is a set of ordered pairs of vertices called arcs. That is, an arc is like an edge, but the direction of it matters.

For example, the following directed graph $G$ can be described by

• the vertex set $V=\{1,2,3,4,5,6\}$ and

• the arc set $A=\{(4,6),(6,4),(4,5),(5,1),(1,2),(2,5),(2,3),(3,4)\}$.

Example 4.10: Minimum-Cost Network Flow

Let $x_{ij}$ represent the amount of goods transported from warehouse $i$ to store $j$. The problem is formulated as:

Solution

Solving the linear program, we obtain the following optimal flow values:

Interpretation of the Solution

• Warehouse 1 sends 15 units to Store 1 and 5 units to Store 2.

• Warehouse 2 sends 10 units to Store 1 and 20 units to Store 2.

• The total transportation cost is minimized to 180.

This solution meets all constraints while ensuring goods are transported at the lowest possible cost.

Example 4.11: Amazonian’s Distribution Network

Amazonian must ship goods from large regional warehouses to local retail stores through intermediate distribution centers. Each warehouse has a certain supply capacity, each store has a demand, and each route incurs a transportation cost (fuel, time, and labor). Amazonian wants to decide how to route products to minimize cost, while ensuring demand is met and no transportation link exceeds its capacity.

The figure below shows a small example. There are:

• Two warehouses (W1, W2) with a total of 50 units of supply,

• Two distribution centers (D1, D2),

• Three stores (S1, S2, S3) that need 20, 15, and 15 units, respectively,

• Arc costs labeled in black,

• Node demands/supplies shown in blue next to each node.

The problem is to determine how many units to send along each route to minimize the total shipping cost.

Sets:

• $V$: set of nodes in the network (warehouses, distribution centers, stores)

• $A$: set of directed arcs $(i,j)$ representing shipment routes

Parameters:

• $c_{ij}$: cost per unit shipped on arc $(i,j)\in A$

• $u_{ij}$: maximum capacity of arc $(i,j)\in A$

• $d_i$: net supply at node $i\in V$ (positive = supply at the warehouses, negative = demand at the stores)

Variables:
$x_{ij}$: amount of flow shipped along arc $(i,j)\in A$

Model:

This problem can be solved using linear programming, and efficient specialized algorithms exist due to its structure. Applications span:

• Freight transportation,

• Supply chain optimization,

• Scheduling and telecommunications.

The minimum cost network flow problem is an extension of the network flow problem that considers not only the capacities of the arcs, but also the costs associated with sending flow along the arcs and the demands at the nodes. The objective is to find the flow of minimum cost that satisfies the demands at the nodes and the capacity constraints on the arcs.

A network can be described as a directed graph $G=(V,A)$, where $V$ is the set of nodes and $A$ is the set of arcs. Each arc $(i,j)\in A$ has a capacity $u_{ij}$ and a cost $c_{ij}$. Each node $i\in V$ has a demand $d_i$, which can be positive, negative, or zero. A positive demand means that the node requires that amount of flow, a negative demand means that the node supplies that amount of flow, and a zero demand means that the node neither requires nor supplies flow.

Consider, for example: The set of vertices is given by:

The set of directed arcs is:

The minimum cost network flow problem can be defined as follows: Given a network $G=(V,A)$, capacities $u_{ij}$ and costs $c_{ij}$ on the arcs, and demands $d_i$ at the nodes, find the flow $x_{ij}$ on the arcs that minimizes the total cost of the flow, while satisfying the demands at the nodes and the capacity constraints on the arcs.

Sets:

• $V$: Set of nodes in the network.

• $A$: Set of arcs in the network.

Parameters:

• $u_{ij}$: Capacity of arc $(i,j)\in A$.

• $c_{ij}$: Cost per unit of flow on arc $(i,j)\in A$.

• $d_i$: Net demand at node $i\in V$ (positive = demand, negative = supply).

Variables:

• $x_{ij}$: Flow on arc $(i,j)\in A$.

Model: The minimum cost network flow problem can be formulated as a linear programming problem as follows:

Objective: - The objective is to minimize the total cost of the flow.

Constraints: - Flow Conservation: The first set of constraints ensures that the flow into each node minus the flow out of the node is equal to the demand at the node.

- Capacity Constraints: The second set of constraints ensures that the flow on each arc does not exceed its capacity.

Minimum-cost network flow problems are widely used in transportation planning, supply chain logistics, and production scheduling, where the goal is to efficiently allocate resources at the lowest possible cost.

The maximum flow problem is a fundamental problem in operations research and computer science, with applications in a wide variety of fields. It involves finding the maximum amount of flow that can be sent from a source node to a sink node in a network, without exceeding the capacities of the individual arcs, and ensuring that the flow on each arc is non-negative. This problem arises in many real-world situations, such as in transportation, where it can be used to find the maximum amount of goods that can be transported from a factory to a warehouse, or in telecommunications, where it can be used to find the maximum amount of data that can be sent from one server to another. Other applications include supply chain optimization, water distribution, and electrical power grid optimization. In this section, we will describe a linear programming formulation for the network flow problem.

A network can be described as a directed graph $G=(V,A)$, where $V$ is the set of nodes and $A$ is the set of arcs. Each arc $(i,j)\in A$ has a capacity $u_{ij}$, which is the maximum amount of flow that can traverse the arc from node $i$ to node $j$.

The network flow problem can be defined as follows: Given a network $G=(V,A)$, a source node $s$, a sink node $t$, and capacities $u_{ij}$ on the arcs, find the maximum flow from $s$ to $t$ that respects the capacity constraints.

For example, consider the directed graph here with capacities on the arcs.

Example 4.12: Airline Transfer Network: Maximizing Passenger Throughput