Sorted and ordered sets

Shows the effect of the sorted property on simple sets, tuple sets, and sets used in piecewise linear functions.

Definitions

An ordered set is a set whose elements are arranged in the order in which they were added to the set. Note that this is how sets are created by default. For example:
```
{int} S1 = {3,2,5}; 
```
and
```
ordered {int} S1 = {3,2,5};
```
are equivalent.
A sorted set is a set in which elements are arranged in their natural, ascending (or descending) order. For strings, the natural order is the lexicographic order. The natural order also depends on the system locale. For example:
```
sorted {int} sortedS = {3,2,5};
```
and
```
ordered {int} orderedS = {2,3,5};
```
are equivalent, and iterating over sortedS or orderedS will have the same behavior.

To specify the descending order, you add the keyword reversed.

Simple sets

The following code sample enables you to see the difference between the union of ordered sets and the union of sorted sets.

{int} s1 = {3,5,1};
{int} s2 = {4,2};
{int} orderedS = s1 union s2;
sorted {int} sortedS = s1 union s2;
execute{
    writeln("ordered union = ", orderedS);
    writeln("sorted union = ", sortedS);
}

The statement

{int} orderedS = s1 union s2;

returns

ordered union =  {3 5 1 4 2}

while the statement

sorted {int} sortedS = s1 union s2;

returns

sorted union =  {1 2 3 4 5}

Sorted tuple sets

When a tuple set does not use keys, the entire tuple, except set and array fields, is taken into account for sorting. For tuple sets with keys, sorting takes place on all keys in their order of declaration. In other words, it is not possible to sort a tuple set on one (or more) given column(s) only.

The following code extract declares a team of people who are defined by their first name, last name, and nickname, then prints the list of team members first in the creation order, then in alphabetical order.

tuple person {
     string firstname;
     string lastname;
     string nickname;
}
tuple personKeys {
     key string firstname;
     key string lastname;
     string nickname;
}
{person} devTeam = {
<"David", "Atkinson", "Dave">,
<"David", "Doe", "Skinner">,
<"Gregory", "Simons", "Greg">, 
<"David", "Smith", "Lewis">,
<"Kevin", "Morgan", "Kev">,
<"Gregory", "McNamara ", "Mac">
};
sorted {personKeys} sortedDevTeam = {<i,j,k> | <i,j,k> in devTeam};
execute{
        writeln(devTeam);
        writeln(sortedDevTeam);
}

The person tuple uses no keys.

tuple person {
     string firstname;
     string lastname;
     string nickname;
}

The personKeys tuple uses keys for the first and last names, not for the nickname.

tuple personKeys {
     key string firstname;
     key string lastname;
     string nickname;
}

The data shows that the team includes three people whose first name is David, two people whose first name is Gregory, and one person whose first name is Kevin.

As a consequence, the statement

sorted {personKeys} sortedDevTeam = {<i,j,k> | <i,j,k> in devTeam};

lists the David tuples before the Gregory tuples, which themselves appear before the Kevin tuple. Within the David tuples, "David" "Doe" "Skinner" comes before "David" "Smith" "Lewis" because a second sorting also takes place on the second field with the key lastname. In contrast, since there is no person with the same first name and last name, no sort is ever done on the last field nickname.

The output of sortedDevTeam is displayed in the CPLEX Studio IDE as:

   {<"David" "Atkinson" "Dave"> <"David" "Doe" "Skinner">
    <"David" "Smith" "Lewis"> <"Gregory" "McNamara " "Mac">
    <"Gregory" "Simons" "Greg"> <"Kevin" "Morgan" "Kev">}

Sorted sets in piecewise linear functions

In piecewise linear functions, breakpoints must be strictly increasing. However, in most cases, the data supplied by a database or a .dat file is not sorted in an increasing numeric or lexicographic order. As a consequence, you have to add complex and verbose scripting statements to sort the data.

To avoid these extra code lines, the sorted property of sets enables you to sort data by specifying a single keyword, as shown in the following code extract. Writing piecewise linear functions becomes easier, as one code line is sufficient instead of several dozens.

tuple Cost{ 
    key int BreakPoint; 
    float Slope; 
} 
sorted {Cost} sS = { <1, 1.5>, <0, 2.5>, <3, 4.5>, <2, 4.5>}; 

float lastSlope = 3.5; 


dvar float+ x; 
minimize piecewise(t in sS) 
    {t.Slope -> t.BreakPoint; lastSlope} x;