5
$\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?

$\endgroup$
1
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.

$\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 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 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 at 14:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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