Combinatorial optimization: assignment (matching) with "consecutive" assignments

Question

I am trying to model an optimization problem in IBM ILOG CPLEX. Basically it is the classic assignment problem. I have to Sets A = {a_1,...,a_n} und B = {b_1,...b_m} and n < m. Every element of A has to be assigned to one element of B. To each element of B, at maximum one element of A can be assigned. From n < m, it follows that some elements of B remain free (nothing is assigned to them).

Modelling this is extremely easy. However, I have another constraint and I can't find a way to model that. The constraint is: all elements from B to which there is an assignment, have to be connected. The assignment has to be consecutive / sequential / however you want to call it.

Example: A = {a_1,a_2,a_3}, B = {b_1,b_2,b_3_b_4,b_5}

If some element from A is assigned to b_1, then b_2 and b_3 have assignments too.

If some element from A is assigned to b_3, b_4 and b_5 have assignments OR b_2 and b_4 have assignments OR b_1 and and b_2 have assignments.

In other words: If x means something is assigned to an element from B, these configurations are allowed: (xxx - -), (- xxx -), (- - xxx).

I use a decision variable x_ij with i in A and j in B. x_ij = 1 iff i is assigned to j.

Anyone got an idea how to model this restriction?

Answer 1

Let y(j) be 1 if there is an assignment to j and 0 otherwise:

y(j) = sum(i,x(i,j)) 

(This replaces the original assignment constraint sum(i,x(i,j)) ≤ 1)

Now, limit the number of times we have the pattern [0,1] in the y(j)'s as follows:

z(j) ≥ y(j)-y(j-1)
sum(j, z(j)) ≤ 1

This will allow only one transition from 0 to 1 in the y's. All variables y and z should be binary (or continuous between 0 and 1).

Output for a small data set. First the pure assignment problem:

----     30 PARAMETER c  cost coefficients

            j1          j2          j3          j4          j5          j6          j7          j8          j9         j10

i1       0.661       0.756       0.627       0.284       0.086       0.103       0.641       0.545       0.032       0.792
i2       0.073       0.176       0.526       0.750       0.178       0.034       0.585       0.621       0.389       0.359
i3       0.243       0.246       0.131       0.933       0.380       0.783       0.300       0.125       0.749       0.069
i4       0.202       0.005       0.270       0.500       0.151       0.174       0.331       0.317       0.322       0.964
i5       0.994       0.370       0.373       0.772       0.397       0.913       0.120       0.735       0.055       0.576


----     30 VARIABLE x.L  assignment variables

            j2          j5          j6          j9         j10

i1                       1
i2                                   1
i3                                                           1
i4           1
i5                                               1

(zero values are not shown).

After adding these y and z variables and constraints, we see:

----     54 VARIABLE x.L  assignment variables

            j5          j6          j7          j8          j9

i1                                                           1
i2                       1
i3                                               1
i4           1
i5                                   1


----     54 VARIABLE y.L  destination is used

j5 1,    j6 1,    j7 1,    j8 1,    j9 1


----     54 VARIABLE z.L  0-1 transition

j5 1

The complete model for this output was: