| Column |
|---|
This article is a tutorial on using callbacks, a group of advanced CPLEX features. The Traveling Salesmen Problem (TSP) will be used as a running example. CPLEX will be accessed through the Java Concert Technology interface. It will be assumed that the reader has completed all of the prerequisites given here. To navigate, use the menu on the left. Click on Getting Started. |
}
{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
* [http://www.seas.gwu.edu/~simhaweb/champalg/tsp/tsp.html]
* On Construction and Improvement Heuristics: [http://www2.research.att.com/~dsj/papers/TSPchapter.pdf]
TSP Problem Instances
* [http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/] |