seat attribution

[Laurent Bagnoud]

Hi,

I'd like to implement an application that attributes the seats to a number
of persons according to their preferences.
The variables I use are :
x : the number of persons
y : the number of tables
z : the number of seats per table

Moreover, for each person i, it is possible to give the cost that
represents the effort that must undertake i for sitting with person j. That
is the cost cij

I guess it' s a kind of an attribution LP like the following one :

min Sumi Sumj of (cij + cji) xij // cij + cji because it costs efforts to
i AND j to sit together at the same table
s.t. Sumi xij = z-1 for all j // z-1 : number of seats minus the place of
i
Sumj xij = z-1 for all i
and xij is either 0 or 1

My questions :
a) Is this LP correct for the resolution of my problem ?
b) I guess I should use the Hungarian method to solve it, but I have to
modify it because of the z-1 that is normally a 1. I guess I could add a
very big number to
the cij that represent the xij of the first solution and use the Hungarian
method again with this new cost matrix until I have filled up the tables.
Is it correct to do so ?

Thank you very much in advance for your precious help,
Laurent

[Lutz Tautenhahn]

Hi Laurent,

I'm afraid, the Hungarian method will not work in your case,
because your problem seems not to be a linear Assignment problem.
It looks more like a special case of the so-called Layout problem,
which is quadratic. Look at my page at
www.tu-chemnitz.de/~luta/plt/lgrthm/layout.html
(in german) for more details about the Layout problem.
A short translation [with appropriate symbols of your model]:
Data:
o number of objects [=x]
O number of places ( O = o ) [=y*z]
m_ij quantity to transport from object i to object j [=c_ij]
S_kl distance from place k to place l
[=1 if place k and place l are on the same table, otherwise 0]
Variables:
u_ik is 1, if object i is assigned to place k, otherwise 0

Regards,
Lutz Tautenhahn

"Laurent Bagnoud" <laurent...@swisscom.ch> schrieb im Newsbeitrag
news:01c182f3$51a18c10$a16e400a@u54165...

[Paul A. Rubin]

[posted and mailed]

"Laurent Bagnoud" <laurent...@swisscom.ch> wrote in
news:01c182f3$51a18c10$a16e400a@u54165:

Your formulation does not seem to take into account the number of tables or
the capacities of the tables (if not all equal). Also, since xij must equal
xji in your setup, you must either add those constraints or define the xij
variables only for i < j, in which case your sum xij = z-1 constraints are
not correct as written. Last, I don't see how your constraint ensure
transitivity (if i sits with j and j sits with k, then i must sit with k).

As long as you are willing to use 0-1 variables, which makes the model a
integer (or mixed-integer) linear program, the following formulation should
work.

Parameters: N = # of people, T = # of tables, C_i (i=1...T) = capacity of
i-th table (for consistency, we require that sum_i C_i >= N), c_ij = cost to
person i for sitting with person j.

Variables: x_ij = 1 if person i sits with person j, 0 otherwise (i, j =
1...N; i < j); y_it = 1 if person i sits at table t, 0 otherwise (i = 1...N,
t = 1...T).

Objective: minimize sum {i, j = 1...N; i < j} (c_ij + c_ji)*x_ij

Constraints:

sum_{t=1...T} y_it = 1 for all i [everyone sits at exactly one table]

sum_{i=1...N} y_it <= C_t for all t [table capacity limits]

x_ij >= y_it + y_jt - 1 for all i < j and all t [does i sit with j?]

0 <= x_ij <= 1 for all i < j

y_it \in {0, 1} for all i and all t.

Note that the y variables are constrained to be binary but the x variables
can be allowed to be continuous between 0 and 1.

I'm assuming that the costs c_ij are nonnegative, so that the program will
automatically try to take the smallest feasible value for each x_ij subject
to the values for y and the constraints. The third constraint works as
follows: if neither i nor j sits at table t, it reduces to x_ij >= -1,
which is vacuous; if one but not both of i and j sits at table t, it reduces
to x_ij >= 0, also vacuous; but if both i and j sit at table t (y_it = 1 =
y_jt), it reduces to x_ij >= 1, which forces x_ij = 1 and thus contributes
c_ij + c_ji to the objective.

HTH,

Paul

***************************************************************************
Paul A. Rubin Phone: (517) 432-3509
Department of Management Fax: (517) 432-1111
The Eli Broad Graduate School of Management E-mail: ru...@msu.edu
Michigan State University http://www.msu.edu/~rubin/
East Lansing, MI 48824-1122 (USA)
***************************************************************************
Mathematicians are like Frenchmen: whenever you say something to them,
they translate it into their own language, and at once it is something
entirely different. J. W. v. GOETHE

[Ivo van Baren]

Hi Lutz ,

Could you please open www.tu-chemnitz.de/~luta/plt/lgrthm/layout.html

I can get no access.

Thanks in advance.

Ivo van Baren

"Lutz Tautenhahn" <lutz.ta...@wirtschaft.tu-chemnitz.de> wrote in
message news:9v86cc$kqg$1...@narses.hrz.tu-chemnitz.de...

[Ivo van Baren]

Hi Lutz ,

Could you please open www.tu-chemnitz.de/~luta/plt/lgrthm/layout.html

I cann't get access to the site, and I am still interested.

Thanks in advance.

Ivo van Baren

"Lutz Tautenhahn" <lutz.ta...@wirtschaft.tu-chemnitz.de> wrote in
message news:9v86cc$kqg$1...@narses.hrz.tu-chemnitz.de...

[Lutz Tautenhahn]

Hi Ivo,
the link works fine for me, but you can also try the mirror page at
http://home.t-online.de/home/lutz.tautenhahn/plt/lgrthm/layout.html
or go to the root of my homepage at
www.tu-chemnitz.de/~luta/
and use the links PLT->Algorithms->Layout.
Regards
Lutz Tautenhahn.

"Ivo van Baren" <i.a.c.v...@freeler.nl> schrieb im Newsbeitrag
news:9vq2kb$bf9$1...@newswriterENV1.svr.pol.co.uk...