O&C Test 1

A linear programming problem consits in finding $\max\{\vec{c} \cdot \vec{x} \mid A \vec{x} \leq \vec{b}, \vec{x}\in \mathbb{R}_{+}^n\}$ where $\vec{c} \in \mathbb{R}^n, \vec{b} \in \mathbb{R}^m, A \in \mathbb{R}^{n \times m}$

An integer programming problem consits in finding $\max\{\vec{c} \cdot \vec{x} \mid A \vec{x} \leq \vec{b}, \vec{x}\in \mathbb{Z}_{+}^n\}$ where $\vec{c} \in \mathbb{R}^n, \vec{b} \in \mathbb{R}^m, A \in \mathbb{R}^{n \times m}$

A boolean programming problem consits in finding $\max\{\vec{c} \cdot \vec{x} \mid A \vec{x} \leq \vec{b}, \vec{x}\in \mathbb{B}_{+}^n\}$ where $\vec{c} \in \mathbb{R}^n, \vec{b} \in \mathbb{R}^m, A \in \mathbb{R}^{n \times m}$

$\max\{\vec{c} \cdot \vec{x} \mid A \vec{x} \leq \vec{b}, \vec{x}\in \mathbb{R}_{+}^n\}$ where $\vec{c} \in \mathbb{R}^n, \vec{b} \in \mathbb{R}^m, A \in \mathbb{R}^{m \times n}$

$S = \{\vec{x} \mid A\vec{x} \leq \vec{b}, \vec{x} \in \mathbb{R}^n\}$

Let $M = \{1,2,...,m\}$ and $N=\{1,...,n\}$. For each $j\in N$ in $M$ we consider a subset $M_j \subseteq M$. Let $F \subseteq N$ (F is an index subset).

F is called a convering of $M$ if $\bigcup_{j \in F} M_j = M$

F is called a packing of $M$ if $M_j^1 \bigcap M_j^2 = \empty \quad \forall j_1 \neq j_2 \in F$

F is called a partition of $M$ is $F$ is both a convering and packing.

$(P): Z_{LP} =\max\{\vec{c} \cdot \vec{x} \mid A \vec{x} \leq \vec{b}, \vec{x}\in \mathbb{R}_{+}^n\}$

$(D): W_{LP} =\min\{\vec{y} \cdot \vec{b} \mid \vec{y}^T A \geq \vec{c}^T, \vec{y}\in \mathbb{R}_{+}^m\}$

Let $A\in \mathbb{R}^{m \times n}, \vec{b} \in \mathbb{R}^m, \vec{c} \in \mathbb{R}^n$ and $(P): Z_{LP} =\max\{\vec{c} \cdot \vec{x} \mid A \vec{x} \leq \vec{b}, \vec{x}\in \mathbb{R}_{+}^n\}$ , $(D): W_{LP} =\min\{\vec{y} \cdot \vec{b} \mid \vec{y}^T A \geq \vec{c}^T, \vec{y}\in \mathbb{R}_{+}^m\}$ its dual.

If $\vec{x}$ is primal feasible and $\vec{y}$ is dual feasible then $\vec{c}\cdot \vec{x}\leq Z_{LP} \leq W_{LP} \leq \vec{y}\cdot \vec{b}$.

Let $S \subseteq \mathbb{R}^n$. S is called convex if for all elements $\vec{x}, \vec{y} \in S$ we have $[\vec{x}, \vec{y}] \subseteq S$ where $[\vec{x}, \vec{y}]=\{(1-t)\vec{x} + t\vec{y} \mid 0\leq t \leq 1\}$ (segment determined by $\vec{x}$ and $\vec{y}$).

$\vec{Z}(t) = (1-t)\vec{x} + t\vec{x}$. $\vec{Z}(t)$ is a convex combination of $\vec{x}$ and $\vec{y}$.

If $\vec{Z}(t) = (1-t)\vec{x}+t\vec{y}$ with $0\leq t\leq 1$, then $\vec{Z}$ is called strict-convex combination.

A subset $S \subseteq \mathbb{R}^n$ is called bounded if $S \subseteq \mathbb{B}_{\vec{0}, r}$ for some $r$. By the previous statement we have if $S \subseteq \mathbb{B}_{\vec{x}, r}$ then $S$ is bounded.

A subset $S \in \mathbb{R}^n$ is called closed if whenever a sequence of points $\{\vec{s}_i\}_{i\geq 1}$ in $S$ converges, the limit of the sequence is also in $S$.

Let $S \subseteq \mathbb{R}^n$. A point $\vec{s} \in S$ is called an interior point if there exists $\epsilon > 0$ such that $\mathbf{B}_{\vec{s}, \epsilon} \subseteq S$

$\mathring{S}$ is the set of all interior points of $S$

Let $S \subseteq \mathbb{R}^n$. The boundary of $S$, denoted $\partial S$ is the set of all points in $S$ that not inteior to $S$ and not interior to the complement of $S$ denoted $S^c$.

$\partial S = (S \backslash \mathring{S})\cup(S^c \backslash \mathring{S^c})$

