Question

7.4: Ms Skorean's parties in Washington D.С.: Ms. Skorean is famous for her parties in the Washington, D.C. area. In each four- year administration she throws k parties, sets m tables at each party and seats n people at each table. She makes a list of mn influential people at the start of party. Her tables are all distinct from each other (teak, oak, cherry etc.) and k . 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 find themselves at the same table after the first time, she awards herself an the four year period and invites them to every Ch.7, Integer Programs imaginary penalty of c units, where c 0. Given k,m, n (all positive integers 2 2 and k 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 conditions should m,n satisfy to guarantee that a zero penalty seating arrangement exists? When k-m 2, show that there is no zero penalty seating arrangement using your formulation above. Vishwas Bawle).

Answer 1

First let's define our seating variables: 1 if the Ith person sits at table i in party j 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 a-1 implies that ali, = 0 (for l l') 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 bi as l if guest IAND guest !' sit at table i in party j 0 if they don't Since this only happens when both aj accurately define bif as and at1 then we can more 崰ー(晴)(時) Now we define S the first time: as the number of times guests and l' meet at a table after Sll' = Ly 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: 1 if guests 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 for every party j so from the final cost function we must eliminate these cases. This final cost function is given: