Additional resources for this type of problem formulation

Question

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!

Answer 1

The model looks really linear to me. After substituting out $V_{i,j}$ you have basically terms $x_{i,j}\cdot x_{k,j}$. Solvers may linearize that automatically or you must do it yourself. My guess is this is a fairly easy MIP (of course, I am wrong 50% of the time).

---

I used random data on a problem with similar size:

$ontext

   use with cuts=5 gives a total runtime of

   --- MIQP status (102): integer optimal, tolerance.
   --- Cplex Time: 216.98sec (det. 155164.34 ticks)

   Solution satisfies tolerances
   MIP Solution:           62.444674    (1681459 iterations, 8326 nodes)
   Final Solve:            62.444674    (0 iterations)

   Best possible:          62.438838
   Absolute gap:            0.005837
   Relative gap:            0.000093

$offtext

set
   i /i1*i100/
   j /j1*j3/
;
alias(i,k);

set n(i,k) 'neighbors (about 10 neigbors for each i)';
n(i,k) = ord(k)>=ord(i)-5 and ord(k)<=ord(i)+5 and ord(i)<>ord(k);

parameter C(i);
c(i) = uniform(0,1);

binary variable x(i,j);
variable z;

equation
   obj
   e
;

obj.. z =e= sum((i,j,k)$n(i,k), c(k)*x(i,j)*x(k,j));
e(i)..  sum(j,x(i,j)) =e= 1;

option miqcp = cplex,threads=0;
model mod /all/;
solve mod minimizing z using miqcp;

display x.l;

Cplex automatically linearizes this:

 Classifier predicts products in MIQP should be linearized.

Interestingly, some machine learning algorithm tells Cplex what to do. (Disadvantage: this makes it a bit unpredictable whether Cplex linearizes. For more predictability set option qtolin.)

The original model has 300 variables and 100 constraints. After linearization this becomes:

MIP Presolve eliminated 1455 rows and 0 columns.
Reduced MIP has 1555 rows, 1755 columns, and 4665 nonzeros.
Reduced MIP has 1755 binaries, 0 generals, 0 SOSs, and 0 indicators.

Total time < 4 minutes. (On a small machine). Which is quite good. Of course, random data may behave very differently than real data.