Appropriate ML algorithm for allocating students to seats

Question

I'm new to machine learning and am trying to use it to solve a specific problem related to seating students in a classroom. I want to take a list of students and allocate them each to a seat, such that a certain output value is maximised.

An example:

Students (each one containing all the data from which a compatibility score can be calculated): A B C D E F

Seats: 1 2 3 4 5 6 7 8

Each pair of students has a predefined 'compatibility score' and each pair of seats has a geometric distance between them. After sorting students into seats, I would calculate a ratio between those two values, the average of which would be my outcome to be optimised.

A class of 25 students and 25 seats has something like 15,000,000,000,000,000,000,000,000 possible arrangements, so a brute force method is rather unfeasible. My ideal outcome here is that machine learning can develop an optimised algorithm for sorting them.

Any ideas for what kind of ML algorithm I want?

Answer 1

That problem is an optimization problem, selecting the selection of the best element (with regard to some criterion) from some set of available alternatives.

It falls in the general class of computational geometry. Specifically, a bin packing problem, items of different values must be packed into a finite number of containers.

Answer 2

I think you want to look more into the filed of Linear Programming or Operational Research. It boils down to maximize/minimize a function, given some constraints.

Of course, you might not be able to find an optimal solutions in some cases, but the solution found by any of these methods is usually close.

Here you can find some good intro together with a Python library: https://developers.google.com/optimization/introduction/python