Tuesday, July 27, 2021

A variant of an assignment problem

 In one [1], the following problem is sketched:

  • We have different types of workers. In the data set below, I call them type-A and type-B workers. 
  • We need to assign workers to jobs.
  • We have more workers than jobs, so we can execute all jobs. 
  • This is a standard assignment problem: \[\begin{align} \min &\sum_{w,j} \color{darkblue}c_{w,j} \color{darkred}x_{w,j}\\ & \sum_j \color{darkred}x_{w,j} \le 1 &&\forall w \\ & \sum_w \color{darkred}x_{w,j} = 1 && \forall j \\ & \color{darkred}x_{w,j} \in [0,1] \end{align}\]
  • The complication is that we can form teams of two workers, one of type A and one of type B. Such a team can work faster and execute the job in less time.
  • How to handle this?

I don't know how to handle this within an assignment problem, but stating this as a MIP allows us to make some progress. Allowing two persons to work on a job is easy. Just replace the second constraint by \[1 \le \sum_w \color{darkred}x_{w,j} \le 2\] Unfortunately this ignores that we need one worker of each type in a team. Also, this makes it difficult to impose a cost for each specific team.


As an alternative one could explicitly use teams in the model. Here is my data set with random costs:


----     13 SET i  workers+teams

a1     ,    a2     ,    a3     ,    a4     ,    a5     ,    a6     ,    a7     ,    a8     ,    a9     ,    a10    
b1     ,    b2     ,    b3     ,    b4     ,    b5     ,    b6     ,    b7     ,    b8     ,    b9     ,    b10    
team1  ,    team2  ,    team3  ,    team4  ,    team5  ,    team6  ,    team7  ,    team8  ,    team9  ,    team10 
team11 ,    team12 ,    team13 ,    team14 ,    team15 ,    team16 ,    team17 ,    team18 ,    team19 ,    team20 
team21 ,    team22 ,    team23 ,    team24 ,    team25 ,    team26 ,    team27 ,    team28 ,    team29 ,    team30 
team31 ,    team32 ,    team33 ,    team34 ,    team35 ,    team36 ,    team37 ,    team38 ,    team39 ,    team40 
team41 ,    team42 ,    team43 ,    team44 ,    team45 ,    team46 ,    team47 ,    team48 ,    team49 ,    team50 
team51 ,    team52 ,    team53 ,    team54 ,    team55 ,    team56 ,    team57 ,    team58 ,    team59 ,    team60 
team61 ,    team62 ,    team63 ,    team64 ,    team65 ,    team66 ,    team67 ,    team68 ,    team69 ,    team70 
team71 ,    team72 ,    team73 ,    team74 ,    team75 ,    team76 ,    team77 ,    team78 ,    team79 ,    team80 
team81 ,    team82 ,    team83 ,    team84 ,    team85 ,    team86 ,    team87 ,    team88 ,    team89 ,    team90 
team91 ,    team92 ,    team93 ,    team94 ,    team95 ,    team96 ,    team97 ,    team98 ,    team99 ,    team100


----     13 SET w  workers

a1 ,    a2 ,    a3 ,    a4 ,    a5 ,    a6 ,    a7 ,    a8 ,    a9 ,    a10,    b1 ,    b2 ,    b3 ,    b4 ,    b5 
b6 ,    b7 ,    b8 ,    b9 ,    b10


----     13 SET a  type-A workers

a1 ,    a2 ,    a3 ,    a4 ,    a5 ,    a6 ,    a7 ,    a8 ,    a9 ,    a10


----     13 SET b  type-B workers

b1 ,    b2 ,    b3 ,    b4 ,    b5 ,    b6 ,    b7 ,    b8 ,    b9 ,    b10


----     13 SET t  teams

team1  ,    team2  ,    team3  ,    team4  ,    team5  ,    team6  ,    team7  ,    team8  ,    team9  ,    team10 
team11 ,    team12 ,    team13 ,    team14 ,    team15 ,    team16 ,    team17 ,    team18 ,    team19 ,    team20 
team21 ,    team22 ,    team23 ,    team24 ,    team25 ,    team26 ,    team27 ,    team28 ,    team29 ,    team30 
team31 ,    team32 ,    team33 ,    team34 ,    team35 ,    team36 ,    team37 ,    team38 ,    team39 ,    team40 
team41 ,    team42 ,    team43 ,    team44 ,    team45 ,    team46 ,    team47 ,    team48 ,    team49 ,    team50 
team51 ,    team52 ,    team53 ,    team54 ,    team55 ,    team56 ,    team57 ,    team58 ,    team59 ,    team60 
team61 ,    team62 ,    team63 ,    team64 ,    team65 ,    team66 ,    team67 ,    team68 ,    team69 ,    team70 
team71 ,    team72 ,    team73 ,    team74 ,    team75 ,    team76 ,    team77 ,    team78 ,    team79 ,    team80 
team81 ,    team82 ,    team83 ,    team84 ,    team85 ,    team86 ,    team87 ,    team88 ,    team89 ,    team90 
team91 ,    team92 ,    team93 ,    team94 ,    team95 ,    team96 ,    team97 ,    team98 ,    team99 ,    team100


