\documentclass{article}
\usepackage{amsmath}
\usepackage{mdwtab}
\usepackage{mathenv}
\usepackage{graphicx}
\begin{document}
\section{Integer Multicommodity Flow Problem}
The problem we try to solve is the Splitable Integer Multicommodity Flow
Problem. The input for the problem is a directed graph $G(V,E)$; for each arc
of the graph three values are specified: a (non-negative integer) lower and
upper bound on the total amount of flow that can pass through the arc and the
cost of sending a unit flow through the arc. $N$ commodities (source-sink
pairs together with the desired flow from the source to the sink) are also
specified. The solution output is the amount of flow on each arc for each
commodity. To describe the problem we will use the following notation:
\begin{center}
\begin{tabular}{lp{3.5in}}
\hline 
$l$: & The vector of lower bounds on the individual and total amount of
flows on the arcs of $G$. \\
$u$: & The vector of upper bounds on the individual and total amount of
flows on the arcs of $G$. \\
$w$: & The vector of weights (i.e., the cost of sending a unit flow) of the
arcs of $G$. \\
$f_i$: & The flow for commodity $i$ \\ 
$\textit{source}_i$: & The source node for commodity $i$ \\ 
$\textit{sink}_i$: & The sink node for commodity $i$ \\ 
$d_i$: & The demand vector for commodity $i$. \\
\hline
\end{tabular}
\end{center}
Superscripting with an edge $e \in E$ (a node $v \in V$) any vector on the
arcs (nodes) of $G$ indicates the entry of the vector on that arc (node).

With this notation it is fairly simple to model this problem as an integer
programming problem:
\begin{eqnarray}[r:l]
\min\sum_{i=1}^Nw^Tf_i
& \nonumber \\
l^e \le \sum_{i=1}^Nf^e_i \le u^e 
& \forall e\in E \label{cap-total}\\
\sum_{(w,v)\in E}f^e_i - \sum_{(v,w)\in E}f^e_i = d^v_i 
& \forall v\in V \label{flow-conv}\\
l \le f_i \le u 
& i=1,...,N \label{cap-edge}\\
f_i \textrm{\ integral} 
& i=1,...,N
\end{eqnarray}

Constraints (\ref{cap-edge}) and (\ref{cap-total}) enforce the capacity
constrints on each arc for each flow individually and for all flows combined.
Constrints (\ref{flow-conv}) are the flow conservation constraints. Finally,
we require integrality.

\section{Column generation}
The solution method is column generation. The columns will correspond to flows
in the network. For each commodity we will generate integral flows. The flows
generated for commodity $i$ will form the columns of matrix $F_i$. Therefore
for each $i$ the matrix $F_i$ has $|E|$ rows and as many columns as the number
of flows we have generated for that commodity. As a shorthand we will say that
$f_i \in F_i$ if $f_i$ is a column of $F_i$. Introducing $\lambda_i$ for each
commodity as the solution vector that indicates what combination of the
columns of $F_i$ will provide the ultimate flow for commodity $i$ we have the
following formulation:
\begin{eqnarray}[r:l]
\min\sum_{i=1}^Nw^TF_i\lambda_i
& \nonumber \\
l \le\sum_{i=1}^NF_i\lambda_i\le u 
& \label{MP-bound} \\
e^T\lambda_i = 1 & 
i=1,...,N \label{MP-conv}\\
F_i\lambda_i \textrm{\ integer} 
& 
\end{eqnarray}
Obviously, the two formulations are equivalent and the latter is the master
problem when Dantzig-Wolfe decomposition is applied to the former. The
corresponding subproblems (used to generate the flows in $F_i$) are for all
$i=1,...,N$:
\begin{eqnarray}[l:r]
\min(w^T-\pi^T)f_i-\nu_i & \nonumber \\
\sum_{(w,v)\in E}f^e_i - \sum_{(v,w)\in E}f^e_i = d^v_i 
& \forall v\in V \label{MP-flow-conv}\\
l \le f_i \le u & \\
f_i \textrm{\ integral} &
\end{eqnarray}
where $\pi$ is the dual vector corresponding to the global bound constraints
(\ref{MP-bound}) and $\nu_i$ is the dual value corresponding to the
$i^\textrm{th}$ convexity constraint (\ref{MP-conv}).

Though the subproblem is an integer programming problem, it is a simple
maximum flow problem. To simplify coding in this example we will solve it with
an LP solver.
\end{document}