A polyhedron in $\mathbb{R}^{n}$ is a finite intersection of half-spaces

Every Polyhedron is a convex set

A polytope is a bounded polyhedron

1. $\vec{z}$ is a corner point if $\vec{z}$ cannot be written as a strict convex combination of points in the polyhedron.

2.

3. A corner point of $P$ is a face of $P$ of dimension 0.

A function $f:\mathbb{R}^n \to \mathbb{R}$ is called convex (function) if for all $\vec{x}, \vec{y} \in \mathbb{R}^n$ and $0\leq t\leq 1$ we have $f\left((1-t)\vec{x} + t\vec{y}\right)\leq (1-t)f(\vec{x})+tf(\vec{y})$

A function $f:\mathbb{R}^n \to \mathbb{R}$ is called concave (function) if for all $\vec{x}, \vec{y} \in \mathbb{R}^n$ and $0\leq t\leq 1$ we have $f\left((1-t)\vec{x} + t\vec{y}\right)\geq (1-t)f(\vec{x})+tf(\vec{y})$

A function of $f: \mathbb{R}^n \to \mathbb{R}$ is called a linear function if $f(\vec{x}) = \vec{a}\cdot \vec{x}$ where $\vec{a}\in \mathbb{R}^n$
Remark: A linear function is both convex and concave

A function of $f: \mathbb{R}^n \to \mathbb{R}$ is called an affine function if there exists $\vec{a}\in \mathbb{R}^n, b\in \mathbb{R}$ such that $f(\vec{x}) = \vec{a} \cdot \vec{x} +b$
Remark: $f$ is concave $\iff f$ is convex

A function $f: \mathbb{R}^n \to \mathbb{R}$ is called continuous if $\forall \lim_{i\to \infty} \vec{s}_i = \vec{s} \implies \lim_{i\to \infty}f(\vec{s}_i) = f(\vec{s})$

A subset of $a\in\mathbb{R}^n$ is called affine subspace of $\mathbb{R}^n$ if it is the translation of some vector (linear) space $\mathbb{R}^n$ by constant vectors.

i.e. there exists $v\subseteq v+\vec{w}=\{\vec{v}+\vec{w} \mid \vec{v} \in V\}$

In other words, $a\subseteq \mathbb{R}^n$ is called affine if there exists a vector space $v\subseteq \mathbb{R}^n$ and a vector $\vec{w}\in \mathbb{R}^n$ such that $a=v+\vec{w}$

We let $S\subseteq \mathbb{R}^n$ be any subset of $\mathbb{R}^n$. The dimension of $S$ we define it as $\dim(S) = \min\{\dim(A) \mid S \subseteq A \text{, A is an affine set} \}$

$\vec{Z}(t) = (1-t)\vec{x}+t\vec{y} \text { for } 0\leq t \leq 1$, $\vec{Z}(t)$ is a convex combination of $\vec{x}$ and $\vec{y}$

$Z_{LP} = \max \{3x_1+2x_2\}$ such that $\begin{cases} -x_1+2x_2\leq 2 \\ x_1+x_2 \leq 4 \\ x_1-x_2 \leq 2 \\ x_1, x_2 \geq 0 \end{cases}$

We introduce slack varaibles $s_1, \ldots, s_m$ where $m$ is the number of equations (inequalities/constraints) and get the augmented form of the primal problem: $Z_{LP}= \max\{3x_1+2x_2\}$ such that $\begin{cases} -x_1+2x_2 + s_1 = 2 \\ x_1+x_2+s_2 = 4 \\ x_1-x_2 + s_2 = 2 \\ x_1, x_2, s_1, s_2, s_3 \geq 0 \end{cases}$

$W_{LP} = \min \{2y_1+4y_2+2y_3\}$ such that $\begin{cases} -y_1 + y_2 +y_3 \geq 3 \\ 2y_1 + y_2 -y_3 \geq 2 \\ y_1, y_2, y_3 \geq 0 \end{cases}$

We introduce surplus varaibles $t_1, \ldots, t_n$ where $n$ is the number columns of $A$ and get the augmented form of the dual problem: $W_{LP} = \min \{2y_1+4y_2+2y_3\}$ such that $\begin{cases} -y_1 + y_2 +y_3 -t_1 = 3 \\ 2y_1 + y_2 -y_3 -t_2 = 2 \\ y_1, y_2, y_3, t_1, t_2 \geq 0 \end{cases}$

Two corner points of $P$ are called adjacent if the line segment between them is an edge of $P$

Given the followin augmented form the of a maximization problem: max $z = 3x_1+x_2$ such that $\begin{cases} 4x_1+x_2+x_3 = 25 \\ 2x_1+3x_2 + x_4 = 15 \\ x_1, x_2, x_3, x_4 \leq 0 \end{cases}$

Initialization: $N = \{x_1, x_2\}$ or $N=\{1, 2\}$ are non-basic variables, $B = \{x_3, x_4\}$ or $B = \{3, 4\}$ are basic variables.

basic and non-basic variables are fluid, meaning they can change at each step of the simplex method.

