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?
Best Answer
In group 4 you have many conditions in a 4 dimensional space. It would help tremendously if you can identify an ordering between the conditions. With an ordering I mean statements like "if the condition in constraint 8282 is satisfied, then the condition in constraints 93, 108 and 2081 are also satisfied". Given such implications, you can add redundant constraints to your problem that will strengthen the relaxed problem.