Is there any Multiple algorithm better than fully arranged while solving constraint problem？

Question

I have n different group， each group should contain 4 people（DB,UI,PF,Designer） and i have 4*n student， i want to place them into the group.

There is several constraint， such as one group can only have 1 female， the average gpa should meet 3.0 etc. Each constraint will have a score and i need to make sure all the group have the similiar score.

I use recusive to try all statement and calculate the score and variance.

However, my method works when there is not too much student. If there is 100 student, it will be 100! and it is hard to solve.

Is there any other idea that can imporve the algorithm？

Thanks so much！

Use a constraint programming solver (e.g., developers.google.com/optimization/cp/cp_solver) — David Eisenstat
– David Eisenstat, Commented Sep 3, 2019 at 13:42

MrSmith42 · Accepted Answer · 2019-09-03 09:58:38Z

1

This is a classical Constraint satisfaction problem (CSP https://en.wikipedia.org/wiki/Constraint_satisfaction_problem) .

This is a hard problem. There are a lot of professional systems out there and a lot of algorithms out there that try to eliminate impossible solutions fast to reduce the search-space.

But as far as I know there is no general approach to reduce the over all complexity. If you apply the constrains in a clever order you can in most cases significantly reduce the search space.

E.g. With the constrain "only 1 female" you can eliminate most combinations in an early state.

answered Sep 3, 2019 at 9:58

MrSmith42

10.2k6 gold badges41 silver badges52 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Is there any Multiple algorithm better than fully arranged while solving constraint problem？

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related