Optimalization problem

**CompuChip** · Jun23-09, 08:38 AM

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 a_i and b_i people ( $LaTeX Code: 0 < a_i \\le b_i$ )
- There may be different room types i, j for which a_i = a_j and b_i = b_j, 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 r_i of type i the manager should reserve, such that
- all n persons have a bed, i.e. $LaTeX Code: \\sum_i r_i b_i \\le n$
- the number of rooms is minimal (i.e. if there is a room with a_i = b_i = 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 a_i = 1, b_i = 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]

**Office_Shredder** · Jun23-09, 09:42 AM

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

**muzialis** · Jun23-09, 09:52 AM

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

Muzialis

**Office_Shredder** · Jun23-09, 09:59 AM

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

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

**muzialis** · Jun24-09, 04:40 AM

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

Muzialis