----     13 SET j  jobs

job1 ,    job2 ,    job3 ,    job4 ,    job5 ,    job6 ,    job7 ,    job8 ,    job9 ,    job10,    job11,    job12
job13,    job14,    job15


----     23 SET team  composition of teams

team1  .a1 ,    team1  .b1 ,    team2  .a1 ,    team2  .b2 ,    team3  .a1 ,    team3  .b3 ,    team4  .a1 
team4  .b4 ,    team5  .a1 ,    team5  .b5 ,    team6  .a1 ,    team6  .b6 ,    team7  .a1 ,    team7  .b7 
team8  .a1 ,    team8  .b8 ,    team9  .a1 ,    team9  .b9 ,    team10 .a1 ,    team10 .b10,    team11 .a2 
team11 .b1 ,    team12 .a2 ,    team12 .b2 ,    team13 .a2 ,    team13 .b3 ,    team14 .a2 ,    team14 .b4 
team15 .a2 ,    team15 .b5 ,    team16 .a2 ,    team16 .b6 ,    team17 .a2 ,    team17 .b7 ,    team18 .a2 
team18 .b8 ,    team19 .a2 ,    team19 .b9 ,    team20 .a2 ,    team20 .b10,    team21 .a3 ,    team21 .b1 
team22 .a3 ,    team22 .b2 ,    team23 .a3 ,    team23 .b3 ,    team24 .a3 ,    team24 .b4 ,    team25 .a3 
team25 .b5 ,    team26 .a3 ,    team26 .b6 ,    team27 .a3 ,    team27 .b7 ,    team28 .a3 ,    team28 .b8 
team29 .a3 ,    team29 .b9 ,    team30 .a3 ,    team30 .b10,    team31 .a4 ,    team31 .b1 ,    team32 .a4 
team32 .b2 ,    team33 .a4 ,    team33 .b3 ,    team34 .a4 ,    team34 .b4 ,    team35 .a4 ,    team35 .b5 
team36 .a4 ,    team36 .b6 ,    team37 .a4 ,    team37 .b7 ,    team38 .a4 ,    team38 .b8 ,    team39 .a4 
team39 .b9 ,    team40 .a4 ,    team40 .b10,    team41 .a5 ,    team41 .b1 ,    team42 .a5 ,    team42 .b2 
team43 .a5 ,    team43 .b3 ,    team44 .a5 ,    team44 .b4 ,    team45 .a5 ,    team45 .b5 ,    team46 .a5 
team46 .b6 ,    team47 .a5 ,    team47 .b7 ,    team48 .a5 ,    team48 .b8 ,    team49 .a5 ,    team49 .b9 
team50 .a5 ,    team50 .b10,    team51 .a6 ,    team51 .b1 ,    team52 .a6 ,    team52 .b2 ,    team53 .a6 
team53 .b3 ,    team54 .a6 ,    team54 .b4 ,    team55 .a6 ,    team55 .b5 ,    team56 .a6 ,    team56 .b6 
team57 .a6 ,    team57 .b7 ,    team58 .a6 ,    team58 .b8 ,    team59 .a6 ,    team59 .b9 ,    team60 .a6 
team60 .b10,    team61 .a7 ,    team61 .b1 ,    team62 .a7 ,    team62 .b2 ,    team63 .a7 ,    team63 .b3 
team64 .a7 ,    team64 .b4 ,    team65 .a7 ,    team65 .b5 ,    team66 .a7 ,    team66 .b6 ,    team67 .a7 
team67 .b7 ,    team68 .a7 ,    team68 .b8 ,    team69 .a7 ,    team69 .b9 ,    team70 .a7 ,    team70 .b10
team71 .a8 ,    team71 .b1 ,    team72 .a8 ,    team72 .b2 ,    team73 .a8 ,    team73 .b3 ,    team74 .a8 
team74 .b4 ,    team75 .a8 ,    team75 .b5 ,    team76 .a8 ,    team76 .b6 ,    team77 .a8 ,    team77 .b7 
team78 .a8 ,    team78 .b8 ,    team79 .a8 ,    team79 .b9 ,    team80 .a8 ,    team80 .b10,    team81 .a9 
team81 .b1 ,    team82 .a9 ,    team82 .b2 ,    team83 .a9 ,    team83 .b3 ,    team84 .a9 ,    team84 .b4 
team85 .a9 ,    team85 .b5 ,    team86 .a9 ,    team86 .b6 ,    team87 .a9 ,    team87 .b7 ,    team88 .a9 
team88 .b8 ,    team89 .a9 ,    team89 .b9 ,    team90 .a9 ,    team90 .b10,    team91 .a10,    team91 .b1 
team92 .a10,    team92 .b2 ,    team93 .a10,    team93 .b3 ,    team94 .a10,    team94 .b4 ,    team95 .a10
team95 .b5 ,    team96 .a10,    team96 .b6 ,    team97 .a10,    team97 .b7 ,    team98 .a10,    team98 .b8 
team99 .a10,    team99 .b9 ,    team100.a10,    team100.b10


