Advanced MIP Start
CPLEX allows you to use a heuristic to generate an initial incumbent integer solution. Recall that at each node (for minimization problems), if the LP relaxation takes a value greater than the current incumbent, then we can prune the node without further branching. See the figure below:
|
Thus having a good incumbent initial incumbent solution will reduce the total number of nodes you visit in branch and bound. Assuming you can generate your incumbent quickly, this could reduce the running time.
Advanced MIP Start in CPLEX
The class IloCplex provides a method for setting the advanced start:
Method Name |
Return Type |
Arguments |
Description |
|---|---|---|---|
addMIPStart |
int |
IloNumVar[] vars, double[] values |
Adds the MIP start specified by its variables and values to the current problem. Multiple calls to this function will overwrite previous calls, not add additional starting points. Return indicates?? |
The advanced MIP start actually has a lot of features that we aren't using, as explained in the documentation
. It can accept only partial or infeasible solutions and then will try and "repair" them to get an incumbent. It can also apply local search techniques to improve the quality of the incumbent, but we will be doing that with a custom algorithm soon instead.
Christofides Algorithm
Christofides Algorithm is an approximation algorithm that gives a 1.5 approximation factor for metric TSP problems (TSP problems where distance/cost function between nodes is a a metric). In fact, the algorithm can be run on any TSP problem on a complete graph, although we have performance guarantee if the distances are not a metric. As all of the problems we are considering use the Euclidean metric for distance (see also Euclidean TSP), Christofides algorithm should give us good performance. The algorithm is summarized below (from wikipedia):