h1. Valid inequalities

Valid inequalities are additional constraints that can be added to a correct integer program that potentially strengthen the formulation, i.e. reduce the size of the feasible region for the linear programming relaxation.
For example, in the 0-1 knapsack problem,
{mathdisplay}
\begin{aligned}
&\max&\sum_{i=1}^n v_i x_i\\
&\text{subject to}& \sum_{i=1}^n w_i x_i &\leq b\\
&&x_i & \in \{0,1\}&i&=1,\ldots,n,
\end{aligned}
{mathdisplay}
for any set {mathinline}C \subset \{1,\ldots,n\}{mathinline} such that
{mathdisplay}
\sum_{i \in C} w_i > b
{mathdisplay}
we can add the _cover inequalities_
{mathdisplay}
\sum_{i \in C} x_i \leq |C|-1
{mathdisplay}
To be completely concrete, suppose that {mathinline}n=2{mathinline}, and our instance was
{mathdisplay}
\begin{aligned}
&\max& x_1 + 2x_2\\
&\text{subject to}& 3x_1 + 4 x_2 &\leq 5\\
&&x_1,\, x_2 & \in \{0,1\}.
\end{aligned}
{mathdisplay}
The feasible region of this LP and the feasible region of the integer hull are shown below.
{chart:type=xyarea|legend=true|xLabel=x\_1}
|| ||0||1||1.6667||
|LP|1.25|.5| 0|
|IP hull|1|0|0|
{chart}
Observing that {mathinline}3+5 > 5{mathinline}, we can apply a cover inequality with the set {mathinline}\{1,2\}{mathinline} to obtain the inequality
{mathdisplay}
x_1 + x_2 \leq 1.
{mathdisplay}
Observe that adding this inequality to the knapsack formulation makes the LP relaxation integral, thus it is a stronger formulation.

h1. User Cuts in CPLEX

User cuts are, at a high level, valid inequalities for an integer program that strengthen the formulation, but are not required for correctness of the formulation.  


CPLEX checks for violated user cuts at the highlighted stage in the diagram below.
{gliffy:name=userCutCplex|align=left|size=L|version=1}