15 A Simple Permutation Model (examp-tsp)

Run LPL Code  ,  PDF Document

An interesting model class are the permutation problems (PERM). Many of them can be formulated in linear (MIP) or non-linear discrete models too, but are inefficient in solving so. In simple permutation problem we are looking for a permuation out of all permutations that minimizes an expression. A typical example is the TSP problem (see also model tsp): The cities to be visited are numbered from 1 to n. Then any permutation of these numbers can be interpreted as “round trip” – visiting all cities in the order of the sequence of these numbers. The goal is now to find a particular permutation that minimizes the total distance. (In the Casebook I, several formulations of the TSP problem are given, for example.) In practice such problems are often solved using (meta)-heuristics. There are many problems that fall into this class: quadratic assignment (QAP), flowshop scheduling, linear ordering problem (LOP), etc. As an example, the traveling salsman problem (TSP) is an used here.

Problem

Given a complete graph G = (V,E,c), with a set of nodes i,j V = {1,,n} and edge list E = V ×V and an edge length ci,j for each edge (i,j) E, find a Hamilton cycle of the graph, that is, a “round trip” in the graph that visits all nodes exactly once with minimal length (the sum of its edge lengths).

In a complete graph it is easy to get a Hamilton cycle: Every permutation of the nodes determines a Hamilton cycle. The difficulty arises when we ask for the shortest cycle. At the present time, we do not known a better method (in the worst case) to get the shortest one, then to enumerate all Hamilton cycles and pick the shortest, that means to check all (n - 1)! permutations and check each time its length. For a small graph with n = 30, we already have the gigantic number of permutations of 29! = 8.84 1030, far to big to be enumerated even by supercomputers in reasonable time. Nevertheless clever methods and mathematical models have been invented that can solve larger problems most of the time.

Modeling Steps

A mathematical formulation can be derived directly from the definition: Out of all permutation, find the one that minimizes the cycle.

  1. Let Π be the set of all permutations, and let π be a single permutation (π Π). For example, π = [1, 2, 3,,n] is a single permutation. Let πi be the i-th element in π.

  2. Then the distance of a roundtrip of the permutation π = [π12,n1] can be formulated as :

     n
∑
   cπi,πj  ,withj =  i  mod  n + 1
i=1

    or

    n- 1
∑
    cπi,πi+1 + cπn,π1
 i=1

    (j is the next element of i in the permutation π, and the next to the last is the first element in π). That is:

        {
j =    i + 1 :  i < n
          1  :  i = n
  3. In other words: Let π be a permutation π1π2π3πn-1πn. Then cπij with 1 i,j n is the cost from the node πi to node πj. The summation, therefore, expresses the costs of a round trip: cπ12+cπ23++cπn-1n+cπn1. Each possible round trip can be generated by a permutation. Minimizing this sum over all permutations means to look for the shortest round trip. Hence, the traveling salesman problem can be formulated as following:

               ∑n
min           cπi-1,πi + cπn,π1
           i=2
subjectto  π ∈ Π

    Note the syntax characteristic for this kind of models is, that (integer) variable are used as indexes: πi is a variable. For example, π2 = 7 means that 7 is at the second position (from left to right) in the permutation. And cπij is the distance value of ch,k where h = πi and k = πj. This notation extension allows the modeler to formulated the problem directly in the modeling language LPL:


Listing 13: The Main Model implemented in LPL [10]
model tsp "A Simple Permutation Model"; 
  set i,j          "the node set"; 
  parameter c{i,j} "distance matrix"; 
  alldiff variable z{i} [1..#i] "a permutation"; 
  minimize obj: sum{i} c[z[if(i=1,#i,i-1)],z[i]]; 
end

Further Comments

The LPL code is an one-to-one formulation of the model above. The variable definition alldiff defines a permutation of numbers starting with 1. The minimization function is also close to the mathematical notation: in LPL, the construct with if is used instead of the modulo operation. One could also use the modulo operation to specify the objective function as follows:

  minimize obj: sum{i} c[z[i],z[i%#i+1]];

This is a very compact formulation, but how is the problem solved? A model in LPL consisting of only a permutation variable and an objective function is identified by LPL as a special model type, called here as Simple Permutation Problem (PERM). These problems are sent to an special solver integrated in LPL which is based on an Tabu-Search metaheuristic method. A much more powerful solver is the commercial LocalSolver.

Solution

A random instance with 30 locations (nodes) is generated in the data model. So, n = 30 coordinates are generated for the nodes in a rectangle and calculate the distances as Euclidean distances:


Listing 14: The Data Model
  model data; 
    parameter n:=[30] "problem size"; 
    parameter X{i}; Y{i}; m:=Trunc(Sqrt(n));; 
    i:=1..n; 
    X{i}:=(i%m+1)*2+Trunc(Rnd(0,2)); 
    Y{i}:=(i/m+1)*2+Trunc(Rnd(0,2)); 
    c{i,j}:= Sqrt((X[j]-X[i])^2+(Y[j]-Y[i])^2); 
  end

With the problem size n = 30, the Tabu-Search method normally finds the optimal solution in a few seconds, which is 51.8052 in this case (see Figure 5).


PIC

Figure 5: The Optimal Solution of a 30 Location Problem