Krdytkyu

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 $4times 1$, $v$ is of size $4times 1$, $q$ is of size $225times 1$, $w$ is of size $225times 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_kBig]^2+ sum_{k=7}^{12}Big[a_k - f_{k-6}(w)*b_kBig]^2
$$

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

Constraints:

(Group 1)

$begin{cases}
u_1in {-1,1}\
v_1in {-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 0Big] text{ or } Big[s_{i,1}(u)leq 0 text{ and }s_{i,2}(u)leq 0Big] 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 0Big] text{ or } Big[s_{i,1}(v)leq 0 text{ and }s_{i,2}(v)leq 0Big] 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_2in [-5,5], u_3in [-5,5], u_4in [-5,5], v_2in [-5,5], u_3in [-5,5], u_4in [-5,5]\
qin [0,1]^{225}\
win [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?

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.