Formulating Linear Programs
Linear Programming(LP) is a widely used technique in algorithm design and analysis, especially for getting good approximations for NP hard problems. The first step in LP would be to formulate the the problem as an optimization problem with linear constraints where the quantity we are trying to optimize is also linear. It is a good excersize to formulate simple problems as linear programs. Linear programming problems typically expressed in their canonical form look like this:
\[\begin{equation*} \begin{array}{ll@{}ll} \text{minimize} & \displaystyle\sum\limits_{j=1}^{m} c_{j}x_{j} &\\ \text{subject to}& \displaystyle\sum\limits_{j=1}^{m} a_{i,j}x_{j} &\geq b_i &i=1 ,..., n\\ & x_{j} \ge 0& &j=1 ,..., m \end{array} \end{equation*}\]Here we are supposed to assign values for \(x_1,x_2,...,x_m\) such that we minimize the cost \(\sum_{j=1}^{m} c_jx_j\) subject to the above \(n + m\) inequalities. \(c_1,c_2,...,c_m\) are called cost coefficients. An Integer Linear program is an LP where some or all the variables are restricted to be integers.
Lets formulate problems as Integer Linear Programs(ILP).
Minimum Vertex Cover
Given a undirected graph \(G(V,E)\). A set of vertices \(V'\) is a vertex cover of \(G\) if every edge has atleast one endpoint in \(V'\). A vertex cover of the smallest cardinality is the Minimum vertex cover.
Let \(x_v\) be an indicator variable which indicates whether a vertex is part of the vertex cover or not. This is a 0-1 ILP as the variables are constrained to be binary.
\[x_v= \begin{cases} 1 & \text{If v} \in V'\\ 0 & \text{otherwise}\\ \end{cases}\]The cardinality of the vertex cover is simply the sum of all the indicator variables. So we are trying to minimize:
\[\sum_{v \in V} x_v\]Subject to the constraints:
\[x_a+x_b \ge 1 \quad \forall (a,b) \in E\]This constraint ensures that each edge has atleast one vertex in the vertex cover.
Minimum Spanning Tree
Given a weighted undirected connected graph \(G(V,E)\), find the tree \(T\) such that the sum of the weights of the edges in the tree is minimum.
Let \(x_e\) be an indicator variable which indicates whether an edge is part of the tree or not. This is again 0-1 ILP as the variables are constrained to be binary.
\[x_e= \begin{cases} 1 & \text{If e} \in T\\ 0 & \text{otherwise}\\ \end{cases}\]The cost of including edge \(e\) in the tree would be its weight \(w_e\). So we are trying to minimize:
\[\sum_{e \in E}w_ex_e\]Subject to the constraints:
\[\sum_{e \in E}x_e = \mid V \mid -1 \\ \sum_{e \in E(S)} x_e \le \mid S \mid -1 \quad \forall S \subseteq V\]\(E(S)\) is the set of edges with both vertices in \(S\). The first condition ensures that we have exactly \(\mid V\mid -1\) edges in the graph formed by the edges having \(x_e=1\). The second condition ensures that there are no cycles formed in any subgraph. The graph formed by these constraints is a tree as it has exactly \(\mid V\mid -1\) edges and has no cycles.
An alternative constraint which is also correct is:
\[\sum_{e \in Cut(S,V-S)} x_e \ge 1 \quad \forall S \subset V, S\neq \emptyset\]\(Cut(A,B)\) is the set of edges with one vertex in \(A\) and the other in \(B\). This constraint ensures that the graph is connected. Since the graph which is minimally connected is a tree, this constraint is sufficient.