6
$\begingroup$

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?

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
11
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you for your answer!. What about the objective function itself, can I linearize it using the same method applied to the constraints ? and what are the trade-offs of the linearization over solving it as MIQCQP ? I think linearizing the program would expand the number of constraints, is that Ok ? $\endgroup$
    – Ibrahim Amer
    Jun 22, 2021 at 20:34
  • 2
    $\begingroup$ 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. $\endgroup$
    – RobPratt
    Jun 22, 2021 at 20:56
  • $\begingroup$ Thank you so very much sir for this complete and detailed answer!. I really appreciate your help $\endgroup$
    – Ibrahim Amer
    Jun 23, 2021 at 14:42

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.