Versions Compared

Old Version 29

changes.mady.by.user Ross Michael Anderson

Saved on

compared with

New Version 30

changes.mady.by.user Ross Michael Anderson

Saved on

Key

  • This line was added.
  • This line was removed.
  • Formatting was changed.
{} {composition-setup} {pagetree:root=Tutorial} h1. 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-cloak:id=TspIpSolverStart} _Toggle TspIpSolver.java_ {cloak:id=TspIpSolverStart|visible=true} {code} 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; } } {code} {cloak} 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 {code} private IloCplex cplex; private TspInstance<V,E> tspInstance; private final ImmutableBiMap<E,IloIntVar> edgeVariables; {code} and initialize them, as below. {code} 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 } {code} 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 {mathinline}e{mathinline} of {{set}}, finds the corresponding variable {mathinline}x_e{mathinline} and returns {mathinline}\sum_{e \in \text{set}} x_e {mathinline} * 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. {toggle-cloak:id=ConstraintsSolution} _Solution_ {cloak:id=ConstraintsSolution|visible=false} {code} //the degree constraints for(V vertex: graph.getVertices()){ cplex.addEq(Util.integerSum(cplex, edgeVariables, graph.getIncidentEdges(vertex)), 2); } {code} {cloak} 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 {mathinline}e{mathinline} of {{set}}, gets the corresponding variable {mathinline}x_e{mathinline} from {{variables}} and the number {mathinline}d_e{mathinline} from {{coefficients}} and returns an expression for {mathinline}\sum_{e \in \text{set}} d_e x_e {mathinline}. {toggle-cloak:id=ObjectiveSolution} _Solution_ {cloak:id=ObjectiveSolution|visible=false} {code} //the objective cplex.addMinimize(Util.integerSum( cplex, edgeVariables, graph.getEdges(),tspInstance.getEdgeWeights())); {code} {cloak} h1. A First Solution by LazyConstraintCallback h1. Interesting TSP References. On solving TSPs * [
Wiki Markup
Composition Setup
 Page Tree
root15DOTs60ia13:Tutorial
A First Solution by LazyConstraintCallback
Interesting TSP References.
On solving TSPs
...
  • On 
...
  •  Construction 
...
  •  and 
...
  •  Improvement 
...
  •  Heuristics: 
...
...
TSP 
...
 Problem 
...
 Instances
...
...