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,
\begin
&\max&\sum_
^n v_i x_i
&\text
& \sum_
^n w_i x_i &\leq b
&&x_i & \in {0,1}&i&=1,\ldots,n,
\end
for any set
C \subset {1,\ldots,n}
such that
\sum_
w_i > b
we can add the cover inequalities
\sum_
x_i \leq |C|-1
To be completely concrete, suppose that
n=2
, and our instance was
\begin
&\max& x_1 + 2x_2
&\text
& 3x_1 + 4 x_2 &\leq 5
&&x_1,\, x_2 & \in {0,1}.
\end
The feasible region of this LP and the feasible region of the integer hull are shown below.
|
0 |
1 |
1.6667 |
|---|---|---|---|
LP |
1.25 |
.5 |
0 |
IP hull |
1 |
0 |
0 |
Observing that
3+5 > 5
, we can apply a cover inequality with the set
{1,2}
to obtain the inequality
x_1 + x_2 \leq 1.
Observe that adding this inequality to the knapsack formulation makes the LP relaxation integral, thus it is a stronger formulation.
User Cuts in CPLEX
User cuts are, at a high level, valid inequalities for an integer program CPLEX will optionally add while searching for an integer solution. Like lazy cuts, user cuts can be added either before the optimization begins (with addUserCut() from IloCplex) or by using a UserCutCallback (documentation here
) to detect violated constraints on the fly and add them to the formulation. CPLEX checks for violated user cuts at the highlighted stage in the diagram below.
|
As you can see, there is no guarantee that a feasible solution will satisfy all of the user cuts, as LP solutions which are integral are sent through the lazy constraints to the incumbent. Thus if a constraint is necessary for the formulation to be correct, but you want to check for it as a user cut, you must also check for it as a lazy cut. Additionally, we have the benefit that our method for identifying user cuts doesn't need to work 100% of the time, as if it fails we always have the lazy cuts for insurance. This is how we will be using user cuts for our TSP solver.