Issues with objective - GMPL

Question

I'm trying to model an objective.

It's a special case of assignment problem, where I want to minimize the workers needed for making all the jobs. So all jobs have to be done, but not all the workers have to do something.

Constraints:

s.t. AllJobsHaveToBeDone {j in Jobs}:
    sum {w in Workers} WhichWorkerDoWhichJob[w,j]=1; 


s.t. JustDoWhatHeCanDo {w in Worker, j in Jobs}:
    WhichWorkerDoWhichJob[w,j] <= WhatCanHeDo[e, j];

But I just can't minimize the number of workers in the objective. Is there a way to count the workers in a variable who actually do a job, and then minimize that variable?

I'm fairly new to it, any suggestions?

    set Jobs;
    set Workers;

    param WhatCanHeDo{w in Workers, j in Jobs}, binary;
    param M;

    var WhichWorkerDoWhichJob {w in Workers, j in Jobs}, binary;
    var Y{w in Workers}, binary;


    s.t. AllJobsHaveToBeDone {j in Jobs}:
    sum {w in Workers} WhichWorkerDoWhichJob[w,j]=1;

    s.t. JustDoWhatHeCanDo {w in Workers, j in Jobs}:
    WhichWorkerDoWhichJob[w,j] <= WhatCanHeDo[w, j];

    s.t. Newrule{w in Workers, j in Jobs}:
    WhichWorkerDoWhichJob[w,j] >= M * Y[w];

    minimize target: sum{w in Workers} Y[w];

    solve;


    printf "------------------------------------------\n"  ;

    #To check the values of each Y[w] -> but all will be zeros.
    for{w in Workers}
    printf "%s %s\n",w,Y[w];

    for{w in Workers, j in Jobs:
    WhichWorkerDoWhichJob[w,j]=1}
    printf "%s do %s job. \n",w,j;

    data;

    set Jobs:= j1 j2 j3 j4 j5 j6 j7 j8;
    set Workers:=w1 w2 w3 w4 w5;

    param WhatCanHeDo: j1 j2 j3 j4 j5 j6 j7 j8 :=
            w1 1 0 0 0 1 1 1 0
            w2 1 1 0 1 0 1 0 0
            w3 1 0 1 0 1 0 1 0
            w4 1 1 1 0 0 0 1 1
            w5 1 0 1 0 0 1 0 0
            ;

    param M:=10000;

    end;

Any new tips or suggestions?

Answer 1

So I think there are multiple ways to get this done. The big M-Method is nice but here not strictly necessary, since you already defined binary variables and glpk can solve the resulting mixed integer problem.

So GLPK gives me satisfying results for two minor changes to your example code. First I deleted the big M and the newrule. Second I added the binary Y variable to your JustDoWhatHeCanDo constraint:

s.t. JustDoWhatHeCanDo {w in Workers, j in Jobs}:
WhichWorkerDoWhichJob[w,j] <= WhatCanHeDo[w, j] * Y[w];

This will output me that w2, w3 and w4 are doing all the jobs.

Answer 2

You can minimize the number of workers as follows

minimize NumWorkers:
  sum {w in Workers, j in Jobs} WhichWorkerDoWhichJob[w, j];

where WhichWorkerDoWhichJob is a binary variable that is 1 if worker w does job j. You'll also need constraints on WhichWorkerDoWhichJob, but these depend on problem specifics (whether one worker can do multiple jobs etc).