Versions Compared

Key

  • This line was added.
  • This line was removed.
  • Formatting was changed.
Comment: Migration of unmigrated content due to installation of a new plugin
{
Wiki Markup
Composition Setup
Section
Column
width300px
Page Tree
rootTutorial
} {composition-setup} {section} {column:width=300px} {pagetree:root=Tutorial} {column} {column} h1. Solver Input The problem data is organized and passed to the solver in an instance of the class {{TspInstance<V,E>}}. Note the use of generics. Here {{V}} is the type of the objects that will correspond to vertices and {{E}} is the type of the objects that will correspond to edges. The point of generics is that our code will not really depend on what the types of our nodes and edges are. Lets take a quick look at the highlights of the public interface to this class. {code}
Column

Solver Input

The problem data is organized and passed to the solver in an instance of the class TspInstance<V,E>. Note the use of generics. Here V is the type of the objects that will correspond to vertices and E is the type of the objects that will correspond to edges. The point of generics is that our code will not really depend on what the types of our nodes and edges are. Lets take a quick look at the highlights of the public interface to this class.

Code Block

public UndirectedGraph<V, E> getGraph() {
	...
}
public Function<E, Integer> getEdgeWeights() {
	...
}
{code}

The

UndirectedGraph<V,E>

returned

by

{{

getGraph()

}}

is

from

the

JUNG

library.

You

can

view

the

complete

documentation

[

here

|http://jung.sourceforge.net/doc/api/edu/uci/ics/jung/graph/UndirectedGraph.html]

(

[

this

page

|http://jung.sourceforge.net/doc/api/edu/uci/ics/jung/graph/UndirectedSparseGraph.html]

might

be

more

helpful),

but

some

important

highlights

are

||Name||Return Type||Arguments||Description|| |addVertex|boolean|V vertex| Adds vertex to this graph. Fails if vertex is null or already in the graph.| |addEdge|boolean|E e, V v1, V v2| Adds edge e to this graph such that it connects vertex v1 to v2.| |findEdge|E|V v1, V v2| Returns an edge that connects vertex v1 and vertex v2. Returns null if either v2 is not connected to v1 or either v1 or v2 are not present in this graph.| |getIncidentEdges|Collection<E>|V vertex|Returns the collection of edges in this graph which are connected to vertex.| |getVertices|Collection<V>| |Returns a view of all vertices in this graph.| |getEdges|Collection<E>| |Returns a view of all edges in this graph.| The Function<E,Integer> will give the cost of any edge for our optimization. The interface is quite simple: ||Name||Return Type||Arguments||Description|| |apply|Integer|E edge|Returns the result of applying this function to edge.| h1. Solver Interface Open the file _

Name

Return Type

Arguments

Description

addVertex

boolean

V vertex

Adds vertex to this graph. Fails if vertex is null or already in the graph.

addEdge

boolean

E e, V v1, V v2

Adds edge e to this graph such that it connects vertex v1 to v2.

findEdge

E

V v1, V v2

Returns an edge that connects vertex v1 and vertex v2. Returns null if either v2 is not connected to v1 or either v1 or v2 are not present in this graph.

getIncidentEdges

Collection<E>

V vertex

Returns the collection of edges in this graph which are connected to vertex.

getVertices

Collection<V>

 

Returns a view of all vertices in this graph.

getEdges

Collection<E>

 

Returns a view of all edges in this graph.

The Function<E,Integer> will give the cost of any edge for our optimization. The interface is quite simple:

Name

Return Type

Arguments

Description

apply

Integer

E edge

Returns the result of applying this function to edge.

Solver Interface

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} For now, nothing in this class does much. Below, we summarize how all the parts _should_ work. The enum {{Option}} is a collection of flags that can be passed in to the solver indicating what special techniques the solver should use. We now briefly summarize what each option indicates: ||Option Name||Description|| |lazy|Add a LazyConstraintCallback to check potential integer solutions to ensure that the _cutset_ constraints are satisfied. Without this option, there is no guarantee that cutset constraints are checked.| |userCut|Add a UserCutCallback to check fractional solutions to ensure that the _cutset_ constraints are satisfied.| |randomizedUserCut|A variant of userCut where only a random subset of the _cutset_ constraints are checked. If flagged, userCut should not be flagged| |christofidesApprox|Use Christofides Algorithm to give an initial solution to CPLEX.| |christofidesHeuristic|Use a variant of Christofides Algorithm to generate integer solutions from fractional solutions.| |twoOpt|Use the Two-Opt local search heuristic to improve solutions generated by christofidesApprox, christofidesHeuristic, or incumbent, if any are selected.| |incumbent|Collect integer solutions found by CPLEX to have Two-Opt applied. Requires that twoOpt is flagged.| Next, the constructors for class {{TspIpSolver}}: ||Arguments||Description|| |TspInstance<V,E> tspInstance, EnumSet<Option> options| Creates an instance of the solver according to options| |TspInstance<V,E> tspInstance|Creates an instance of the solver with the default options \{lazy, userCut, christofidesApprox, christofidesHeuristic\}| Finally, the methods of the class should behave as follows: ||Name||Return Type||Arguments||Description|| |solve|void| |Runs CPLEX to solve the TSP with problem data given by TspInstance. Do not call more than once.| |getEdgesInOpt|ImmutableSet<E>| |Returns the subset of the edges of the TspInstance that are in the optimal solution. Do not call until solve() has finished. Behavior is undefined otherwise.| |getOptVal|double| |Returns the value of the optimal solution. Do not call until solve() has finished. Behavior is undefined otherwise.| Now that we understand the problem, we can begin implementing a solution! {column} {section}

Cloak
visibletrue
idTspIpSolverStart

For now, nothing in this class does much. Below, we summarize how all the parts should work. The enum Option is a collection of flags that can be passed in to the solver indicating what special techniques the solver should use. We now briefly summarize what each option indicates:

Option Name

Description

lazy

Add a LazyConstraintCallback to check potential integer solutions to ensure that the cutset constraints are satisfied. Without this option, there is no guarantee that cutset constraints are checked.

userCut

Add a UserCutCallback to check fractional solutions to ensure that the cutset constraints are satisfied.

randomizedUserCut

A variant of userCut where only a random subset of the cutset constraints are checked. If flagged, userCut should not be flagged

christofidesApprox

Use Christofides Algorithm to give an initial solution to CPLEX.

christofidesHeuristic

Use a variant of Christofides Algorithm to generate integer solutions from fractional solutions.

twoOpt

Use the Two-Opt local search heuristic to improve solutions generated by christofidesApprox, christofidesHeuristic, or incumbent, if any are selected.

incumbent

Collect integer solutions found by CPLEX to have Two-Opt applied. Requires that twoOpt is flagged.

Next, the constructors for class TspIpSolver:

Arguments

Description

TspInstance<V,E> tspInstance, EnumSet<Option> options

Creates an instance of the solver according to options

TspInstance<V,E> tspInstance

Creates an instance of the solver with the default options {lazy, userCut, christofidesApprox, christofidesHeuristic}

Finally, the methods of the class should behave as follows:

Name

Return Type

Arguments

Description

solve

void

 

Runs CPLEX to solve the TSP with problem data given by TspInstance. Do not call more than once.

getEdgesInOpt

ImmutableSet<E>

 

Returns the subset of the edges of the TspInstance that are in the optimal solution. Do not call until solve() has finished. Behavior is undefined otherwise.

getOptVal

double

 

Returns the value of the optimal solution. Do not call until solve() has finished. Behavior is undefined otherwise.

Now that we understand the problem, we can begin implementing a solution!