You are viewing an old version of this page. View the current version.

Compare with Current View Page History

« Previous Version 29 Next »

Setting up the problem

Open the file src/solver/TspIpSolver.java by double clicking it from the Project Explorer. This is the file we will be primarily editing. It should contain the following (after the imports):
Toggle TspIpSolver.java 

public class TspIpSolver<V,E> {
	
	public static enum Option{
		lazy,userCut, randomizedUserCut, christofidesApprox, christofidesHeuristic,twoOpt,incumbent;
	}
	
	public TspIpSolver(TspInstance<V,E> tspInstance) throws IloException{
		this(tspInstance,EnumSet.of(Option.lazy, Option.userCut, 
		Option.christofidesApprox, Option.christofidesHeuristic));
	}
	
	public TspIpSolver(TspInstance<V,E> tspInstance, EnumSet<Option> options) throws IloException{}
	
	public void solve() throws IloException{		
	}
	
	public ImmutableSet<E> getEdgesInOpt(){
		return null;
	}
	
	public double getOptVal(){
		return 0;
	}	
}

The Option arguments will be needed later. First, we need to set up the objective and the degree constraints. First, add the following fields to the class

private IloCplex cplex;
private TspInstance<V,E> tspInstance;
private final ImmutableBiMap<E,IloIntVar> edgeVariables;

and initialize them, as below.

	public TspIpSolver(TspInstance<V,E> tspInstance, EnumSet<Option> options) throws IloException{
		this.options = options;
		this.tspInstance = tspInstance;
		this.cplex = new IloCplex();
		UndirectedGraph<V,E> graph = tspInstance.getGraph(); //for convenience, we will be using this a lot
		this.edgeVariables = Util.makeBinaryVariables(cplex, graph.getEdges());
		//the degree constraints
		//the objective		
	}

The constraints and objective still need to be added to the cplex object. Try adding them yourself! The following methods should be useful for making the constraints:

  • From Util, public static <T> IloLinearIntExpr integerSum(IloCplex cplex, BiMap<T,IloIntVar> variables, Iterable<T> set)
    • For each element \( e \) of set, finds the corresponding variable \( x_e \) and returns \( \sum_{e \in \text{set}} x_e \)
  • From IloCplex, public IloRange addEq(IloNumExpr e, double v)
    • Adds the equality constraint e = v
  • From UndirectedGraph<V,E>, public Collection<E> getIncidentEdges(V vertex)
    • returns the edges of the graph that are incident to vertex

If you are unfamiliar with Java, consider viewing the solution for the constraint, then trying the objective yourself.
Solution

For the objective, we need the functions:

  • From Util, public static <T> IloLinearNumExpr sum(IloCplex cplex, BiMap<T,IloIntVar> variables, Iterable<T> set, Function<? super T,? extends Number> coefficients)
    • For every element \( e \) of set, gets the corresponding variable \( x_e \) from variables and the number \( d_e \) from coefficients and returns an expression for \( \sum_{e \in \text{set}} d_e x_e \) .

Solution

A First Solution by LazyConstraintCallback

Interesting TSP References.

On solving TSPs

TSP Problem Instances

  • No labels