----     28 PARAMETER c  cost coefficients

               job1        job2        job3        job4        job5        job6        job7        job8        job9

a1           17.175      84.327      55.038      30.114      29.221      22.405      34.983      85.627       6.711
a2           63.972      15.952      25.008      66.893      43.536      35.970      35.144      13.149      15.010
a3           11.049      50.238      16.017      87.246      26.511      28.581      59.396      72.272      62.825
a4           18.210      64.573      56.075      76.996      29.781      66.111      75.582      62.745      28.386
a5            7.277      17.566      52.563      75.021      17.812       3.414      58.513      62.123      38.936
a6           78.340      30.003      12.548      74.887       6.923      20.202       0.507      26.961      49.985
a7           99.360      36.990      37.289      77.198      39.668      91.310      11.958      73.548       5.542
a8           22.575      39.612      27.601      15.237      93.632      42.266      13.466      38.606      37.463
a9           10.169      38.389      32.409      19.213      11.237      59.656      51.145       4.507      78.310
a10          50.659      15.925      65.689      52.388      12.440      98.672      22.812      67.565      77.678
b1           73.497       8.544      15.035      43.419      18.694      69.269      76.297      15.481      38.938
b2            8.712      54.040      12.686      73.400      11.323      48.835      79.560      49.205      53.356
b3            2.463      17.782       6.132       1.664      83.565      60.166       2.702      19.609      95.071
b4           39.334      80.546      54.099      39.072      55.782      93.276      34.877       0.829      94.884
b5           58.032      16.642      64.336      34.431      91.233      90.006       1.626      36.863      66.438
b6           49.662       4.493      77.370      53.297      74.677      72.005      63.160      11.492      97.116
b7           79.070      61.022       5.431      48.518       5.255      69.858      19.478      22.603      81.364
b8           81.953      86.041      21.269      45.679       3.836      32.300      43.988      31.533      13.477
b9            6.441      41.460      34.161      46.829      64.267      64.358      33.761      10.082      90.583
b10          40.419      11.167      75.113      80.340       2.366      48.088      27.859      90.161       1.759
team1        50.421      83.126      60.214       8.225      57.776      59.318      68.377      15.877      33.178
team2        57.624      71.983      68.373       1.985      83.980      71.005      15.551      61.071      66.155
team3         1.252       1.017      95.203      97.668      96.632      85.628      14.161       4.973      55.303
team4        34.968      11.734      58.598      44.553      41.232      91.451      21.378      22.417      54.233
team5        31.014       4.020      82.117      23.096      41.003      30.258      44.492      71.600      59.315
team6        68.639      67.463      33.213      75.994      17.678      68.248      67.299      83.121      51.517
team7         8.469      57.216       2.206      74.204      90.510      56.082      47.283      71.756      51.301
team8        96.552      95.789      89.923      32.755      45.710      59.618      87.862      17.067      63.360
team9        33.626      58.864      57.439      54.342      57.816      97.722      32.147      76.297      96.251
team10       27.016      75.848      61.743      29.100      74.070       0.776      86.651       1.514      42.828
team11       93.347      46.928      21.361      51.078      36.572      93.540       6.801      50.387      39.241
team12       54.748       5.827      37.772      97.407      37.982      15.629      47.226      39.700      20.552
team13        7.212      76.065      29.015      24.495      43.598      36.881      55.342       7.466      90.944
team14       86.568      97.532      57.238      31.397      45.503      37.102      41.985       8.530      81.454
team15       44.431      69.547      67.669      57.154      17.352      60.435      58.599      72.778      24.623
team16       99.602      46.449      53.049      19.038      19.906      64.490      79.908      58.636      97.157
team17        0.309      61.802       0.666      40.558      65.629      61.550      26.341       7.045       4.597
team18       35.535      33.787      48.649      25.937      89.119      84.933      63.452      98.647      75.792
team19       60.358      97.705      55.407      93.504      41.320      80.645       0.078      45.526      41.917
team20       18.987      42.806      16.651      88.626      67.654      86.334       9.276      99.648      61.681
team21       44.199      65.906      48.445      31.819      91.404      18.423      87.211      45.610      45.892
team22       82.294      48.052      91.376      92.928      10.811      35.060      85.998      34.050      21.309
team23       29.676      11.550      39.978      91.176      25.155      10.298      14.633      38.630       4.641
team24       97.215      24.343      36.197      63.034      24.285      10.106      40.593      47.906      14.495
team25       72.042      87.195      29.952      75.390      84.376      46.823      65.493      37.805      35.887
team26       80.649      73.261      92.001      33.164      20.978       4.715      88.304       9.281      83.691
team27       57.996      96.211      51.419      59.030      56.746       2.990      96.890      59.375       5.962
team28       99.295       5.533      61.908      80.444      29.659      95.892      69.475      63.141      61.598
team29       35.582      76.108      13.636      71.663      96.370      44.192      26.448      44.418      39.670
team30        6.910      93.857      84.397      95.044      57.938       3.522      40.743       5.743      53.197
team31       18.614      50.068      93.882      68.157      18.523      87.288      16.501      43.083      77.173
team32       74.914      64.760      74.838      52.317      68.611      69.107      86.565      79.576      21.755
team33       32.482      39.012      29.932      21.896      82.172      15.266      95.055       3.192      73.446
team34       97.108       9.633      47.892      72.217      43.320      15.818      10.066      80.551      39.869
team35       90.918      72.309      16.635      32.755      58.135      57.754      62.758       2.673      12.942
team36       33.861      22.424      90.003      82.938      31.622      95.222      25.669      62.612      97.126
team37       59.518      60.638      63.365      95.824       8.226      12.537      60.522      74.148      84.752
team38       34.621      40.959      93.986      60.293      89.954      28.473      22.224      57.484      50.950
team39       75.582      47.491       7.619       9.750      32.967      20.061       9.075      44.877      46.281
team40       70.315      87.492      55.513      25.563      25.918      35.512      13.688      80.707      32.598
team41       40.712      16.162      86.175      37.771      88.861      26.998      77.739      42.279      42.985
team42       96.851      27.002      31.815      88.338      58.622      38.209      97.298      67.083      95.115
team43       11.834      96.538      84.355      72.133      96.444      36.457      76.831      33.248      54.208
team44       69.156       5.474      24.020      88.275      10.058      67.836      10.138       4.281      75.345
team45       18.595      79.016      86.452      74.793      38.949      79.504      62.098      76.137      58.026
team46       12.291      61.786      53.395      14.408      39.228       1.476      87.077      24.552      80.318
team47        3.952      91.293      54.250      22.099      92.557      79.278      73.938      67.774      50.119
team48       84.202      65.738      11.651      27.425       8.316      50.531      23.268      79.857      98.805
team49       34.050      25.641      99.307      24.779      12.148      94.371      25.320      36.335      39.410
team50       91.418      19.241      14.414      76.037      33.058       0.019      54.343      53.506      86.860
team51       34.192      86.537      46.085      42.106      72.583      66.959       9.290      52.659      89.543
team52       51.518       2.499      44.818      50.129      68.119      79.904      87.295      28.298      91.049
team53        1.814      46.041      62.397      71.636      33.516       1.288      35.621      36.817      91.687
team54       91.703       3.812      30.238       7.003      46.649      56.070      46.509      54.733      17.797
team55       70.710       8.983      40.810      13.683      73.463      59.277      35.746       7.368      63.081
team56       64.880      12.222      76.004      63.311      82.901      90.882      85.856      96.624       3.575
team57       28.704      68.662      27.527      39.028       9.470      21.756      84.353      84.226      88.356
team58       57.295      33.574      39.984      52.038      21.880      70.111      35.389      30.443      95.367
team59       13.348      76.050       9.416      44.537      79.383      46.261      32.450      35.389      17.424
team60       60.266      29.786      50.115      48.842      78.452      62.111      60.558      80.206      65.321
team61       48.293      25.076      48.480      80.988      51.944      97.473      10.245      46.995       1.720
team62       55.262      88.315      57.951      78.826      11.309      65.844       6.641      89.806      88.661
team63       83.952      92.298      23.661      44.994      27.202       5.529      96.659       1.775       1.772
team64       40.231      90.447      44.817      34.879      50.561      39.529       5.694      71.671      17.966
team65       18.090      63.984      14.545      66.332      13.193      70.742      57.057       3.341      28.519
team66       89.692      86.518      54.621      32.159      96.335      91.053       8.301      63.871       7.836
team67       70.988      39.985      21.743      79.525      72.178      78.875      42.399      88.496      65.532
team68       28.220      39.850      65.030      28.160      73.649      66.889      48.940      35.909      67.851
team69       15.372      12.775      86.772      76.504      57.896      78.856      89.680      43.896      58.892
team70        9.648      25.858      13.713      29.323      59.717      68.814      54.855      16.832      81.477
team71       19.761      71.657      31.438      62.191      47.632      79.540      52.101      47.061      61.375
team72       70.554      57.888      27.608       3.980      26.706      23.417      69.728      96.838      67.951
team73       25.746      47.557      87.610      40.229       8.167      70.932      85.333      29.275      27.718
team74       12.422      19.260      68.593      79.726      65.104      46.900      52.869      51.100      40.703
team75       21.644      73.245      57.380      17.480      22.512      98.857       8.098      71.535      71.020
team76       63.699       0.915      41.984      51.118      77.637      69.816      58.570      56.036      62.796
team77       25.208      80.883      81.776      17.895      87.611       4.852      36.311      68.449      71.587
team78        7.306      77.867      62.608      17.979      70.584      44.212       6.017      52.787      41.516
team79       90.690      37.166      86.201      41.745      28.674      18.114      61.104      74.749      84.652
team80        5.566      19.271       6.217       4.931       2.812      59.614      52.066      45.392      93.225
team81       10.011      12.271      56.491      66.269      86.984      72.970      70.643      51.238      66.539
team82       51.279      36.202      94.217      85.481      82.929       5.236      92.337       6.478      48.276
team83       30.503      56.251      38.438      16.202      68.007      28.049       4.744      21.577      75.036
team84       87.864      27.182      14.756      18.279       1.906      64.281      73.222      56.717      57.004
team85       73.607      79.475       4.997      40.372       4.539      37.561       8.753      26.090      45.468
team86        2.424      32.723      54.412       2.884       1.616      42.871      69.679      29.672      70.529
team87       41.065      31.774      50.934      23.799      26.394      69.386       9.290      13.320      10.917
team88       65.125      28.141      11.859      29.774      48.321      25.058      28.436      81.414      80.148
team89       72.420      84.144      67.924      74.009      52.949      38.862      29.610      93.236      81.799
team90       40.964       5.398      56.449      13.812      42.358      54.718      37.845      56.767      72.899
team91       29.231      21.862      51.143      69.911      56.027      33.616      51.876      24.922      41.096
team92       66.764       7.579      41.141      51.840       0.690      18.665      18.361      54.365      55.272
team93       36.443      60.224      83.947      68.479      88.239      61.747       9.943      38.910       2.983
team94        6.396      12.787      28.332      91.485      84.993      21.966      26.917      46.702      51.649
team95       29.600      62.579      93.929      79.012      34.292      58.557      60.675      25.588       3.830
team96       96.945      57.303       8.341      34.519      89.812      54.275      40.901      32.755      98.966
team97        5.720      76.327      87.034      78.061      17.198      69.229      63.387      61.913       0.038
team98       21.277       8.252      28.341      97.284      47.146      22.196      56.537      89.966      15.708
team99       77.385      12.015      78.861      79.375      83.146      11.379       3.413      72.925      88.689
team100      11.050      20.276      21.448      27.928      15.073      76.671      91.574      94.498       7.094

      +       job10       job11       job12       job13       job14       job15

