Issue in solving a large scale MIQP problem

Question

I am solving a large scale MIQP optimisation problem at each step of a model predictive control problem. The problem description is as below. \begin{align} \min_{u} \quad (x_{k}&-x_\text{ref})^{T}Q(x_{k}-x_\text{ref}) + (P_{k}-P_{\text{ref},k})^{T}R(P_{k}-P_{\text{ref},k}) \\ \text{s.t. } x_{k+1}&=Ax_{k}+Bu_{k} \\ P_{k} &= \mathbb{I}^{T}u_{k}\\ u_{k} &\in \{0.25,0.50,0.75,1.0\}\\ \underline{x}&\leq x_{k}\leq \overline{x} \end{align} where $Q$ and $R$ are positive definite, $\underline{x}$ and $\overline{x}$ represent the lower and upper bounds of $x$, $x_{ref}$ and $P_{ref}$ are the reference values at each step $k$. In addition to that, $P_{k} = \sum_{i} u_{k}^{i}$ which is the sum of all decision variables at time step $k$.

The issue that I have is, the decision variable $u$ is in $\mathbb{R}^{1000}$, i.e. the problem involves a large number of integer variables which are not even binary.

I tried solving this optimisation problem at each iteration with Gurobi but was unable to solve at all. Thereafter, I contacted the Gurobi support centre and based on their suggestions, tried tweaking parameters (MIPGap, MIPHeuristics) to find at least a feasible solution. But it also did not improve the performance of the task. On the other hand, I am in need of finding a feasible solution within 60 seconds to match the real-world application.

I would really appreciate if someone could help me in the following problems.

1. Is this problem NP-hard? if so is there any way to solve this kind of a large problem based on the formulation shown above.
2. I am familiar with McCormick envelopes and big-M relaxations, but since the decision variables are not binary, is there any way I can apply those techniques here, I mean constraint relaxations?
3. Is there any powerful solver which I can try other than Gurobi?

Thank you.

Answer 1

TL;DR: Some optimization problems are tough, and it requires a lot of work to get them solved.

First, let me answer your questions:

1. Yes, this is NP-hard, but that does not say anything about whether or not it is easy to solve. Most MIPs are NP-hard, yet they are solved extremely frequently. My favorite treatment of this comes courtesy of Paul Rubin (see here).

2. You can always convert your integers into binaries. So if you have $u \in \{0,1,2,3\}$, you can convert this into $y_k\in \{0,1\}$, where $u = \sum \limits_k ky_k$, $\sum \limits_k y_k = 1$ and $k\in\{0,1,2,3\}$. Then you can apply the traditional McCormick relaxations and big-M formulations from the textbooks. Note that you can do McCormick relaxations also for a bound integer variable.

3. I work for Gurobi, so my obvious answer is "No" :) However, this being an MPC problem gives you actually quite a bit of structure. First off, I would try to work with shorter horizon lengths and see how that degrades performance. Next, I would look into relaxing $u_k$ and seeing what type of results you get. This is going to be the LP relaxation of the problem, and from the log file you posted on Gurobi's community forum it seems that the lower bound does not move much. So this may be a good place to start.

In general, you may have to create some specialized approaches. Note though that what you are really doing here is performance tuning, and following the comments of Yair Altman, you should always have a quantitative goal when performance tuning. So e.g. Gurobi does provide you a heuristic solution extremely quickly, however the MIP gap is fairly high. So you have to see which MIP gap would be acceptable for you and then add layers of algorithms on top to achieve this performance.

EDIT: thanks to Paul Rubin and Rob Pratt for spotting mistakes in my equations.