Versions Compared

Key

  • This line was added.
  • This line was removed.
  • Formatting was changed.

...

Section
Column
width300px
Page Tree
root15DOTs60ia13:Tutorial
Column

Problem Formulation

First, we will add the following fields to the class so we can easily reference our problem data from any method. Add

Code Block
private EnumSet<Option> options;
private IloCplex cplex;
private TspInstance<V,E> tspInstance;
private ImmutableBiMap<E,IloIntVar> edgeVariables;

and initialize them, as below.

Code Block
	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		
	}

Next, we need to add the objective and the degree constraints to the IloCplex instance. Try adding them yourself! The following methods (as defined in Solver Specification and Java Style for CPLEX) should be useful for making the degree constraints:

  • From Util, the static method integerSum(IloCplex cplex, BiMap<T,IloIntVar> variables, Iterable<T> set)
  • From IloCplex, the method addEq(IloNumExpr e, double v)
  • From UndirectedGraph<V,E>, the method getIncidentEdges(V vertex)

Toggle Cloak
idConstraintsSolution
Solution

Cloak
visiblefalse
idConstraintsSolution

For the objective, we need the functions:

  • From Util, the static method sum(IloCplex cplex, BiMap<T,IloIntVar> variables, Iterable<T> set, Function<? super T,? extends Number> coefficients)
  • From UndirectedGraph<V,E>, the method getEdges()
  • From TspInstance, the method getEdgeWeights()

Toggle Cloak
idObjectiveSolution
Solution

Cloak
visiblefalse
idObjectiveSolution

Solving and Extracting the Solution

Recall the warning from warning.

Here we fill in the blank methods solve(), getEdgesInOpt(), and getOptVal(). For performance reasons, it is a good idea to cache the solution as a field of the TspIpSolver and "shut down" CPLEX. To accomplish this, add the fields

Code Block
	private ImmutableSet<E> edgesInOpt;
	private double optVal;

then fill in the solve() method with