Wiki Markup |
---|
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} |
User Cuts in CPLEXUser 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. 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\}
|
CPLEX checks for violated user cuts at the highlighted stage in the diagram below. Gliffy Diagram |
---|
|