## 5.248. max_size_set_of_consecutive_var

Origin

N. Beldiceanu

Constraint

$\mathrm{𝚖𝚊𝚡}_\mathrm{𝚜𝚒𝚣𝚎}_\mathrm{𝚜𝚎𝚝}_\mathrm{𝚘𝚏}_\mathrm{𝚌𝚘𝚗𝚜𝚎𝚌𝚞𝚝𝚒𝚟𝚎}_\mathrm{𝚟𝚊𝚛}\left(\mathrm{𝙼𝙰𝚇},\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right)$

Arguments
 $\mathrm{𝙼𝙰𝚇}$ $\mathrm{𝚍𝚟𝚊𝚛}$ $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚛}-\mathrm{𝚍𝚟𝚊𝚛}\right)$
Restrictions
 $\mathrm{𝙼𝙰𝚇}\ge 1$ $\mathrm{𝙼𝙰𝚇}\le |\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂},\mathrm{𝚟𝚊𝚛}\right)$
Purpose

$\mathrm{𝙼𝙰𝚇}$ is the size of the largest set of variables of the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ that all take their value in a set of consecutive values.

Example
 $\left(6,〈3,1,3,7,4,1,2,8,7,6〉\right)$ $\left(2,〈2,6,7,3,0,9〉\right)$

In the first example, the two sets $\left\{3,1,3,4,1,2\right\}$ and $\left\{7,8,7,6\right\}$ take respectively their values in the two following sets of consecutive values $\left\{1,2,3,4\right\}$ and $\left\{6,7,8\right\}$. Consequently, the corresponding $\mathrm{𝚖𝚊𝚡}_\mathrm{𝚜𝚒𝚣𝚎}_\mathrm{𝚜𝚎𝚝}_\mathrm{𝚘𝚏}_\mathrm{𝚌𝚘𝚗𝚜𝚎𝚌𝚞𝚝𝚒𝚟𝚎}_\mathrm{𝚟𝚊𝚛}$ constraint holds since the cardinality of the largest set of variables is 6.

Typical
 $\mathrm{𝙼𝙰𝚇}<|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|$ $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|>0$ $\mathrm{𝚛𝚊𝚗𝚐𝚎}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}\right)>1$
Symmetries
• Items of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ are permutable.

• All occurrences of two distinct values of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}$ can be swapped.

• One and the same constant can be added to the $\mathrm{𝚟𝚊𝚛}$ attribute of all items of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$.

Arg. properties

Functional dependency: $\mathrm{𝙼𝙰𝚇}$ determined by $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$.

Counting
 Length ($n$) 2 3 4 5 6 7 8 Solutions 9 64 625 7776 117649 2097152 43046721

Number of solutions for $\mathrm{𝚖𝚊𝚡}_\mathrm{𝚜𝚒𝚣𝚎}_\mathrm{𝚜𝚎𝚝}_\mathrm{𝚘𝚏}_\mathrm{𝚌𝚘𝚗𝚜𝚎𝚌𝚞𝚝𝚒𝚟𝚎}_\mathrm{𝚟𝚊𝚛}$: domains $0..n$  Length ($n$)2345678
Total9646257776117649209715243046721
 Parameter value

12------
2730168720522027720249480
3-342403080355804267206059760
4--21722603603068355012672940
5---17162466047716210592848
6----161593056347044632
7-----1763664239424
8------2187637

Solution count for $\mathrm{𝚖𝚊𝚡}_\mathrm{𝚜𝚒𝚣𝚎}_\mathrm{𝚜𝚎𝚝}_\mathrm{𝚘𝚏}_\mathrm{𝚌𝚘𝚗𝚜𝚎𝚌𝚞𝚝𝚒𝚟𝚎}_\mathrm{𝚟𝚊𝚛}$: domains $0..n$  Keywords
Arc input(s)

$\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$

Arc generator
$\mathrm{𝐶𝐿𝐼𝑄𝑈𝐸}$$↦\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{1},\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{2}\right)$

Arc arity
Arc constraint(s)
$\mathrm{𝚊𝚋𝚜}\left(\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{1}.\mathrm{𝚟𝚊𝚛}-\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{2}.\mathrm{𝚟𝚊𝚛}\right)\le 1$
Graph property(ies)
$\mathrm{𝐌𝐀𝐗}_\mathrm{𝐍𝐒𝐂𝐂}$$=\mathrm{𝙼𝙰𝚇}$

Graph model

Since the arc constraint is symmetric each strongly connected component of the final graph corresponds exactly to one connected component of the final graph.

Parts (A) and (B) of Figure 5.248.1 respectively show the initial and final graph associated with the first example of the Example slot. Since we use the $\mathrm{𝐌𝐀𝐗}_\mathrm{𝐍𝐒𝐂𝐂}$ graph property, we show the largest strongly connected component of the final graph.

##### Figure 5.248.1. Initial and final graph of the $\mathrm{𝚖𝚊𝚡}_\mathrm{𝚜𝚒𝚣𝚎}_\mathrm{𝚜𝚎𝚝}_\mathrm{𝚘𝚏}_\mathrm{𝚌𝚘𝚗𝚜𝚎𝚌𝚞𝚝𝚒𝚟𝚎}_\mathrm{𝚟𝚊𝚛}$ constraint (a) (b)