Is a System of Linear Equations the Right Way to Solve This Optimization Problem?

Question

This is kind of a high-level question, in that I'm not sure which mathematical approach might be best for solving my problem.

I'm trying to automate a painful, error prone, and time consuming process that we do every year. Our camp gets requests from kids for programs, we use this data to base how many sessions of each program we offer (since a session has a cap due to room capacities), and then we try to fill the sessions with the kids in a way that minimizes the number of sessions while maximizing filled requests.

There are restrictions on how we organize our sessions, for example:

• Certain pairs of courses MUST be offered at different times because they use the same resources; graphic design and movie making both use the computer lab
• Certain pairs of courses SHOULD be offered at different times; dance and music should not be scheduled at the same time because the same campers like to take both topics
• If a course has more than one session those sessions should not be offered at the same time; for example it would be better to have a crafts session in 3 different time slots instead of having them all offered at the same time
• We would like to balance the number of sessions (and relatedly, camper spaces) being offered in each time slot; we don't want to have 20 sessions in the first time slot, and 45 in the second, or have 10 small programs in the first slot, and 10 huge programs in the second slot.

I would like to find the "schedule" for our camp that results in the most choices being fulfilled, and I'm sure there must be some kind of mathematical approach to do this.

I've been told that you can do Linear Equations (perhaps with Microsoft Excel "solver") to do this, but before I spend many hours trying to setup the equations and the rules, I wanted to be sure that an expert wouldn't suggest something better suited to the task.

Thanks for your ideas!

Answer 1

This is a linear programming type of problem in that you want to optimize your efforts. But, the nature of the problem is rather simple (outside of the fact that you have many thousands of requests) so you don't need anything elaborate to figure it out. I may be wrong, and someone else can correct me, but this seems like a problem you can just 'count'.

List out all classes that are offered and just add one to a course whenever a request is put in. A class that requires a prerequisite only gets +$1$ once that student completes the prereq. After all requests are submitted, offer the courses that have the highest number of requests. When requests are submitted, you could ask the kids to give their top $12$ classes (or whatever number is appropriate) they'd wish to take as to give you more options of where you can put them.

There are a few other variables such as how many teachers/camp counselors you have, or if a class fills, is that it? Or do you open a new section and offer a second class if the requests for that class are greater than some other class. This seems like something that could be pretty reasonable done by writing a program. I have very little knowledge with programming (could learn what I know inside a week easy) and I'd feel confident I know all the code to write this without a problem (so it shouldn't take you very long to learn). The only real annoying part of the code would be the 'satisfaction' value. Every student you input into the program should be assigned a 'satisfaction' counter. This will represent the number of classes they requested and are able to take. If written in the correct way, you can have the program distribute the students in the course in such a way that optimizes the overall 'satisfaction'.

I should also mention that the program won't differentiate between kids with a satisfaction value of $8$ and $0$ unless you tell it to. By that I mean it won't understand if one kid gets all $8$ classes they want and the other gets $0$ vs each kid gets $4$ and $4$. So, you'd have to have satisfaction preferences. For example, $4$,$4$ is perferable to $8$,$0$ (this won't change your overall satisfaction so you can do this).

Forgive me if I misinterpreted the problem and this was all useless information.