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.

Implementing Advanced MIP Start for TspIpSolver