2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for the answer. I've posted another more specific question on the same topic, to be sure that I've understood your advice. Could you help if you have some time? Thanks math.stackexchange.com/questions/3023993/… $\endgroup$ – STF Dec 3 '18 at 12:39

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.