Question

ip formulation

Ms. Candy is famous for her parties in the New York area. In each four year administration she throws k parties, set m tables at each party and seats n people at each table. She makes a list of mn influential people at the start of the four year period and invites them to every party. Her tables are all distinct from each other (teak, oak, cherry, etc.) and k s m. It is rumored that her parties are famous because of her clever seating arrangements. She makes sure that each of her guests sits at each table at most once. And she believes very strongly that the atmosphere remains lively if each guest meets different people at his/her table at each party. So, every time any pair of guests finds themselves at the same table after the first time, she awards herself an imaginary penalty of c units, where c> 0. Given k, m, n (all positive integers 2 2 and k s m. formulate the problem of determining the seating arrangement of her guests at the tables at the various parties, subject to the constraint that no guest sits at a table more than once and the overall penalty is as small as possible, as an integer program. If k = m, what condition should m, n satisfy to guarantee that a zero penalty seating arrangement exists? When k-m-n-2, show that there is no zero penalty seating arrangement using your formulation above.

Answer 1

SOLUTION

First let's define our seating variables: (1 if the Ith person sits at table i in partyj l0 if they don't This variable allows us to control which guest sits where and when. Using this we can already formulate the first constraint -since we can't seat the same person twice at the same table then it must be the case that if af, = 1 implies that 0 (for ')so our constraint looks like so: Now to find the cost function we have to define another variable to control how many times a pair of guests will meet at a table. For this we define bu as (1 if guest IAND guest l' sit at table i in party j 0 if they don't 1 and a= 1 then we can Since this only happens when both af accurately define more = as b(a,)aj) Now we define Sur as the number of times guests l and ' meet at a table after the first time: )-1 Su (1) = ij

However, we cannot define the cost function yet since in Su we are counting guests who never meet. To fix this, we add another variable: fiif guests I and never meet 0 if they do Which, in terms of the a's is given by: |0 otherwise Also notice that in (1) we have that b =1 for every partyj so from the final cost function we must eliminate these cases. This final cost function is given: mn mn mine ΣΣ(ΣΣ+)-