This year I took a course about linear programming. Actually its name is “linear optimisations”. But i think i still not really understand some major concepts about linear algebra…

Here are some notes when I’m reviewing and preparing for the final exam.

A linear program is said to be in standard form if it has the following structure:

Minimise $c \cdot x$

Subject to

$Ax = b \ x \geq 0$

The matrix $A$ is called the constraint matrix. Each row of the matrix is a single constraint. Each column of the matrix represents a variable in the LP.

So let’s give an example for a LP. Here is a LP for edge colouring:

Let $\mathcal{M}$ be the set of all matching in the input graph,

Minimise $\sum_{M\in \mathcal{M}} $

Subject to

$$\begin{matrix} \sum{M\in \mathcal{M} :e \in M} & x_{M} = 1 & \forall e \in E \\ & x_{M}\geq 0& \forall e\in E \end{matrix}$$

And we can deduce its dual. A dual of a LP has the same solution with the LP itself.

Minimise $\sum_{e\in E}y_e $

Subject to

$$\begin{matrix} \sum_{e\in M} & y_{e} \leq 1 & \forall M \in \mathcal{M} \\ & y_e \, free& \forall e\in E \end{matrix}$$

Separation oracle:

Detect whether a given solution x follows the constraint in the LP. If not, return the violated constraint.

Usually separation oracle are used to help with solving LPs with a large number of constraints. We can give an example with the dual problem above.

Our example:

Find a matching $M \in \mathcal{M}$ Maximising $y(M)= \sum_{e\in M} y_{e}$

If $y(M) \geq 1$ , we found a violated constraint.

Else, it is feasible.

Submodular functions:

If $S \in T$

$f(S+x)-f(S)\geq f(T+x)-f(T)$

I took me a while to understand it… To make it simple it just means “adding a new element to a small set is much more beneficial than adding it to a larger set”. A good example is the coverage function which G(V,E) is a graph and h(S) = number of neighbours of vertices from S. h(x) will get smaller as set S grows cause we only have |V| vertices total. The more vertices in your set the less neighbours you can get.