Reduce Min-Cut to 0/1 Integer Program
Hint: Let's try to encode the constraints using two types of variables: $a_v$ for each vertex $v$, and $b_{uv}$ for each edge $u,v$. The variable $a_v$ encodes which part of the cut vertex $v$ belongs to. The variables $b_{uv}$ equals 1 if the edge $(u,v)$ is cut.

We want to enforce the following constraints:


$a_s = 0$ and $a_t = 1$.
$b_{uv} = 1$ if $a_u = 1$ and $a_v = 0$ or if $a_u = 0$ and $a_v = 1$.
$\sum_{uv \in E} w(u,v) b_{uv} \leq k$.


Try to encode all these constraints as inequality constraints.