1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Linear Programming question (I think?)

  1. Jun 11, 2012 #1
    1. The problem statement, all variables and given/known data
    This is not a homework question, but it is something I want to work on related to something I volunteer for. Regardless, I did not know where to post this question and this forum was the best place I could think of it. I don't need someone to work it out for me, but what I am looking for is to be pointed in the right direction.

    The question is as follows:

    I have n people and over the course of about 30 weeks, there are m classes. Sometimes in a week there are 2-3, sometimes in a week there are none. Classes can have between 5-25 people in them depending on their type, but all that matters for the question at hand is that classes have a limit on how many people they can have, and this limit varies from class to class.

    For the ENTIRE 30 WEEKS, people have placed preferences for whether they would like to be in a class or doing a completely separate activity, by week.

    The best possible solution is where as many people are in these classes and that everyone is in the same number (i.e. you don't have some in 7 classes and others in 2, I'm looking for a nice even spread).

    2. Relevant equations
    I think this section is explained above...

    3. The attempt at a solution
    I note this seems to be somewhat like a Linear Programming question, and half of a subject I did at university was on LPs. But it was a year ago now since I did it and this is quite a specific type. Things like Simplex method and Interior Point method race through my mind but I don't know lol.

    I searched this on google which was helpful at getting me clearer but the best things I could come across were things like the Assignment problem or the Stable Marriage problem (can't link them as I am under 10 posts)

    I am fairly sure it is an LP, what I am looking for is where to go from here. I know this is my first post in this forum so I really hope I posted this in the right place - I read the stickies. To me this seems to be a fairly complex problem, so if someone doesn't know how to help but can still tell me a good place I could re-ask this question, that would be AWESOME.
  2. jcsd
  3. Jun 12, 2012 #2
    Okay so I have been thinking lots about this and I have been able to well and truly simplify the question I posed in the original post, but I can't see how to edit (maybe I can't) my original post.

    The question is as follows:

    There are m events of varying capacity
    n people
    Each person gives a preference of 0 or 1 for each event (1 means they are able to do it)
    Some events are mutually exclusive with eachother (i.e. someone cannot do two mutually exclusive events)

    That is the whole of it. It could potentially be a linear programming question, but the more I think about it the less I think that is right, I think it is some form of timetabling question. REGARDLESS, I am NOT looking for anyone to solve this for me (purely because I think it is so difficult). ALL I am looking for is someone who can point me in the correct direction (e.g. hey, that expert/expert website over there deals with this sort of thing, maybe go ask some people there!). Anything you can do is extremely helpful.

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook