I'm working on a problem with the following formulation:
\begin{align} \min&\quad\sum_{i \in N} \sum_{j \in J} V_{ij}x_{ij} \\ \text{s.t.}&\quad \sum_j x_{ij} = 1 \quad \forall i \in N\\ &\quad V_{ij} = \sum_{k \in N(i)} C_kx_{kj} \quad \forall i \in N, \forall j \in J \\ &\quad x_{ij} \in \{0,1\}, \quad V_{ij} \ge 0 \end{align} where $C_k$ is a positive parameter, $J$ is small (ie $\{1,2,3\}$). Every node $i$ is associated to every element in the set $J$. For example, the objective would read something like: $$V_{a,1}x_{a,1}+V_{a,2}x_{a,2}+V_{a,3}x_{a,3}+V_{b,1}x_{b,1}+\cdots$$
Essentially, I have a dense connected graph with $N$ nodes, where $N(i)$ is the neighboring nodes of $i$. The value of $V_{ij}$ is only relevant to the objective function if $x_{ij}$ takes a value of $1$, however this means that $x_{ij}$ impacts its neighbors $V_{ij}$ value.
I was hoping this model would be manageable for a solver, but it doesn't seem to be the case. The solver is unable to close the MIP gap (after ~1 hour of runtime), but it does look like its finding a good solution. I do recognize that there is a bilinear term in the objective, but the solver is able to break that on its own with relative ease. Also, I've broken the bilinear term but it doesn't make much of a difference, sadly. I have attempted to break the bilinear term by trying to approached (i) applying a new variable $z_{ij}$ that is either $0$ or $V_{ij}$ depending on the value of $x_{ij}$, AND (ii) by changing the equation for $V_{ij}$ directly so it either takes a value of $0$ or the relevant value.
Is anyone aware of this type of formulation and where I can read more about it? Or any ideas on model improvements? Thanks!