The root page 15DOTs60ia13:Tutorial could not be found in space 15.S60 SSIM: Software Tools for Operations Research.
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,
for any set \( C \subset \{1,\ldots,n\} \) such that
\[ \sum_{i \in C} w_i x_i > b \]we can add the cover inequalities
\[ \sum_{i \in C} x_i \leq |C|-1 \]To be completely concrete, suppose that \( n=2 \) , \( v_1 = v_2 =1 \) , \( b = 5 \) , \( w_1 = 3 \) , and \( w_2 = 4 \) .
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.
|