I'm totally new to the world of optimization and I have an optimization problem that I think it can be formulated as Mixed Integer Quadratically Constrained Quadratic Program (QCQP) but I'm not sure of it. I know that (QCQP) has the following format: \begin{align}\min_x&\quad\frac12x^\top Hx+f^\top x\\\text{s.t.}&\quad Ax\le b\\&\quad A_{\rm eq}x=b_{\rm eq}\\&\quad\ell_b\le x\le u_b\\&\quad x^\top Qx+\ell^\top x\le r\\&\quad x_i\in\Bbb Z\\&\quad x_j\in\{0,1\}\end{align} My optimization problem can be formulated in this form but has only cross product terms between the decision variables without any quadratic term. Here is my optimization formulation: \begin{align}\min_{x_{ij},y_{ij}\,\forall i,j}&\quad\sum_{j=0}^K\sum_{i=0}^Np_{ij}y_{ij}x_{ij}\\\text{s.t.}&\quad\sum_{i=0}^Ny_{ij}x_{ij}=z_j^\max&\quad\forall j\in\{0,\cdots,K\}\\&\quad\sum_{j=0}^Kx_{ij}\le 1&\quad\forall i\in\{0,\cdots,N\}\\&\quad x_{ij}\in\{0,1\}&\quad\forall i\in\{0,\cdots,N\}\quad\text{and}\quad\forall j\in\{0,\cdots,K\}\\&\quad y^\min\le y_{ij}\le y^\max&\quad\forall i\in\{0,\cdots,N\}\quad\text{and}\quad\forall j\in\{0,\cdots,K\}\end{align} where $$x_{ij}$$ and $$y_{ij}$$ are my decision variables $$\forall i, j$$. $$z^{\max}_j \forall j$$ are some constants. $$x_{ij}$$ are binary decision variables while $$y_{ij}$$ are continuous decision variables.

I tried to formulate it and here is the $$H$$ matrix value for $$K = 1$$ and $$N = 2$$ as an example: $$\begin{equation} H = \begin{bmatrix} 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ \end{bmatrix} \end{equation}$$

Is this correct? Or do you think the problem should be linearly relaxed instead of formulating it in this way?

Rather than solving this directly as MIQCQP, you might consider linearizing the products $$y_{ij} x_{ij}$$, as shown here, yielding instead an MILP problem.
• Yes, you would use the same new variable $z_{ij}$ in place of the product $y_{ij}x_{ij}$ in both the objective and the quadratic constraint. MILP technology is more mature than MIQCQP, and I would expect the linearized formulation to solve faster even though it has a larger number of variables and constraints. Jun 22, 2021 at 20:56