TSPLIB performance

Run your new code (through main, with both the lazy and userCut options) on the same TSPLIB problems as before and compare the performance. My running times were

We see that the running time increased on every example! What is going on here? Lets add a few timely print statements to our UserCutCallback to try and better understand how the performance is worse.

			V source = graph.getVertices().iterator().next();
			double best = Double.MAX_VALUE;
			System.out.print("looking for cut... ");
			for(V sink : graph.getVertices()){
				if(sink != source){
					Set<V> cutNodes = minCutSolver.computeMinCut(source, sink);
					Set<E> cutEdges = tspInstance.cutEdges(cutNodes);
					double cutVal = Util.calcSum(cutEdges,edgeWeights);
					best = Math.min(best, cutVal);
					if(cutVal < minCutVal){
						cutSets.add(cutEdges);
					}
				}
			}
			System.out.println("found " + cutSets.size() + " cuts, best " +	best);

Lets run the code again on d198 and take a closer look at the output.
Show d198 output

Running the code with and without user cuts, judging from the print statements (which are not entirely reliable), it seems that the bottle neck is actually solving the max flow min cut problems. While we know there are better ways to compute a global minimum cut from our previous discussion, instead we will explore some heuristics to vastly improve performance without writing a lot of code.

Look at the first column of CPLEX's output, which gives the number of nodes generated thus far. When this column is zero, that means we are still working on the root node. Here are a few observations about our cuts:

  • More often then not, when there is a violated cut, the most violated cut has weight zero.
  • This is particularly true towards the end of the optimization when we are doing branch and bound (perhaps the extreme action of forcing a variable to take the value one or zero causes the solution to make loops).
  • The value of the root LP is significantly larger (which is better) with the cutset constraints, as seen below
  • The total number of nodes created using the cutset constraints is much smaller, as seen below.

These final two bullet points indicate that we do stand to gain a lot from the cutset formulation if we can get the running time of our separation routine under control. We now give a few heuristics to improve performance.

Check Connected Components First

The first heuristic is as follows: on the subgraph using the edges with only nonnegative weight (which we have already formed) check for connectivity. If you have more than one connected component, then any cut separating connected components will have weight zero and hence be minimal. As we can check for connected components in time, we will save a lot of time when there are multiple connected components. Viewing the log file above, we this is frequently the case (as conversely, whenever the best cut is zero, there must have been multiple connected components). Notice that the class MinCutSolver (which is holding the subgraph using only edges with positive weight) already has a method built in:

Method Name

Return Type

Arguments

Description

checkConnectedComponents

Set<Set<V>>

 

Returns the nodes of the subgraph using only edges with positive weight, partitioned into connected components.

To integrate this with the UserCutCallback, simply add the code

			MinCutSolver<V,E> minCutSolver = new MinCutSolver<V,E>(graph,edgeWeights);
			Set<Set<E>> cutSets = new HashSet<Set<E>>();
			//add here
			Set<Set<V>> connectedComponents = minCutSolver.checkConnectedComponents();
			if(connectedComponents.size() > 1){				
				for(Set<V> connectedComponent: connectedComponents){
					cutSets.add(tspInstance.cutEdges(connectedComponent));				
				}
				System.out.println("trivial cuts exist, found " + cutSets.size());
			}
			else{
				//old
				V source = graph.getVertices().iterator().next();
				//...
				System.out.println("found " + cutSets.size() + " cuts, best " +	best);
				//add extra brace
			}			
			for(Set<E> cutEdges: cutSets){
				this.add(cplex.ge(Util.integerSum(cplex, edgeVariables, cutEdges), 2));
			}

Observe the large improvement in running time below.

However, we are still not faster than our solver without user cuts, and we still can't practically solve d493 (although we get a lower bound that is 99.6% of the optimum in about 60 seconds). Our separation routine is still too slow, and is notably ineffective towards the end of the optimization. We give a quick fix in the next section.

Use Only Connected Components After Root Node

