Which algorithm(s) can solve this constraint programming problem ?

Question

Hello,

I need to solve a job affectation problem and I would like to find preferably efficient algorithms to solve this problem.

Let's say there are some workers that can do several kind of tasks. We also have a pool of tasks which must be done every week. Each task takes some time. Each task must be taken by someone. Each worker must work between N an P hours a week.

This first part of the problem seems to be a good candidate for a constraint programming algorithm.

But here is the complication: because a worker can do different tasks they may also have preferences (or wishes). If one want to satisfy all wishes for everyone there is no solution to the problem (too many constraints).

So I need an algorithm to solve this problem. I don't want to reinvent the wheel if the perfect wheel already exists.

The algorithm must be fair (if one can define this word) so for example I should be able to add a constraint like "try to satisfy at least one wish per people". I'm not sure that this problem can be solved by Constraint Hierarchies methods described here: Constraint Herarchies. In fact I'm not sure that "fairness" and wishes can be expressed by valid constraints for this category of algorithms.

Is there a constraint programming expert to give me some advices ? Do I need to develop a new wheel with some heuristics instead of using efficient CP algorithms ?

Thanks !

Answer 1

This sounds like job shop scheduling.

Answer 2

Your problem is complex enough that a general solution will probably require formulating as a linear-integer problem. If on the other hand you are able to relax certain requirements, you may be able to use a simpler approach. For example, bipartite matching would allow you to schedule multiple workers to multiple jobs, and can even handle preferences, but would not be able to enforce general 'fairness' constraints. See e.g. this related SO question. Vertex colouring has efficient algorithms for enforcing job separation constraints.

Other posters have mentioned simplex and job shop scheduling. Simplex is an optimisation algorithm - it traverses a solution space seeking to maximise some objective function. Formulating the objective function can certainly be done, but is non-trivial. Classical job shop scheduling, like bipartite matching, can model some aspects of your problem, but not all. There are no precedence constraints, for example. There are extended versions that can handle some constraints, for example placing time bounds on tasks.

If you're interested in existing implementations, the Python networkx library has an implementation of this matching algorithm. An example of an open source timetabling program that might be of interest is Tablix.

Answer 3

I've done timetabling, which can be considered a form of constraint programming. You have hard (inviolable) constraints and soft constraints (such as interval preferences).

Linear integer programming usually becomes useless after more than 30 variables, and this can also be said about simplex.

It was trough domain-specific optimizations of heuristic algorithms that a solution was found.

The heuristic algorithms used were simmulated annealing, genetic algorithms, metaheuristic algorithms and similar, but in the end the best result were provided by an "intelligent" domain customized greedy search algorithm.

Basically, you might get some decent results with one of the heuristics here, but the main problem is being able to discern when a problem is overconstrained.

A great open-source tool for research is the HeuristicLab.

Answer 4

I agree with what have been proposed here. However, MIP (Mixed Integer Programming problems) of very large size (far beyond 30 variables !) are practically solved nowadays thanks to commercial codes (Xpress, Cplex, Gurobi) or open-source (Coin-Or/Cbc). Furthermore, fancy modeling languages such as OPL Studio, GAMS, AMPL, Flop ... allow to write easily mathematic models instead of using APIs.

You can take advantage of NEOS server (http://neos.mcs.anl.gov/neos/solvers/index.html) to try very esaily different MIPs available. You send your model in AMPL format . Although AMPL comes as a free limited version, NEOS can handle unlimited instances.

Modeling languages exist also for CP (COMET / OPL Studio) and Local Search (COMET).

Feel free to get in touch with me through my web site www.rostudel.com ('contact' page)

David