Formal Definitions

<aside> 💡 For counterexamples, consider disconnected graphs.

</aside>

Multiperiod Model

• Multiple periods, resources carry over from previous period

Knapsack

• Maximize profit given costs

Scheduling

• Minimize supply given demand on each day

Worker Assignment

• Minimize cost of perfect matching
  • $x_e=1→e∈M$
  • min $\sum(c_ex_e:e∈E)$
  • $\sum (x_e : e ∈ δ(v)) = 1$ for all $v∈V$

Shortest Path

• If a set of edges $S\subseteq E$ intersects every st-cut, then it contains an st-path.
  • Converse is also true: Any valid st-path intersects every st-cut.
• Minimize cost of $s,t$-path

  • i.e. min $\sum(c_e:e∈S)$

    

Standard Equality Form (SEF)

An LP is in SEF if

1. It is a maximization problem
   • To convert min to max, just multiply the objective function by $-1$.
2. All variables are nonnegative (i.e. the constraint $x_j ≥0$ is given explicitly)
   • If we have $x_1 + x_2 ≤ 7$, then replace it with $x_1 + x_2 + s = 7; s≥0$
   • If we have $x_3+x_4≥8$, then replace it with $x_3 + x_4-t=8;t≥0$
3. All other constraints are equality constraints
   • We can write any number as the difference between two nonnegative numbers $a-b$
   • If we have a free variable $x_k$, add constraints $x_k = a-b; a,b≥0$

<aside> 💡 All constraints are in the form $x_i ≥ 0 \text{ and } g_j(x) = 0$.

</aside>

Width

Widths $y_U$ are numbers assigned to each s,t-cut set $U$

• Feasible if for every edge $e$, the sum of the widths of every s,t-cut that cut $e$ is $≤$ $c_e$

• Every s,t-path must have a length of at least the sum of all $y_U$

  • If length == sum of all widths, then it is a shortest path

• Random theorem: max # of independent columns = max # of independent rows

Simplex

Binary Variables

• Takes on a value of 0 or 1
• If we have $n$ events, and exactly 2 must occur, we can write
  • $e_1 + e_2 + \ldots + e_n = 2$

Graphs

• Vertices: $v_1, v_2, \ldots ∈ V$
• Edges: $v_1v_2, v_2v_3, \ldots ∈ E$ are bidirectional
• Graph: $G :=(V,E)$

Matching

• Collection of edges $M\subseteq E$ that do not share ANY endpoint
• Perfect: Matching contains all vertices in the graph
  • $|M∩δ(v)| = 1$ for all $v∈V$
  • For bipartite graphs, can be thought of as a one-to-one relationship

Cuts and Paths

• $δ(v)$ is the set of all edges with a vertex $v$ as an endpoint.
• $δ(S)$ is the set of edges with exactly one vertex in a set of vertices $S$
• $s,t$-cut: Set of edges that when removed, causes $s$ and $t$ to become disconnected
  • If $s∈S$ and $t\not∈S$, then $S$ is an st-cut
• $s,t$-path: Sequence of unique edges starting at s and ending at t
  • Called a walk if edges are not unique
  • Length is given by sum of edge costs $c_e$
  • Must contain an edge from some $s,t$-cut $δ(S)$ (since you have to take out at least one edge from a path to disconnect it)

Optimality

• For some solution $\overline{x}$, prove that it is feasible and an upper (max) or lower (min) bound

Infeasibility

• $\max\left\{c^Tx:Ax=b,x≥0\right\}$
• Farkas’ Lemma: If the constraints do not hold i.e. no such $x$ where $Ax=b$, then
  • There exists $y$ where $y^TA≥\mathbb{0}$ and $y^Tb<0$

Unboundedness

• $\max\left\{c^Tx:Ax=b,x≥0\right\}$
• Unbounded if there exists $\overline{x}, r$ such that
  • $\overline{x}≥0,r≥0, A\overline{x}=b,Ar=0, c^Tr>0$

Basis

Given some 3 by 5 matrix $A$

• If a basis is chosen by selecting columns $B=\{1, 2, 4\}$
  • $A_B$ is the matrix formed by the 1st, 2nd, and 4th columns
  • $x_B = (x_1, x_2, x_4)^T$ is the unique basic solution for $B$
    • But different bases $B$ can have the same basic solution
  • $x_3 = x_5 = 0$ are non-basic variables ↓
• $x_j$ is a basic variable if $j∈B$, and $x_j = 0$ if $j\not∈B$
  • And it is feasible if it is non-negative $x ≥ 0$
• In general, $B$, a set of column indices, is a basis if
  1. $A_B$ is square
  2. Its columns are linearly independent

Canonical Form

The linear program $\max \left\{c^Tx \colon Ax=b,x≥0 \right\}$ is in canonical form if

1. $A_B = I$
2. $c_j=0$ for all $j∈B$