What type of algorithm should I use?

Question

So I am looking to solve the problem stated below and I am having problems and what to actually look for as I can not describe the problem in simple terms. I am hoping someone may be able to shed some light on the correct Algorithm or path I should take to solve it.

The problem(simplified):

so lets say I have a multiple people objects.

Person1
Person2
Person3

Now lets say I have 6 slots

Slot1
Slot2
Slot3
Slot4
Slot5
Slot6

Each person has rules associated with them such as

• Person1 can not use a slot with an odd number and must be in 3 different slots.
• Person2 Can only go into slots from 2 up and must be in 2 slots
• Person3 can only go into 1 prime number slot.

so we end up with

 Slot1 - Person3
 Slot2 - Person1
 Slot3 - Person2
 Slot4 - Person1
 Slot5 - Person2
 Slot6 - Person1

I know this will require use of A.I/Machine learning and I have done some research into the area but I cannot find what algorithm I should be using for a problem like or even how to search for this. The only way I have found of doing this in some way is through as regression tree but it seems to me like that way seems like the wrong path to take.

Note: I will be using c# to solve this problem and hopefully some framework like Encog.

Answer 1

The pairing between Person and Slot is a scheduling problem which requires knowledge to solve it. The knowledge is described in rules like "Person1 can not use a slot with an odd number and must be in 3 different slots." The algorithm to solve the problem uses the rules and the given ressources (three persons and six slots) to generate all possible solutions. Computerscience has the task to formalize the knowledge into machine readable code. There are many programming languages out there e.g. PDDL, Prolog or object-oriented languages. In classical "AI Planning and scheduling" which is discussed at the ICAPS Conference the PDDL language would be the prefered choice for modelling the knowledge. The algorithm itself to solve a given domain is in most cases backtracking, monte-carlo-tree-search or simply brute-force. That is called "problem solving as search".

Answer 2

Actually I think you can solve this problem with Maximum Matching with a simple modification. In the standard Maximum Matching each node is only matched with one other node but here a Person can have multiple matches. By creating multiple instances of Person you can reduce this problem to Maximum Matching. For example:

Person1 cannot use a slot with an odd number and must be in 3 different slots.

Create 3 nodes for Person1 and connect them to even number slots.

Person 2 Can only go into slots from 2 up and must be in 2 slots

Create 2 nodes of Person2 and connect them to slots with number bigger than 2.

Person 3 can only go into 1 prime number slot.

Create 1 node for Person3 and connect it to slot1, slot2, slot3, and slot5.

Perform Maximum Matching on the resulted graph and you will find the answer.

Answer 3

Actually this problem is standard discrete optimization problem. You may want to look at coursera discrete optimization course. In its first week, it has a workshop named Simple Puzzles. It gives a similar problem to yours and shows how to solve it in their platform mini-zinc.

After you understand how this type of problems solved, you may want to look a c# solution from List of optimization software.