a1           50.021      99.812      57.873      99.113      76.225      13.069
a2           58.911      83.089      23.082      66.573      77.586      30.366
a3           46.380      41.331      11.770      31.421       4.655      33.855
a4            8.642      10.251      64.125      54.531       3.152      79.236
a5           35.871      24.303      24.642      13.050      93.345      37.994
a6           15.129      17.417      33.064      31.691      32.209      96.398
a7           57.630       5.141       0.601      40.123      51.988      62.888
a8           26.848      94.837      18.894      29.751       7.455      40.135
a9           94.575      59.646      60.734      36.251      59.407      67.985
a10          93.245      20.124      29.714      19.723      24.635      64.648
b1           69.543      84.581      61.272      97.597       2.689      18.745
b2            1.062      54.387      45.113      97.533      18.385      16.353
b3           33.554      59.426      25.919      64.063      15.525      46.002
b4           57.192      33.363      98.375      76.646      11.009      99.480
b5           59.338       3.457      84.182      93.208      50.796      29.960
b6           70.674      98.627      85.482      62.144      70.131      70.089
b7           99.173      75.067      71.834       0.059      26.386      82.382
b8           81.096      41.679      14.178      46.553      28.299      89.568
b9           21.735      91.887      45.175       8.993      37.420      41.499
b10          68.104      95.091      90.018      89.880      87.446      39.100
team1        31.586      51.993      36.379      16.776      68.309      50.539
team2        19.437      36.352      62.390      73.139      41.397      15.749
team3        18.403      99.417      80.909      30.621       8.740      43.050
team4        63.106      32.743      14.878      92.915      25.103       6.259
team5        13.119      16.125      31.563      57.206      26.872       3.639
team6        28.303      55.542      41.399       7.341      80.601      33.272
team7        88.708      77.152      14.012      26.452      68.256      44.980
team8        77.159      56.945       2.768      81.099      27.893      43.335
team9        94.899      25.589      32.495      21.479      17.396      73.125
team10       35.865      70.487      41.587      54.980      34.504      69.958
team11       20.485      52.955      58.909      34.580      25.288      54.766
team12       62.734       0.355      50.395       0.223      52.137      83.612
team13        4.870      82.036      79.295      65.954      39.177      41.315
team14       50.920      73.442      82.438      41.453      92.443      39.415
team15       14.208      89.119      44.276      11.432      90.362      33.385
team16       49.109      37.254      82.717      82.087       3.134      92.520
team17       16.027      45.248      16.887      57.160      85.871       3.587
team18       50.788      76.777      83.213      58.394      57.506      55.671
team19        1.566       8.198      59.881      55.518      61.800      88.509
team20        0.077      60.894      17.371      31.119      72.888       8.475
team21       12.410      10.380      23.489      34.016      87.307      84.479
team22       92.636      36.073      87.599      14.814      45.598      26.825
team23        2.638      15.400       7.271      82.864      39.977      41.717
team24       50.969      88.528       5.548      50.740      76.411      97.900
team25       25.448      25.548      45.062      94.485      33.553       4.849
team26       46.381       0.017      15.658      70.503      28.035      63.558
team27       54.411      12.736      42.049      88.145      71.659      31.358
team28       52.302      14.103      83.673      89.209      69.647      31.179
team29       36.692      62.126      85.973      75.501      90.081      43.805
team30       11.241      89.385      24.169      64.224      29.078      81.356
team31       97.805      94.446      24.884      88.646      88.443      96.495
team32       58.962      92.262      60.290       3.570      91.112      56.501
team33       11.049      48.775      36.104      21.639      92.371      44.996
team34       11.709      87.435      14.486      17.774      54.520      46.860
team35        6.413      31.110      57.851      80.980      67.920      73.567
team36       96.208      42.528      10.539       7.708      64.413      31.222
team37       35.246      64.141      89.573      38.817      27.340      97.040
team38       55.748      34.417      39.827      77.623       2.823      36.238
team39       81.196      45.000      95.426      12.264      40.660      88.637
team40       42.884       0.896      22.429      66.067      28.740      13.112
team41       24.907      38.177       7.098      71.563      70.290       7.016
team42       71.826      44.360      87.973      46.981      46.385      37.143
team43       13.844      31.367       7.988      93.415      49.425      67.891
team44       98.704       1.484      14.686      99.098      13.219       8.543
team45       66.356       8.214      56.686      44.323      32.825      33.060
team46        8.403      98.722      55.827      68.192      85.958      58.673
team47       43.112      57.008      11.104      98.701      51.940      70.649
team48       32.505      85.537      78.998      32.109      21.287      52.089
team49       83.634      44.400      92.630      47.921      90.388      50.953
team50       45.454      35.833      11.389      66.954      93.801       1.507
team51       99.013      50.686      64.450      76.030      90.608      16.629
team52       45.086      87.401      21.689       8.013      70.529      90.050
team53       99.013      20.769      35.039      48.676      64.386       5.633
team54       38.196      51.292      95.655      60.229      45.482      69.008
team55       77.601      42.048      80.743      60.465      65.903      79.763
team56       96.249       0.307      11.849      75.860      25.550      91.410
team57       15.025      75.074      52.294      27.738      62.185      96.519
team58       20.167      92.258      46.872      80.252      33.477       8.141
team59       98.775      12.936      14.749      65.759      16.316      81.181
team60       45.928      59.696      97.952      18.544      98.218      95.787
team61       30.616      30.093      28.045      43.326      50.263      20.108
team62       73.263      62.787      36.521       3.721      72.866      61.417
team63       14.849      47.073      72.492      16.541       8.858      26.414
team64       62.309      40.152      11.728      72.430      71.573       7.407
team65       40.583      83.084       9.441      15.552      90.330      45.777
team66       33.257      10.303      25.409      74.720       9.085      59.351
team67       76.152      20.123      35.185      56.502      76.928      71.735
team68       34.541      56.673      80.032      22.247      42.671      68.199
team69       83.586      42.060       6.977       2.520      85.098      34.960
team70       55.371      44.282      16.569      52.015      82.687       4.228
team71       81.404      82.443      50.158      78.512      73.539      41.490
team72       59.114      50.268      65.876      33.903      25.404      17.194
team73       17.480      87.136      27.001       5.615      57.788      88.698
team74       53.110      42.123      56.285      18.663      75.419      71.128
team75       56.391      35.594      48.240       1.750      90.267      97.382
team76       99.214      55.162       3.345      81.593      87.442      66.650
team77       46.953      83.749       1.146       7.489       4.977      80.452
team78       45.724       4.450      47.499       9.823      29.869      82.283
team79       39.594      75.002      88.492      22.723      82.525      97.911
team80       81.169      42.279      75.647      89.440      11.416      39.335
team81       64.250      39.299      49.818      57.864      96.402      95.548
team82       94.841      24.040      11.958       5.318      59.969      10.779
team83       92.933       1.026      81.710      97.464      78.841      57.344
team84       36.450       8.395      69.400      86.812      36.597      16.455
team85       71.750      24.884      30.636      74.946      79.263      77.997
team86       99.362      91.168      46.240      26.168      59.711       1.738
team87       83.334      34.916      88.320      85.146      25.043      20.107
team88        2.643      31.249      24.757      67.152      83.604      31.640
team89       99.156      45.081      44.858      27.230      88.129      83.337
team90       65.141      24.610      58.167      71.459      18.801      86.023
team91       51.628      76.886      66.395       1.916      90.864      45.338
team92       40.155      87.428      62.177      41.007      27.307       1.300
team93       58.294      20.857      40.273      28.308       1.953      12.584
team94        2.418      39.419      67.587      10.242      37.156      57.060
team95       67.278      49.566      38.350      77.755      89.927       0.652
team96        4.016      89.297      30.993      62.085      17.336      18.329
team97       21.721      61.058      46.024      20.753      50.344      33.152
team98       29.133      14.527      85.909       2.355      84.514      27.198
team99       26.202      79.054      63.522      11.883      52.116      17.222
team100      81.173      48.660      46.727      24.455      84.132      38.186