Recall our observation from the log file that as we progressed in the branch and bound tree, it became rare that we encountered violated cutset constraints where the graph was not disconnected into multiple peices (i.e. constraints violated by 2.0). A coarse but effect solution for this problem is to simply stop solving max flow problems after a certain point in the optimization, and rely on the heuristic from the previous section (as a user cut) in combination with the lazy constraints. A convenient (and reasonable) place to stop attempting these max flow problems is when we solve the root node and start branching. That we chose the root node to stop looking for expensive cuts was not a coincidence: we see in was not a coincidence, our earlier computations on the quality of the cutset LP relaxation suggest that once we have solved the root node, our lower bound will be within 1% of optimal, leaving little room for further improvement by more cutting planes. Using the method getNnodes64(), we can modify MinCutCallback with a single line of code as follows:

			//...
			if(connectedComponents.size() > 1){				
				for(Set<V> connectedComponent: connectedComponents){
					cutSets.add(tspInstance.cutEdges(connectedComponent));				
				}
				System.out.println("trivial cuts exist, found " + cutSets.size());
			}
			else if(this.getNnodes64() == 0){// <--- the only line that changed!				
				V source = graph.getVertices().iterator().next();
			//...

We see in the chart below that this new variation beats out all the other user cut heuristics thus far and is competitive with just using lazy constraints on small instances.

However, the real gain is on the larger, more challenging instances, which we can now actually solve. As seen here:
Show d493 CPLEX log

it took a little over 2 minutes to be provably within 1% of optimal, and we were able to solve the problem completely in about 12 minutes, while it took about 2 hours with only lazy constraints. Again the LP was 99.6% of optimal, so we can't make a lot of improvement with better cuts (i.e. there is more room for improvement on the primal problem of generating good integer solutions). However, we did ultimately visit over 26,000 nodes. The problem d657 is still well out of reach; after 4571 seconds (over an hour), the MIP relative gap was still 0.33%.

Next, we try two more tricks to improve performance, but they are essentially second order corrections as compared to Christofides and Two-Opt.

Use a Back Off Function After the Root Node

We now introduce the abstract class BackOffFunction. The idea of a back off function is as follows: suppose you repeatedly have the opportunity to take some action, but you do not want to take the action at every opportunity. Further, suppose that at as time passes, you want to take the action with a lower frequency. Suppose that is the waiting time between the and time that the action was taken. The various subclasses of BackOffFunction provided will deterministically set as

Class

Constructor Arguments

ConstantWaiting

int

LinearWaiting

 

QuadraticWaiting

 

ExponentialWaiting

 

InfiniteWaiting

 

Warning

If you downloaded version 2-1 or earlier, you are missing InfiniteWaiting. If you want it, paste

	/**
	 * always returns false
	 * @author ross
	 *
	 */
	public static class InfiniteWating extends BackOffFunction {		
		public InfiniteWating(){
			super(1);			
		}
		@Override
		protected int nextWaitingPeriod() {
			return 1;
		}
		public boolean makeAttempt(){
			return false;
		}
	}

at the end of BackOff.java. (If InfiniteWaiting is already at the bottom of the file, then you are fine.)

Note our strategy from the previous section is just InfiniteWaiting, and our strategy before that is just ConstantWaiting(0). Of course many other functions, perhaps more complicated, are possible. Note that ConstantWaiting technically is not backing off... In any event, back off functions are robust way to contain a potentially troublesome heuristic, as it limits how much the heuristic can hurt you, since in the worst case (when the problem takes a long time to solve), you will stop using the heuristic. The class BackOffFunction (and its subclasses) are all used through the single method

Method Name

Return Type

Arguments

Description

makeAttempt

boolean

 

Call this function at each possible time to take the action. Will return true iff you should take the action this time period.

The idea for using the back off function is as follows: we will still always solve the max flow problems at the root node, but after the root node, when the connectivity test does not produce a new cut, we will only periodically attempt to solve the max flow problems according to the back off function. I found that Quadratic Waiting seemed about right, but feel free try anything! To make the change you only need to adjust a few lines of code. First add the back off function as a field then set in the constructor (as you please):

		private BackOffFunction backOff;
		private double minCutVal;
		
		public MinCutCallback(){
			minCutVal = 1.99;
			this.backOff = new BackOffFunction.QuadraticWaiting();
		}

Then, in the same line of code we adjusted in the previous section, write:

			//...
			if(connectedComponents.size() > 1){				
				for(Set<V> connectedComponent: connectedComponents){
					cutSets.add(tspInstance.cutEdges(connectedComponent));				
				}
				System.out.println("trivial cuts exist, found " + cutSets.size());
			}
			else if(this.getNnodes64() == 0 || this.backOff.makeAttempt()){// <--- the only line that changed!				
				V source = graph.getVertices().iterator().next();
			//...

Running the code on d493, we have the disappoiting result

However, we did visit only 24270 nodes, less than our previous algorithm. Thus if we could solve min cut separate faster, then maybe it could be worth attempting min cut occasionally after the root node. We attempt this in the next section.

If all else fails, your code should look like this:
Toggle TspIpSolver

Check Random s-t Cuts

In this final section, we try to fully exploit the following idea: since user cuts are not required to find a violated inequality, it could be more efficient quickly find one with high probability and fail otherwise. Recall that in all of our previous algorithms, we fixed and then for every with , we solved a min - cut problem. Now instead, for some small fixed number of attempts , we will randomly select with and then compute the minimum - cut. Observe that we will find the global minimum cut if in at least one random attempt, we have and , or vice versa. Next, observe that if , then it is very likely we will succeed. If (in the best case scenario) , then in each trial we succeed in finding the global minimum cut with probability , thus on attempts, we would succeed at least once with probability . By tracking a little extra data and adding a few more print statements (you can try it yourself if you are interested), you can actually track the size of the minimum cut. Perhaps surprisingly, it is often quite large!

Instead of modifying MinCutCallback, we will actually create a second class RandomMinCutCallback. Paste the following after the class MinCutCallback in TspIpSolver.java.

	private class RandomMinCutCallback extends UserCutCallback{
		
		private int numAttempts;
		private Random rand;
		private BackOffFunction backOff;
		private double minCutVal;
		
		public RandomMinCutCallback(){
			numAttempts = 20;
			rand = new Random();
			backOff = new BackOffFunction.QuadraticWaiting();
			minCutVal = 1.99;
		}

		@Override
		protected void main() throws IloException {
			//do not attempt to add any cutset constraints until CPLEX is done adding constraints
			if(!this.isAfterCutLoop()){
				return;
			}
			double[] edgeVals = this.getValues(edgeVariablesAsArray);
			Map<E,Double> edgeWeights = getNonZeroEdgeWeights(edgeVals);
			UndirectedGraph<V,E> graph = tspInstance.getGraph();
			MinCutSolver<V,E> minCutSolver = new MinCutSolver<V,E>(graph,edgeWeights);
			Set<Set<E>> cutSets = new HashSet<Set<E>>();
			Set<Set<V>> connectedComponents = minCutSolver.checkConnectedComponents();						
			if(connectedComponents.size() > 1){				
				for(Set<V> connectedComponent: connectedComponents){
					cutSets.add(tspInstance.cutEdges(connectedComponent));				
				}
				System.out.println("trivial cuts exist, found " + cutSets.size());
			}
			else if(this.getNnodes64() == 0 || this.backOff.makeAttempt()){
				double best = Double.MAX_VALUE;
				System.out.print("looking for cut... ");
				List<V> nodes = new ArrayList<V>(graph.getVertices());
				for(int i = 0; i <numAttempts; i++){				
					V source = nodes.get(rand.nextInt(nodes.size()));
					V sink = nodes.get(rand.nextInt(nodes.size()));
					if(source != sink){
						Set<V> cutNodes = minCutSolver.computeMinCut(source, sink);
						Set<E> cutEdges = tspInstance.cutEdges(cutNodes);
						double cutVal = Util.calcSum(cutEdges,edgeWeights);
						best = Math.min(best, cutVal);
						if(cutVal < minCutVal){
							cutSets.add(cutEdges);
						}
					}
				}
				System.out.println("found " + cutSets.size() + " cuts, best " + best);
			}
			
			for(Set<E> cutEdges: cutSets){
				this.add(cplex.ge(Util.integerSum(cplex, edgeVariables, cutEdges), 2));
			}						
		}		
	}

Then, replace the end of the TspIpSolver constructor (where the userCut option is parsed) with the following so we can choose the RandomMinCutCallback instead of the regular MinCutCallback.

		if(options.contains(Option.userCut)){
			cplex.use(new MinCutCallback());
			if(options.contains(Option.randomizedUserCut)){
				System.err.println("Warning, userCut and randomizedUserCut both selected, ignoring randomizedUserCut");
			}
		}
		else if(options.contains(Option.randomizedUserCut)){
			cplex.use(new RandomMinCutCallback());
		}

To run your new code, be sure to change the options in Main.main. We see that our running time improves slightly! However, some of the improvement comes from "solving" the root relaxation more quickly. However, Randomized s-t with linear waiting visits only about 20,000 nodes, showing that the cuts from linear waiting with imperfect separation are stronger then perfect cuts with quadratic waiting. However, as infinite waiting beats everything, at least on this problem we are not gaining anything by using back off functions.

What's next?

Below is output generated from using the src/output/NodeLog.java to turn the node log above into a plot. We used the MinCutCallback with the InfiniteWaiting back off function.

excerpt d493 randomized node log

While our lower bounds seem to be converging more slowly than our upper bounds, we see that it still takes a little over 5000 nodes for us to get to our strongest possible upper bound, which will help us prune away more nodes. In the next section, we work on finding strong upper bounds faster.

  • No labels