View Source

 

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 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|http://pic.dhe.ibm.com/infocenter/cosinfoc/v12r5/index.jsp?topic=%2Filog.odms.cplex.help%2Frefjavacplex%2Fhtml%2Filog%2Fcplex%2FIloCplex.UserCutCallback.html]) 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.
{gliffy:name=userCutCplex|align=left|size=L|version=2}
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.

h1. Using UserCutCallback

{{UserCutCallback}} works very similarly to {{LazyConstraintCallback}}.  Mathematically, you are passing CPLEX the following function:
* *Input:* A fractional solution to the LP relaxation of your problem, potentially after some lazy constraints, CPLEX generated cuts, or user cuts have been added
* *Output:* A list (potentially empty) of violated valid inequalities.

Note that there is no assumption that the list is is nonempty, and that there is no guarantee that the {{UserCutCallback}} will ever be checked.  The Javadoc for {{UserCutCallback}} can be found [here|http://pic.dhe.ibm.com/infocenter/cosinfoc/v12r5/index.jsp?topic=%2Filog.odms.cplex.help%2Frefjavacplex%2Fhtml%2Filog%2Fcplex%2FIloCplex.UserCutCallback.html], but we summarize the important methods in the table below (the interface is very similar to that of {{LazyConstraintCallback}}):

||Method Name||Return Type||Arguments||Description|| 
|getValue|double|IloNumVar var|Returns the solution value of var at the current node.| 
|getValues|double[]|IloNumVar[] vars|Returns the solution values for vars at the current node.| 
|add|IloRange|IloRange cut|Adds the constraint cut to the model. Assumes cut is linear.| 
|isAfterCutLoop|boolean| |This method indicates whether or not the callback was invoked after CPLEX stopped generating cuts and called the callback a final time.|

The final method requires some explanation.  The "cut loop" refers to the loop in the above diagram where CPLEX looks for cuts, adds cuts, and resolves the LP relaxation.  While CPLEX could do this indefinitely until an optimal integer solution was found (which would solve the whole IP, see [cutting plane method|http://en.wikipedia.org/wiki/Cutting-plane_method] and chapter 9 of [Optimization over the Integers|http://www.dynamic-ideas.com/Books/097591462/OptOverInt-toc-ex.pdf]), this would generally take a long time.  Instead, CPLEX uses some internal Heuristics (which you can toggle, although I don't recommend it) to control how many cuts to add, then it "exits the cut loop" and will not generate more cuts.  By calling {{isAfterCutLoop}}, you can tell if CPLEX is done adding cuts before you start adding your own.  It might be a good idea to wait until CPLEX is done, as the cuts it adds may change the LP so much that the cut you were about to add becomes irrelevant.  Alternatively, the cut you add may cause CPLEX to add smarter cuts.  Whether or not waiting until the cut loop is over to add cuts is something that you will need to determine for your own problem.

Otherwise, the same warnings [as before|A First Solution by LazyConstraintCallback#Using LazyConstraintCallback] about using {{cplex.ge()}} instead of {{cplex.addGe()}} and using {{getValues()}} instead of {{getValue()}} are still relevant.  In fact, the performance hit on using {{getValue()}} is much more severe here than for {{LazyConstraintCallback}}, as we will pay the price at every node, not just at every integer solution.

h1. Polynomial Time Separation for TSP over Cutset Constraints