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?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Is $\lambda_t$ a nonnegative variable? Is $q_i$ a constant? $\endgroup$
    – RobPratt
    Dec 9, 2022 at 20:22
  • $\begingroup$ What is the relationship between $m_{ij}$ and $M^{(t)}$? $\endgroup$
    – prubin ♦
    Dec 9, 2022 at 22:42
  • $\begingroup$ @prubin I'll edit to clarify. $\endgroup$
    – Davide Trono
    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$
    – Davide Trono
    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$
    – Erwin Kalvelagen
    Dec 29, 2022 at 17:06

1 Answer 1

Reset to default
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?

Improve this answer
$\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$
    – Davide Trono
    Jan 2 at 21:49
  • $\begingroup$ @DavideTrono You should still impose that $m_{ij}^{(t)}$ is binary. $\endgroup$
    – RobPratt
    Jan 2 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$
    – Davide Trono
    Jan 2 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
    Jan 2 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
    Jan 2 at 22:22

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.