As I have 10 type-A workers and 10 type-B workers, we end up with 100 possible teams. As we can still use individual workers, our set \(i\) has \(10+10+10\times 10= 120\) elements. As you can see the model will quickly become rather large due to the enumeration of all possible teams.

My first thought was to add a side constraint to the assignment problem:


Assignment with side-constraint
\[\begin{align}\min&\sum_{i,j} \color{darkblue}c_{i,j}\color{darkred}x_{i,j}\\ & \sum_j \color{darkred}x_{i,j} \le 1 &&\forall i\\ & \sum_i \color{darkred}x_{i,j} = 1 &&\forall j \\ & \sum_j \left[\color{darkred}x_{w,j} + \sum_{t|\color{darkblue}{\mathit{team}}(t,w)} \color{darkred}x_{t,j} \right] \le 1 && \forall w \\ & \color{darkred}x_{i,j}\in \{0,1\}\end{align}\]


The last constraint says: a worker \(w\) can be used at most once, either individually or as part of a team. This problem is now a full-blown MIP as we can no longer assume that the decision variables \(\color{darkred}x_{i,j}\) are automatically integer-valued.

If we look at the model more carefully, we see that the last constraint implies the first constraint: any worker or any team can be used only once. That means we can drop the first constraint, and we end up with:


Final model
\[\begin{align}\min&\sum_{i,j} \color{darkblue}c_{i,j}\color{darkred}x_{i,j} \\ & \sum_j \left[\color{darkred}x_{w,j} + \sum_{t|\color{darkblue}{\mathit{team}}(t,w)} \color{darkred}x_{t,j} \right] \le 1 && \forall w \\ & \sum_i \color{darkred}x_{i,j} = 1 &&\forall j \\ & \color{darkred}x_{i,j}\in \{0,1\}\end{align}\]


Results


To obtain a reference point, I first solved the pure assignment problem using only individuals (no teams). This gave:


----    103 VARIABLE x.L  assignment

           job1        job2        job3        job4        job5        job6        job7        job8        job9

a5                                                                        1
a6                                                                                    1
b1                                    1
b3                                                1
b4                                                                                                1
b6                        1
b8                                                            1
b9            1
b10                                                                                                           1

  +       job10       job11       job12       job13       job14       job15

a1                                                                        1
a4                                                            1
a7                                    1
b2            1
b5                        1
b7                                                1


----    103 VARIABLE z.L                   =       59.379  total cost


When we add teams to the model, we see:
 

----    142 VARIABLE x.L  assignment

               job1        job2        job3        job4        job5        job6        job7        job8        job9

a1                                                                                                                1
a5                                                                            1
a6                                                                                        1
b3                                                    1
b4                                                                                                    1
b9                1
b10                                                               1
team17                                    1
team28                        1

      +       job10       job11       job12       job13       job14       job15

a4                                                                1
a7                                        1
b2                1
b5                            1
team86                                                                        1
team91                                                1


----    142 VARIABLE z.L                   =       40.057  total cost


The objective goes down. That makes sense: we can select some really cheap teams. To verify that we do not select a worker twice, I also generated a different solution report:
 

----    153 SET sol  alternative solution report

                  job1        job2        job3        job4        job5        job6        job7        job8        job9

team17.a2                                  YES
team17.b7                                  YES
team28.a3                      YES
team28.b8                      YES
-     .a1                                                                                                          YES
-     .a5                                                                      YES
-     .a6                                                                                  YES
-     .b3                                              YES
-     .b4                                                                                              YES
-     .b9          YES
-     .b10                                                         YES

         +       job10       job11       job12       job13       job14       job15

team86.a9                                                                      YES
team86.b6                                                                      YES
team91.a10                                             YES
team91.b1                                              YES
-     .a4                                                          YES
-     .a7                                  YES
-     .b2          YES
-     .b5                      YES


This confirms that workers are not duplicated in the solution.

Finally, some performance numbers. All these models are easy to solve, even the larger ones.


----    144 PARAMETER results  compare statistics

                assign     sidecon       final

type              RMIP         MIP         MIP
vars           301.000    1801.000    1801.000
  discr        300.000    1800.000    1800.000
