CODEWITHSUNDEEP
algorithmoptimizationgraphconstraints
Samuel
Samuel

Reputation: 686

Affect m students to n groups, but with constraints?

I asked about the minimum cost maximum flow several weeks ago. Kraskevich's answer was brilliant and solved my problem. I've implemented it and it works fine (available only in French, sorry). Additionaly, the algorithm can handle the assignement of i (i > 1) projects to each student.

Now I'm trying something more difficult. I'd like to add constraints on choices. In the case one wants to affect i (i > 1) projects to each student, I'd like to be able to specify which projects are compatible (each other).

In the case some projects are not compatible, I'd like the algorithm to return the global optimum, i.e. affect i projects to each student maximizing global happiness and repecting compatibility constraints.

Chaining i times the original method (and checking constraints at each step) will not help, as it would only return a local optimum.

Any idea about the correct graph to work with ?

Upvotes: 1

Views: 95

Answers (2)

David Eisenstat
David Eisenstat

Reputation: 65498

If you can stomach the library dependency, integer programming will be quicker and easier than anything you can implement yourself. All you have to do is formulate the original problem as an integer program and then add your ad hoc constraints at the end.

Upvotes: 1

kraskevich
kraskevich

Reputation: 18566

Unfortunately, it is not solvable in polynomial time(unless P = NP or there are additional constraints).

Here is a polynomial time reduction from the maximum independent set problem(which is known to be NP-complete) to this one:

Given a graph G and a number k, do the following:

  1. Create a project for each vertex in the graph G and say that two project are incompatible iff there is an edge between the corresponding vertices in G.

  2. Create one student who likes each project equally(we can assume that the happiness each project gives to him is equal to 1).

  3. Find the maximum happiness using an algorithm that solves the problem stated in your question. Let's call it h.

  4. A set of projects can be picked iff they all are compatible, which means that the picked vertices of G form an independent set(due to the way we constructed the graph).

  5. Thus, h is equal to the size of the maximum independent set.

  6. Return h >= k.

What does it mean in practice? It means that it is not reasonable to look for a polynomial time solution to this problem. There are several things that can be done:

  1. If the input is small, you can use exhaustive search.

  2. If it is not, you can use heuristics and/or approximations to find a relatively good solution(not necessary the optimal one, though).

Upvotes: 1

Related Questions