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