17.1 Summary of the permutation problems as implemented in LPL

There are various kinds of permutation problems, all are declared with an alldiff variable in LPL. The unique commercial solver (I know) that can solve this kind of problems is the LocalSolver.

  1. The variable is one-dimensional then we are looking for a simple permutation (the keyword variable can be omitted):

      alldiff variable x{i};

    Example problems are TSP, LOP (linear ordering problem), QAP, etc. If a single objective function is requested – without constraints (as in the TSP) then the small problems can be solved with the internal Tabu-Search solver of LPL.

  2. A variant of the one-dimensional permutation is the subset variant:

      alldiff variable x{i} 'notall';

    In this case we are looking only for a subset of the permutation. An example is the price collecting TSP, a round-trip where not all location are visited.

  3. The variable is 2-dimensional without any additional attribute then are looking for a partitioned permutation. The set i defines the permutation itself and the set k is the partitioning. The permutation is repeated over k.

       alldiff x{k,i};

    Example with defines a permutation of 4 items repeated over 3 sets.

          (           )
        2  3  4  1
xk,i = ( 1 3  2  4)
        4  1  2  3

    An example is the jobshop problem, where the job sequence (permutation) is repeated over all machines (see jobshop1).

  4. The variable is 2-dimensional with the additional attribute ’patition’ means that the unique permutation is partitioned over the set k.

       alldiff x{k,i} 'partition';

    This is the case for the exam-cvrp model: the set of locations defines a permutation, which is partitioned into subtours. Note that the order in the subsets (subtours) matters.

  5. The variable is 2-dimensional with the additional attribute ’set patition’ means that the unique permutation is partitioned over the set k, but the order of the items in the subsets does not matter.

       alldiff x{k,i} 'set partition';

    An example ist the bin-packing problem: the items to place into the bins define a permutation, which is partitioned into the bins, but the order within the bins does not matter.

  6. The variable is 2-dimensional with the additional attribute ’cover’ means that the unique permutation is distributed over the set k, the items in the permutation can be repeated in the different subsets.

       alldiff x{k,i} 'cover';

    A example is the Split Delivery Vehicle Routing (SDVRP) problem, the same customer (location) can be visited by more than one vehicle (can be in more then one subtour) (see sdvrp).