Start with feasible solution

• Repeat Until no improvement can be found:
  • Change to a feasible solution with a better value of the objective function.

Linear Programming

Problem to optimize a linear function of several variables subject to linear constraints.

General Form: Maximize c_1 x_1 + c_2 x_2 + \dots + c_n x_n Subject to:

\begin{aligned} a_{11} x_1 + \dots + a_{1n} x_n &\le b_1 \\ &\dots \\ a_{m1} x_1 + \dots + a_{mn} x_n &\le b_m \\ x_1 \ge 0, \dots, x_n &\ge 0 \end{aligned}

Example:

Maximize 3x+5y

subject to:

\begin{aligned} x+y &\le 4 \\ x+3y &\le 6 \\ x \ge 0, y &\ge 0 \end{aligned}

We can draw a figure in 2D space and find the feasible region bounded by the intersection of these lines.

Extreme Point Theorem:

Any LP problem with a nonempty, bounded feasible region has an optimal solution.

Solving LP

Three outcomes:

1. Has a finite optimal solution
2. Unbounded
3. Infeasible

Simplex

Classic LP problem solver.

Standard Form of LP Problem

Works on maximization problems. All constraints (except the nonnegativity constraints) must be linear equations.

All variables must be nonnegative

Basic Feasible Solutions

A basic solution¹1. In geometric terms, these basic feasible solutions correspond directly to the extreme points (corners) of the feasible region. to a system of m linear equations in n unknowns is obtained by setting n-m variables to 0 and solving the resulting system to get the values of the other m variables.

\begin{aligned} x+y+u &= 4 \\ x+3y+v &= 6 \end{aligned}

(0,0,4,6) is a basic feasible solution.

Simplex Tableau

The Simplex algorithm represents the system of equations as a tableau²2. a matrix.. The bottom row represents the objective function. The algorithm repeatedly selects a pivot column (a variable to enter the basis) with a negative coefficient in the bottom row, and a pivot row (the variable to leave the basis) with the smallest positive ratio of the right-hand side to the pivot column element. It then performs row operations to make the pivot element 1 and all other elements in the pivot column 0. This repeats until no negative values remain in the bottom row.

Analysis — The Simplex algorithm has an exponential worst-case time complexity, but in practice, it is highly efficient and typically runs in polynomial time. Space complexity is O(mn).

Maximum Flow Problem

Problem of maximizing the flow of a material through a transportation network.

Formally, this is represented with a connected, weighted digraph with n verticies numbered 1 to n.

• Vertex 1: Source
  • has no enterting edges
• Vertex n: Sink
  • Has no leaving edges
• Each edge has a weight called the edge capacity, the upper bound of material that can flow through the edge.

Note — There can only be one source, and one sink.

Definition of Flow

Assignemnt of real number x_{ij} to edges (i,j) of a given network that satisfy the following:

1. Flow-Conservation Requirements: Total amount of material entering an intermediate vertex must equal the toal amount of material leaving it.

\sum_j x_{ji} = \sum_k x_{ik} \quad \text{for all } i \ne 1, n

2. Capacity Constraints:

0 \le x_{ij} \le u_{ij} \quad \text{for every edge } (i,j)

No material can be lost or added by going through intermediate verticies, so total amount of material leaving the source must end up at the sink.

This means our objective function is \sum_j x_{1j}, which we want to maximize

As a LP Problem

Maximize \sum_j x_{1j}

subject to

Flow conservation and capacity constraints as defined above.

Ford-Fulkerson

A solution to flow maximization.

Steps:

1. Start with zero flow on all edges.
2. On each iteration, try to find a flow-augmenting path from source to sink, which is a path along which we can push more flow without violating capacities.
3. If flow-augmenting path is found, adjust the flow along the edges by the bottleneck capacity (the minimum residual capacity along the path).
4. Repeat until no augmenting path can be found.

ALGORITHM FordFulkerson(G, s, t)
    // Computes the maximum flow in a flow network
    // Input: Network G with capacities c, source s, sink t
    // Output: Maximum flow
    for each edge (u, v) in E do
        flow[u, v] \leftarrow 0; flow[v, u] \leftarrow 0
    while there exists a path p from s to t in the residual network do
        cf(p) \leftarrow min(capacity_f(u, v) for (u, v) in p)
        for each edge (u, v) in p do
            flow[u, v] \leftarrow flow[u, v] \text{$+$} cf(p)
            flow[v, u] \leftarrow -flow[u, v]
    return sum(flow[s, v] for v adjacent to s)

Analysis — Time complexity is O(|E| \times \text{max\_flow}). This can be inefficient if the max flow is large and capacities are irrational. Space complexity is O(|V| + |E|).

Shortest-Augmenting-Path Algorithm

An improvement on Ford-Fulkerson (often called Edmonds-Karp). It simply chooses the augmenting path with the fewest number of edges using Breadth-First Search (BFS).

ALGORITHM ShortestAugmentingPath(G, s, t)
    // Computes max flow using shortest augmenting paths
    // Input: Network G with capacities c, source s, sink t
    // Output: Maximum flow
    Initialize flow to 0
    while BFS finds a path p from s to t in residual network do
        augment flow along p by the bottleneck capacity
    return flow

Analysis — By using BFS, the time complexity is bounded by O(|V||E|^2), making it strongly polynomial and independent of edge capacities.

Gale-Shapley Algorithm

A solution to the Stable Marriage Problem. It ensures a stable matching between two equally sized sets of elements given their preferences.

Steps:

1. Initially, all men and women are free.
2. While there is a free man who still has a woman to propose to, he proposes to the highest-ranked woman on his list who he hasn’t proposed to yet.
3. If the woman is free, they become engaged.
4. If she is already engaged but prefers this man over her current partner, she accepts, and the old partner becomes free.
5. If she prefers her current partner, she rejects the new proposal.

ALGORITHM GaleShapley(Preferences)
    // Finds stable matching for n men and n women
    // Input: Preference lists for all men and women
    // Output: Stable matching
    Initialize all m in M and w in W to free
    while there is a free man m who has not proposed to every woman do
        w \leftarrow highest-ranked woman on m's list to whom m has not proposed
        if w is free
            (m, w) become engaged
        else if w prefers m to her current fiancé m'
            (m, w) become engaged
            m' becomes free
        else
            w rejects m
    return set of engaged pairs

Analysis — The algorithm terminates after at most n^2 iterations. The time complexity is O(n^2) with efficient data structures. Space complexity is O(n^2) to store the preference lists.