We suppose there are $2n$ students to be assigned to $n$ double rooms, such that each student is assigned exactly one roomate. For each $1 \leq i \leq 2n$ there is a cost value $c_{ij}$ when student $i$ and student $j$ are assigned together.

Problem: finding the pairing that minimizes the total cost (value).

$N = \{1, \ldots, n\}$ is a set of potential sites for facitlities. The cost for setting up a facility at location $j$ is $c_j$. Let $I = \{1, \ldots, m\}$ be a set of clients. The cost for serving the client $i$ at location $j$ is $h_{ij}$.

Problem: Choose a set of locations to set up facilities and assign each client to a facility to minimize the total cost. There is no restriction on the number of clients served at a certain facility.

We consider $V = \{1, \ldots, n\}$ be a set of nodes representing cities. Let $A$ denote a set of arcs representing direct routes, from one city to another city. We denote by $c_{ij}$ the cost of traveling along the route $(i, j)$.

Problem: Find a "tour" starting at $1$, visiting each city exactly once and returning to city $1$ with the minimum total cost.

There are n people to assign m jobs to. Assume $n\geq m$. Each job must be done by exatly one person. Each person must hold at most one job. The cost of person $j\in \{1, ..., n\}$ doing job $i\in \{1, ..., m\}$ is given by $c_{ij}$. We record this information in the cost matrx $C_{ij}$ for $\{1\leq i \leq m\}$ and $\{1 \leq j \leq n\}$, where $i$ denotes the job and $j$ denotes the person.

The problem: assign people to jobs such that the cost is minimum and each job is done.

F is a packing $\iff$ (by definition) $\forall j \neq l \in F$ we have $M_j \cap M_l = \empty$
$\iff \forall j \neq l \in N$ and $x_j = x_l = 1$ we have $\forall i \in M_j \implies i\notin M_l$
$\iff j \neq l \in N$ and $x_j=x_l = 1$ we have $a_{ij} \implies a_{il} = 0$
$iff \forall \neq l \in N \quad \forall i \in M \quad a_{ij}x_j = 1 \implies a_{il}x_l=0$
$\iff \sum_{j=1}^ma_{ij}x_j\leq 1\quad \forall i\in M$
$\iff A\vec{x}\leq \vec{1}$

We start by rewritting the dual in the stadard form: $D(P): min\{\vec{y}\cdot\vec{b} \leq \vec{y}^TA\geq \vec{c}^T, \vec{y} \in \mathbb{R}_+^n\}$.
$(\text{take transpose}) \implies \vec{y}^TA \leq \vec{c}^T (\text{simplify}) \implies (\vec{y}^TA)^T\leq (\vec{c}^T)^T (\text{take minus}) \implies (-A^T)\vec{y} \leq (\vec{c})$
$D(P) \iff -\max\{(-\vec{b})\cdot\vec{y} \mid -A^T\vec{y} \leq -\vec{c}, \vec{y} \in \mathbb{R}_+^m\}$
$D(D(P)): -min\{\vec{x}\cdot\vec{c} \leq \vec{x}^T-A^T\geq -\vec{b}^T, \vec{x} \in \mathbb{R}_+^m\} \iff \max\{(-\vec{c})\cdot\vec{x} \mid \vec{x}^T(-A^T) \geq -\vec{b}^T, \vec{x} \in\mathbb{R}_+^n\}$
$ \iff \max\{\vec{c}\cdot\vec{x} \mid A\vec{x}, \vec{x}\in \mathbb{R}_+^n\}$

If $(P)$ is unboudned, then $(D)$ is not feasible

if $\vec{x}^*$ is an optimal solution for $(P)$ and $\vec{s}^*$ is the corrresponding vector of slack values and $\vec{y}^*$ is an optimal solution for $(D)$ with $\vec{t}^*$ the corresponding vector of surplus values, then the following equalities hold: $(\#) \begin{cases} \vec{x}^* \cdot \vec{t}^* = 0 \\ \vec{y}^* \cdot \vec{s}^* = 0 \end{cases} \iff \begin{cases} x_j \cdot t_j = 0 \forall i \leq j \leq n \\ y_i \cdot s_i = 0 \forall 1 \leq i \leq m \end{cases}$

If the following equalities hold: $(\#) \begin{cases} \vec{x}^* \cdot \vec{t}^* = 0 \\ \vec{y}^* \cdot \vec{s}^* = 0 \end{cases} \iff \begin{cases} x_j \cdot t_j = 0 \forall i \leq j \leq n \\ y_i \cdot s_i = 0 \forall 1 \leq i \leq m \end{cases}$, then $\vec{x}^*$ is an optimal solution for $(P)$ and $\vec{s}^*$ is the corrresponding vector of slack values and $\vec{y}^*$ is an optimal solution for $(D)$ with $\vec{t}^*$ the corresponding vector of surplus values.

let $f:D \to \mathbb{R}$, where $D \subseteq \mathbb{R}^n$, be a continuous function which is also convex. Let $S \subseteq \mathbb{R}^n$ be a bounded closed and convex subset. Then there exists a $\vec{w}$ on the boundary of $S$ such that $f$ has global maximum at $\vec{w}$.