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?

Erwin Kalvelagen · Accepted Answer · 2018-01-02 07:58:18Z

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:

edited Jan 2, 2018 at 7:58

answered Jan 2, 2018 at 3:28

Erwin Kalvelagen

16.9k3 gold badges18 silver badges42 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

ORspecialist Over a year ago

(Deleted my own comment, so again): Thanks a lot for your help. I had the idea to introduce y(j) too but that was as far as I got. Your idea solves my problem. However, there is a small error in your model: Constraint zdef is defined for all j. But for j = 1, we have: z_1 >= y_1 - y_0. y_0 is not defined. I solved this problem by restricting zdef to all j but 1. Then I added another constraint z_1 >= y_1. If there is an assigment to 1, the transition from 0 to 1 has already happended (from an imaginary j = 0).

Erwin Kalvelagen Over a year ago

Sounds right. (The above GAMS code does automatically what you did by hand).

Collectives™ on Stack Overflow

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

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related