# MIQP problem slow to solve: how to rewrite it?

I am looking for suggestions on how to rewrite a MIQP problem.

Let me firstly introduce the problem

Notation:

The unknown vector is $$x$$ with size $$(4*2+225*2)\times 1$$.

We can think of the vector $$x$$ as composed of $$4$$ subvectors $$u,v,q,w$$ where $$u$$ is of size $$4\times 1$$, $$v$$ is of size $$4\times 1$$, $$q$$ is of size $$225\times 1$$, $$w$$ is of size $$225\times 1$$.

$$x_i$$ denotes the $$ith$$ component of $$x$$.

$$\{a_k,b_k\}_{k=1}^{12}, t_1, t_2$$ are known parameters.

Objective function to be minimised:

$$f(x)\equiv \sum_{k=1}^{6}\Big[a_k - f_k(q)*b_k\Big]^2+ \sum_{k=7}^{12}\Big[a_k - f_{k-6}(w)*b_k\Big]^2$$

where $$f_1,..., f_{6}$$ are linear functions.

Constraints:

(Group 1)

$$\begin{cases} u_1\in \{-1,1\}\\ v_1\in \{-1,1\}\\ u_2+v_3=t_1\\ u_3+v_2=t_2 \end{cases}$$

(Group 2)

for $$i=1,...,50$$: $$g_i(q)=0$$ where $$g_i$$ is a linear function

for $$i=1,...,50$$: $$g_i(w)=0$$ where $$g_i$$ is a linear function

(Group 3)

for $$i=1,...,78$$: $$r_i(u)=0$$ $$\Rightarrow$$ $$l_{i,j}(q)=0$$ for $$j=1,...,28$$ where $$r_i, l_{i,j}$$ are linear functions

for $$i=1,...,78$$: $$r_i(v)=0$$ $$\Rightarrow$$ $$l_{i,j}(w)=0$$ for $$j=1,...,28$$ where $$r_i, l_{i,j}$$ are linear functions

(Group 4)

for $$i=1,...,25200$$: $$\Big[s_{i,1}(u)\geq 0 \text{ and }s_{i,2}(u)\geq 0\Big] \text{ or } \Big[s_{i,1}(u)\leq 0 \text{ and }s_{i,2}(u)\leq 0\Big] \Rightarrow p_i(q)\geq 0$$ where $$s_{i,1}, s_{i,2}, p_i$$ are linear functions

for $$i=1,...,25200$$: $$\Big[s_{i,1}(v)\geq 0 \text{ and }s_{i,2}(v)\geq 0\Big] \text{ or } \Big[s_{i,1}(v)\leq 0 \text{ and }s_{i,2}(v)\leq 0\Big] \Rightarrow p_i(w)\geq 0$$ where $$s_{i,1}, s_{i,2}, p_i$$ are linear functions

Lower bounds and upper bounds:

$$\begin{cases} u_2\in [-5,5], u_3\in [-5,5], u_4\in [-5,5], v_2\in [-5,5], u_3\in [-5,5], u_4\in [-5,5]\\ q\in [0,1]^{225}\\ w\in [0,1]^{225}\\ \end{cases}$$

This problem can be rewritten as Mixed Integer Quadratic Programming (MIQP). However, the problem is very slow to solve (using e.g., Gurobi).

I spent a lot of time in tuning the parameters of the Gurobi solver to gain speed but improvements are minor.

I guess that the main problems are caused by the constraints in Group 3 and Group 4. I rewrite them using big-M transformation. They require introducing many binary variables (for group 3 we need to introduce $$(3*78)*2$$ binary variables; for group 4 we need to introduce $$(2+4)*25200*2$$ binary variables).

I'm being very careful in setting the $$M$$ constants as tight as possible.

Hence: do you have any better suggestion to solve my problem?