(Believed to be Optimal) Solution found super quickly, takes forever to certify it with dual
Answered
I am solving a QCQP with a non-PSD matrix in the objective with the NonConvex parameter set to 2. When trying to solve my model, it find a feasible solution quickly (~2 seconds) and while the duality gap decreases slowly (i.e: ~50% to ~45% over several hours or ~30% to ~17%), the dual solution is the only one improving the duality gap, the primal solution stays the same (see photo below). I managed to solve a small instance to optimality that showed that the initial feasible solution was indeed optimal (second photo below).
This phenomenon has been incredibly consist across instance size and parameters and although I found some other related posts mentioning tuning certain search parameters (MIP Focus, Heuristic, Preserve, etc), it was not a drastic change.
Does anyone have any experience with such behaviour?
Some more info: I am solving a Multi-commodity flow variant where certain flow costs are variables themselves along with some quadratic constraints. The resulting model is a QCQP but more specifically a bilinear objective and constraints, which is why I solve it with the NonConvex parameter. I am attaching a log of a run for 100 seconds.
-
Hi Gabriel,
Improving the dual bound is often the hardest part of a nonconvex optimization run. Especially when the number of bilinear terms is big (which it is in your instance 17160 bilinear terms).
In your case, it looks like you should try to provide tight variable bounds for all variables participating in nonlinear terms, i.e., for all variables occuring in a \(x\cdot y\) and \(x^2\) term. These bounds can be motivated by the practical application you are modelling or simply by an educated guess, e.g., "I will never produce more than 100 items of product X". This should already improve the dual bound.
You could also try reformulating your nonlinear terms. For example, it does make a difference to model
\[\begin{align*}
z &= x_1 + y_1\\
u &= x_2 + y_2\\
w &= z\cdot u
\end{align*}\]vs
\[\begin{align*}
w = x_1\cdot x_2 + x_1 \cdot y_2 + y_1\cdot x_2 + y_1 \cdot y2
\end{align*}\]Unfortunately, it is most often not possible to tell which of the two formulations works best for a particular model. Thus, you would have to experiment with different formulations yourself.
Best regards,
Jaromił0
Please sign in to leave a comment.
Comments
1 comment