I am trying to solve a linear programming problem like the following, where $x_i$ represents a binary decision to purchase or not product $i$, and $a_i$ is the utility of product $i$: $$max \sum_{i=1}^n a_ix_i$$ However, I also have a $n\times n$ matrix $b$, where $b_{ij}$ represents the added (or diminished) overall utility of purchasing products $i$ and $j$ together. Given that all the constraints are one-dimensional (i.e. total cost and total number of products), how can I modify the objective function to better represent the model?
I thought of $max \sum_{i=1}^n x_i(a_i+\sum_{j=1}^n x_j b_{ij})$, but I'm pretty sure this breaks the linearity because of the product $x_i x_j$.
Note: as expected, $b$ is symmetrical.
You need to introduce a new set of binary variables $y_{ij}$ that take value $1$ if and only if items $i$ and $j$ are both selected.
So your objective function becomes $$ \sum_{i=1}^n a_ix_i + \sum_{i=1}^n \sum_{j<i} b_{ij}y_{ij} $$
Don't forget to define variables $y_{ij}$ in your constraints: $$ y_{ij}\le x_i \\ y_{ij}\le x_j \\ $$ (If $y_{ij}$ takes value $1$, then $x_i$ and $x_j$ also have to take value $1$)