Assignment that minimizes (or constrains) the number of employed workers

[afe...@netflix.com]

I'm using the cp_solver to solve a fairly standard assignment problem: Minimize cost for assigning N tasks to M workers. In my setup workers can take multiple tasks, but each task can only be assigned to one worker. So far, so good.

But I want to also add a constraint (or, alternatively, modify the objective), to minimize the overall number of workers employed to do the tasks. One approach I've tried is using a constraint that ensures each worker gets either 0, or > 3 tasks. I've used the following code to do this:

for i in range(num_workers):

     enough_work = model.NewBoolVar("%i has enough work" % i)

     worker_off = model.NewBoolVar("worker %i off" % i)

     model.Add(sum( x[j][i] for j in range(num_tasks)) >= 3).OnlyEnforceIf(enough_work)

     model.Add(sum( x[j][i] for j in range(num_tasks)) < 3).OnlyEnforceIf(enough_work.Not())

     model.Add(sum( x[j][i] for j in range(num_tasks)) <= 0).OnlyEnforceIf(worker_off)

     model.Add(sum( x[j][i] for j in range(num_tasks)) > 0).OnlyEnforceIf(worker_off.Not())

    

     model.AddBoolOr((enough_work, worker_off))

This works, but now the problem takes hours to solve, rather than milliseconds. :( In my case I need the problem solution in < 2s runtime.

Another solution I've been considering is to add the number of employed workers into the objective function. But to do that I'd need a function that could count non-zero elements of X[*][j] and I don't see any functions that'd support that.

What's the best way to add this type of constraint / objective? I'm open to relaxations (solution doesn't have to be exact), but I do need to keep it within < 2s runtime. 

Thanks,

Aish

[Laurent Perron]

Why don't you simply write:

for i in range(num_workers):

     working = model.NewBoolVar("%i has enough work" % i)

     model.Add(sum( x[j][i] for j in range(num_tasks)) >= 3).OnlyEnforceIf(working)

     model.Add(sum( x[j][i] for j in range(num_tasks)) <= 0).OnlyEnforceIf(working.Not())

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[afe...@netflix.com]

Thanks Laurent! Ahh, that helped, thanks.

That's got it down to tens of minutes of runtime, but it's still much much slower than without it, and unfortunately still outside my runtime budget. Any tricks I can do to speed it up? I'd be ok with it being only an approximate solution, but I need to make it run within my performance constraints (< ~2s runtime)   

[Laurent Perron]

Can you send me some code?

In the meantime, you can try:

solver.parameters.num_search_workers = 8 # Brute force.

or

solver.parameters.linearlization_level = 0  # or 2

before calling Solve.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00