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!

Optimalization problem

  1. Jun 23, 2009 #1


    User Avatar
    Science Advisor
    Homework Helper

    Hey guys,

    Here is an interesting problem that I find to be a lot harder to solve than I initially thought.
    Suppose you are a hotel manager and people keep asking you to make an offer to their groups. You want to make a simplified model that does the following:
    - The group size is given: n adults
    - You have room types i, which can accommodate between ai and bi people ([itex]0 < a_i \le b_i[/itex])
    - There may be different room types i, j for which ai = aj and bi = bj, then just choose one (e.g. the one with lowest i).
    - The number of rooms of each type is unlimited

    For now I will be satisfied to solve this problem without additional constraints (like the price of the room).
    Do you know of some nice algorithm which will tell me how many rooms ri of type i the manager should reserve, such that
    - all n persons have a bed, i.e. [tex]\sum_i r_i b_i \le n[/tex]
    - the number of rooms is minimal (i.e. if there is a room with ai = bi = 1 then taking that room n times is a possible but not a preferred solution)
    - the number of empty beds is minimal (i.e. if n = 1 and there is a room with ai = 1, bi = 6, then one room of that type will do but it is not preferred because 5 beds will be empty).

    [edit]Solutions may be greedy, as the number of room types will be fairly small (usually 1 to 5) as will the number of people n (usually 1 to 4); but the algorithm should be as fast as possible of course, having to be run rather often[/edit]
    Last edited: Jun 23, 2009
  2. jcsd
  3. Jun 23, 2009 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I'm a bit confused. You just want to stuff the n people into as few rooms as possible? Or does the group have additional conditions on who's rooming with who? As written, it seems like taking the largest room that doesn't have more beds than the remaining people in the group each time, and then if no such room exists taking the smallest room lerft would
    1) Ensure everyone has a bed
    2) Minimize the number of rooms used necessarily
    3) Under the condition that the minimal number of rooms are used, minimize the number of beds used
  4. Jun 23, 2009 #3
    Hi All,

    I am wondering instead how to deal with the fact more than one target is defined (e.g. minimize the numer of rooms and the empty beds).

    A trivial example, the hotel has got three rooms, capacity 4, 5 and 20 beds.
    A group of 6 people arrives, is it preferable to give them 2 rooms (3 empty beds) or 1 room and (16 empty beds)?

    Thank you

  5. Jun 23, 2009 #4


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    That's something the manager of the hotel has to decide (without some sort of weighting function to tell you how 'bad' an empty room and an empty bed is, the question is impossible to answer. It has nothing to do with algorithms). The more interesting question then is something like:

    Given groups of size [itex]n_1, n_2, ..., n_k[/itex] are arriving, and no two groups can share a room, find an algorithm to fit them all minimizing the number of rooms OR minimizing the number of empty beds
  6. Jun 24, 2009 #5
    Hi All,

    I am quite curious to see the answers from more expert forum fellows. In the meantime I will try one.

    It would be possible to use well known common algorithms, having expressed the problem in a linear programming format.

    To do so, consider binary ( 0 or 1) variables per each bed.
    Furthermore, particular consideration will be given, within each room, to the variable with the lower index.
    An additional constraint is added asking that the value of the variable with lower index be more or equal than the other variables within the room. The significance of this will hopefully appear later.

    With this is mind, the number of empty beds, not considering empty rooms, could be calculated by:
    - multiplying the variable with the lower index within each room per the number of beds available in the room
    - subtracting form this the number of guests n

    The number of occupied rooms, to be minimized, could be found by summing the variables with the lower index within the room.

    An additional set of constraints is added to describe the fact that the sum of the variables belonging to a room is equal or lower than the room capacity, and equal or higher than the minimum number if beds occupied.
    A last constraint imposes to the sum of all the variables to be equal to the number of guests n.

    I put some symbols together in the word file as my Latex is very boor.
    Alfa and beta are just weighting coefficient for an overall cost function.

    Hope it makes any sense, good day


    Attached Files:

    • PP.doc
      File size:
      20.5 KB
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook