2
$\begingroup$

I'm implementing on Xpress a problem with different solution proposed on a paper. The idea is to decompose a matrix $X$ into a convex sum $\sum_{t}\lambda_t M^{(t)}$, where each $M^{(t)}$ has only either $0$ or $1$, better stated we have that $M^{(t)} = (m^{(t)}_{ij})_{ij}$ and each $m_{ij}$ is a binary variable. In order to find such decomposition, we consider another continuous variable $\alpha$ and resolve the problem:

$$\begin{align} &\min\; \alpha \tag{1}\\ &\text{s.t.}\\ &\sum_{t}\lambda_t = 1 \tag{2}\\ &\sum_{j} m^{(t)}_{ij}\leq 1 \quad \forall i\;\forall t \tag{3}\\ &\sum_{i}m^{(t)}_{ij}\leq q_{i} \quad \forall j\;\forall t \tag{4}\\ &\sum_{t}\lambda_t M^{(t)} - X \geq 0 \tag{5}\\ &\sum_{t}\lambda_t M^{(t)} - X \leq \alpha\tag{6}\\ &\lambda_t,\alpha\geq 0 \end{align}$$

Equations $(5)$ and $(6)$ are problematic because they are quadratic and would yield a non convex region. We can linearize it by introducing a variable $z^{(t)}_{ij}=\lambda_{t}m^{(t)}_{ij}$ where $Z^{(t)} = (z^{(t)}_{ij})_{ij}$ which ultimately changes the equations to: $$\sum_t Z^{(t)} - X \geq 0\qquad\text{and}\qquad \sum_{t}Z^{(t)} - X \leq\alpha$$ which is now linear but requires the additional constraints: $$\forall i, j,t\hspace{2mm}: 0\leq z_{ij}^{(t)}\leq \lambda_t \qquad z_{ij}^{(t)}\geq \lambda_t + m_{ij}^{(t)}-1$$
The code runs perfectly with a non trivial output, meaning that the problem is feasible. Nontheless the new solution looses the meaning of the initial implementetion: the non linearized equation would have given as a result, $0-1$ matrixes, which is my aim actually. By linearizing, the solution looses any interpretation (as the $z$'s need now to be continuous variables). What's the best idea to set back now? Is dividing each $Z^{(t)}$ by its $\lambda_t$ and rounding the numbers a meaningful step?

$\endgroup$
5
  • 1
    $\begingroup$ Is $\lambda_t$ a nonnegative variable? Is $q_i$ a constant? $\endgroup$
    – RobPratt
    Commented Dec 9, 2022 at 20:22
  • $\begingroup$ What is the relationship between $m_{ij}$ and $M^{(t)}$? $\endgroup$
    – prubin
    Commented Dec 9, 2022 at 22:42
  • $\begingroup$ @prubin I'll edit to clarify. $\endgroup$ Commented Dec 11, 2022 at 17:10
  • $\begingroup$ @RobPratt the $\lambda_t$ are coefficients of a convex combination, so by definition they are nonnegative. The $q_i$, as well as $X$, are constants given by the problem. $\endgroup$ Commented Dec 11, 2022 at 17:17
  • 1
    $\begingroup$ The reason this is not allowed is that Xpress only supports convex MIQCPs. Any nonlinear equality constraint makes the problem immediately non-convex. $\endgroup$ Commented Dec 29, 2022 at 17:06

1 Answer 1

4
$\begingroup$

I can't help you with Xpress, but one approach is to linearize the problem by replacing the products $\lambda_t m_{ij}^{(t)}$ with new nonnegative variables $z_{ijt}$, together with constraints that enforce the product. See How to linearize the product of a binary and a non-negative continuous variable?

$\endgroup$
6
  • $\begingroup$ thank you very much for your help. Indeed I did not know about such trick but it introduces a new challenge. How do we get back to binary matrixes? $\endgroup$ Commented Jan 2, 2023 at 21:49
  • $\begingroup$ @DavideTrono You should still impose that $m_{ij}^{(t)}$ is binary. $\endgroup$
    – RobPratt
    Commented Jan 2, 2023 at 21:54
  • $\begingroup$ $m^{(t)}_{ij}$ is binary, the $z^{(t)}_{ij}$ I thought should be the same type as the $\lambda$'s. This is so because otherwise the output is: $\lambda_0=1$ (with all the remanings equal to 0) and $Z^{(0)}$ being $1$ where $X$ is non zero. Arguably okay result. $\endgroup$ Commented Jan 2, 2023 at 22:09
  • 1
    $\begingroup$ Yes, $z$ is the same type (nonnegative continuous) as $\lambda$. Your linearization is missing $z_{ij}^{(t)} \le m_{ij}^{(t)}$. $\endgroup$
    – RobPratt
    Commented Jan 2, 2023 at 22:15
  • 1
    $\begingroup$ Without the missing constraint, you are not enforcing the implication $m_{ij}^{(t)} = 0 \implies z_{ij}^{(t)} = 0$. $\endgroup$
    – RobPratt
    Commented Jan 2, 2023 at 22:22

Your Answer

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

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