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.
Implementing Advanced MIP Start for TspIpSolver
We have provided an implementation of Chirstofides algorithm for your convenience in the class ChristofidesSolver. The solver has a single method:
Method Name |
Return Type |
Arguments |
Description |
|---|---|---|---|
approximateBestTour |
List<E> tour |
Set<E> suggestedEdges |
Returns the tour given by running Christofides algorithm on the input graph and edge weights. The algorithm attempts to include all edges in suggestedEdges by adjusting the weights when forming a MST (if suggested edges is empty, the result is classical Christofides). If suggestedEdges contains a loop, will return null instead of a tour. |
TODO: rename variable to suggestedEdges.
To incorporate the solver, add the field to TspIpSolver
private ChristofidesSolver<V,E> christofides;
We need a utility method that given a set of edges, will create an array of zeros and ones. Directed after edgesUsed() in TspIpSolver, and the method
/**
* Given a subset of the edges, produces a binary vector indicating which edges were included using the same ordering as edgeVariablesAsArray
* @param edgesUsed a subset of the set of edges in the grpah
* @return an array of zeros and ones where the ith entry corresponds to the ith edge variable from edgeVariablesAsArray
*/
private double[] inverseEdgesUsed(Set<E> edgesUsed){
double[] edgeVals = new double[this.edgeVariablesAsArray.length];
for(int i =0; i < edgeVals.length; i++){
edgeVals[i] = edgesUsed.contains(edgeVariables.inverse().get(edgeVariablesAsArray[i])) ? 1 : 0;
}
return edgeVals;
}
Finally, at the very end of the constructor, add the lines
if(options.contains(Option.christofidesApprox)){
System.out.println("Beginning Christofides...");
ChristofidesSolver<V,E> christofides = new ChristofidesSolver<V,E>(graph,tspInstance.getEdgeWeights());
List<E> christofidesApproxTour = christofides.approximateBestTour(new HashSet<E>());
Set<E> submittedTour = new HashSet<E>(christofidesApproxTour);
double[] edgeVals = inverseEdgesUsed(submittedTour);
cplex.addMIPStart(edgeVariablesAsArray, edgeVals);
}