What is the appropriate algorithm for bipartite matching with constraints?

Question

I have a problem that is a bit complex, and I don't know what method/model I should use to express it (much less solve it).

Let's say we have a lot of employees and a few jobs to be done. Each employee ranks the jobs they want most.

Easy. Bipartite matching, with weighted edges. Or Hungarian algorithm. Right?

Now things become more complicated. Instead of one job each day, an employee has to do 4 jobs in a day. The same single ranking they gave will be taken into account for the other 3 jobs they receive (no repetitions).

Since each employee must have 4 jobs, and there are many more employees than jobs, each job can have multiple people assigned to it for each period.

More complicated: each job has a maximum of employees it can accommodate (different for each job).

More complicated. Now jobs are skill based. Each employee has not only a preference ranking, but a skill class they belong to, low, med, or high. So each job has a phase for the low-skilled, the medium-skilled, and the high-skilled, with a skill level repeated for the fourth phase, as needed.

The objective is to make sure every employee ends up with the most of their highest ranked choices.

Does there exist some framework for solving such problems? Is there a way to adapt bipartite matching for all of these constraints?

• Erel Segal-Halevi: I think what you need is many-to-many matching. The answer by D.W. here: cs.stackexchange.com/q/161149/1342 shows how to solve such problems efficiently, using flow networks.

Answer 1

The problem as described still seems amenable to doing a bipartite matching with weighted edges if you adapt the graph setup as follows.

If an employee must do four jobs, represent the employee with four vertices in the graph. Each job should be represented as four vertices in the graph, one for each needed skill level plus one repeated skill level. Connect each employee vertex with the job vertex corresponding to the highest skill level the employee is capable of performing. Don't connect an employee to more than one skill level within a job. Example: if a job has two high skill phases, connect all the employee vertices for a given qualified employee to one phase or the other, not both. The edge weights between the employee and job vertices should be the employee preference score for the job.

With this graph, a maximal bipartite matching should produce proper job assignments maximizing employee preferences while matching skills.

Answer 2

Constraint satisfaction problems are solved easier on declarative languages, where you specify the problem and not how to actually solve it.

Look for a max-SAT solver (=