  We introduce and study the combinatorial optimization problem with
interaction costs (COPIC). COPIC is the problem of finding two combinatorial
structures, one from each of two given families, such that the sum of their
independent linear costs and the interaction costs between elements of the two
selected structures is minimized. COPIC generalizes the quadratic assignment
problem and many other well studied combinatorial optimization problems, and
hence covers many real world applications. We show how various topics from
different areas in the literature can be formulated as special cases of COPIC.
The main contributions of this paper are results on the computational
complexity and approximability of COPIC for different families of combinatorial
structures (e.g. spanning trees, paths, matroids), and special structures of
the interaction costs. More specifically, we analyze the complexity if the
interaction cost matrix is parameterized by its rank and if it is a diagonal
matrix. Also, we determine the structure of the intersection cost matrix, such
that COPIC is equivalent to independently solving linear optimization problems
for the two given families of combinatorial structures.