equs            36.000     156.000      36.000
status         Optimal     Optimal     Optimal
obj             59.379      40.057      40.057
time             0.172       0.422       0.515
nodes               NA
iterations      12.000      85.000      85.000


For the MIP models, we see that the solver did not need to use any branching (zero nodes).

Conclusion


I am not sure this model can be used as-is for the purpose described in [1]. It is a good tool to think a bit about the problem, however. Furthermore, it is a good way to assess the quality of solutions when developing heuristics. MIP solvers have the special property that they can provide proven optimal solutions or a gap that gives some indication about the quality of the solution. 

References



Appendix: GAMS model


$ontext

 
A variant of an assignment problem.

 
References:
    
https://stackoverflow.com/questions/68482524/assignment-problem-with-2-workers-per-job
    
https://yetanothermathprogrammingconsultant.blogspot.com/2021/07/a-variant-of-assignment-problem.html


$offtext




*------------------------------------------------------------------
* basic data
*------------------------------------------------------------------

set
    i
'workers+teams' /a1*a10, b1*b10, team1*team100/
    w(i)
'workers' /a1*a10,b1*b10/
    a(w)
'type-A workers' /a1*a10/
    b(w)
'type-B workers' /b1*b10/
    t(i) 
'teams' /team1*team100/
    team(t,w)
'composition of teams'
    j
'jobs' /job1*job15/
;

display i,w,a,b,t,j;

*------------------------------------------------------------------
* enumerate possible teams
*------------------------------------------------------------------

set t1(t) /team1/;
loop((a,b),
   team(t1,a) =
yes;
   team(t1,b) =
yes;
* next element:
   t1(t) = t1(t-1);
);
option team:0:0:8;
display team;



*------------------------------------------------------------------
* random cost coefficients
*------------------------------------------------------------------

parameter c(i,j) 'cost coefficients';
c(i,j) = uniform(0,100);
display c;


*------------------------------------------------------------------
* reporting macros
*------------------------------------------------------------------

acronym TimeLimit, Optimal, Error;
acronym MIP,RMIP;

parameter results(*,*) 'compare statistics';
$macro report(m,label,modeltype)  \
    results(
'type',label) = modeltype; \
    results(
'vars',label) = m.numVar; \
    results(
'  discr',label) = m.numDVar; \
    results(
'equs',label) = m.numEqu; \
    results(
'status',label) = Error; \
    results(
'status',label)$(m.solvestat=1) = Optimal; \
    results(
'status',label)$(m.solvestat=3) = TimeLimit; \
    results(
'obj',label) = z.l; \
    results(
'time',label) = m.resusd; \
    results(
'nodes',label) = m.nodusd; \
    results(
'iterations',label) = m.iterusd; \
    results(
'gap%',label)$(m.solvestat=3) = 100*abs(m.objest - m.objval)/abs(m.objest);   \
   
display results;


*------------------------------------------------------------------
* assignment problem (don't use teams)
* model uses w instead of i
*------------------------------------------------------------------

binary variable x(i,j) 'assignment';
variable z 'total cost';

equations
   obj1         
'assignment objective'
   assign1a(w)  
'assignment constraint'
   assign1b(j)  
'assignment constraint'
;

obj1..        z =e=
sum((w,j),c(w,j)*x(w,j));
assign1a(w).. 
sum(j, x(w,j)) =l= 1;
assign1b(j).. 
sum(w ,x(w,j)) =e= 1;

model assign1 /all/;

* solve as RMIP: automatically integer
solve assign1 minimizing z using rmip;

option x:0;
display x.l,z.l;

report(assign1,
'assign',RMIP)

*------------------------------------------------------------------
* assignment problem with side constraint
* assignment constraints now use i
*------------------------------------------------------------------

equations
   obj2        
'assignment objective'
   assign2a(i)  
'assignment constraint'
   assign2b(j)  
'assignment constraint'
   side(w)     
'side-constraint'
;

obj2..         z =e=
sum((i,j),c(i,j)*x(i,j));
assign2a(i).. 
sum(j, x(i,j)) =l= 1;
assign2b(j).. 
sum(i ,x(i,j)) =e= 1;
side(w)..     
sum(j, x(w,j) + sum(team(t,w),x(t,j))) =l= 1;


option optcr=0,threads=8;

model assign2 /all-assign1/;
solve assign2 minimizing z using mip;

display x.l,z.l;

report(assign2,
'sidecon',MIP)


*------------------------------------------------------------------
* drop first assignment constraint
*------------------------------------------------------------------

model assign3 /assign2-assign2a/;
solve assign3 minimizing z using mip;

display x.l,z.l;

report(assign3,
'final',MIP)

*------------------------------------------------------------------
* solution report with team composition
*------------------------------------------------------------------

set sol(*,w,j) 'alternative solution report';
sol(team(t,w),j)$(x.l(t,j)>0.5) =
yes;
sol(
'-',w,j)$(x.l(w,j)>0.5) = yes;
display sol;

No comments:

Post a Comment