linearize quadratic objective function

[Chris]

Hi. I have a set partitioning problem where one incurs a cost of c_
{ij} if sets i and j are both chosen. In other words, the cost of
choosing a particular set depends on what other sets I have selected.
Define a_{ui}=1 if element u is contained in set i and a_{ui}=0
otherwise. My decision variable is y_i where y_i=1 if set i is
chosen, 0 otherwise. My formulation is:

Minimize \sum_{i,j} y_i * y_j * c_{ij}

s.t. \sum_j a_{uj} y_j = 1 for all elements u

Unfortunately, this is quadratic and my attempts at linearizing the
problem by introducing a variable x_{ij}=1 if sets i and j are both
chosen have failed. Any suggestions? Thanks

Chris

[Paul]

This is a pretty common linearization (I think):

minimize \sum_{i,j} w_{ij}
s.t. \sum_j a_{uj}y_j = 1 \forall u
s.t. w_{ij} \ge c_{ij}*(y_i + y_j - 1) \forall i,j

(I'm assuming c >= 0, although you did not say that.) The additional
variables w_{ij} are divisible and non-negative.

/Paul