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?

You can look up examples of IP formulations that use this trick. (The idea is similar to a "fixed" charge.) Create new variable Yw = 1 if worker w is used, 0 ow. Min sum({w}Yw). Add constraints saying: WhichWorkerDoWhichJob[w,j] > M * Yw where M is a big number. If any worker gets assigned to even one job, that will force that worker's Y binary variable to be 1. Hope that helps you. — Ram Narasimhan, May 29 '15 at 00:35
I made the changes, used the big M variable, but didnt change anything. I made a sample code for that. — thomas.kardos, May 29 '15 at 01:36
(Sorry for my bad english) So I want to minimize the number of workers based on their knowledge, like if w4 can do all the jobs, he would be the only one worker i need. — thomas.kardos, May 29 '15 at 01:44
Anyway, if I add a new print to check the values of each Y[w], all will return zeros. — thomas.kardos, May 29 '15 at 12:30
yes, Yw = 0 satisfies the New rule as it is stated. Please modify the Newrule to be: `Newrule{w in Workers, j in Jobs}: WhichWorkerDoWhichJob[w,j] < M * Y[w];` Notice that it should be strictly greater than, to force the Y variables become 1, if that worker w is assigned any job. — Ram Narasimhan, May 29 '15 at 18:09

score 0 · Answer 1 · answered May 29 '15 at 16:27

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).

score 0 · Answer 2 · answered Jun 19 '15 at 12:38

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.

Issues with objective - GMPL

2 Answers2