5
$\begingroup$

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!

$\endgroup$
0

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ I agree that it is very linear, but it is not easy to solve at all. Solving with around 100 nodes (average neighbor amount of 10ish) causes the solver to stall around 40% MIP gap. $\endgroup$
    – Bob Jeans
    Jun 25, 2022 at 15:20
  • $\begingroup$ What means "very linear"? It is completely linear. I suggest to carefully study the solver log. Also, solvers may have options like mipemphasis or mipfocus that can help. $\endgroup$ Jun 25, 2022 at 15:25
  • $\begingroup$ I was using 'very' to indicate emphasis, but yes the problem is linear. I have looked through the solver logs, and I can see that the solver can identify new incumbent solution (up to a point), but the relaxed bound is very slow to improve (ie the LP relaxation). I've used different settings and Ive gotten some minor improvements, but nothing worth getting excited over. Im not sure I understand your confusion about the objective, but Ill make an edit to clarify what I can. The notation is a little fast and loose. $\endgroup$
    – Bob Jeans
    Jun 25, 2022 at 16:20
  • $\begingroup$ Erwin's point about $J$ is that your second constraint defines $V_{ij}$ only for $j\in J$ (which appears to be a small subset of $N$) while the objective function, lacking specific indices of summation, appears to be summing over all $j\in N.$ $\endgroup$
    – prubin
    Jun 25, 2022 at 16:24
  • $\begingroup$ This looks like a clustering problem, although I don't know enough about the various incarnations of clustering problems to suggest specific resources. $\endgroup$
    – prubin
    Jun 25, 2022 at 16:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.