Mixing
MIQP problem slow to solve: how to rewrite it?
up vote
2
down vote
favorite
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?
optimization nonlinear-optimization quadratic-forms mixed-integer-programming
asked Nov 15 at 23:02
STF
40420
This question has an open bounty worth +50
reputation from STF ending in 5 days.
The question is widely applicable to a large audience. A detailed canonical answer is required to address all the concerns.
add a comment |
up vote
2
down vote
favorite
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?
optimization nonlinear-optimization quadratic-forms mixed-integer-programming
asked Nov 15 at 23:02
STF
40420
This question has an open bounty worth +50
reputation from STF ending in 5 days.
The question is widely applicable to a large audience. A detailed canonical answer is required to address all the concerns.
add a comment |
up vote
2
down vote
favorite
up vote
2
down vote
favorite
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?
optimization nonlinear-optimization quadratic-forms mixed-integer-programming
asked Nov 15 at 23:02
STF
40420
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?
optimization nonlinear-optimization quadratic-forms mixed-integer-programming
optimization nonlinear-optimization quadratic-forms mixed-integer-programming
asked Nov 15 at 23:02
STF
40420
asked Nov 15 at 23:02
STF
40420
asked Nov 15 at 23:02
STF
40420
asked Nov 15 at 23:02
STF
40420
asked Nov 15 at 23:02
STF
40420
40420
This question has an open bounty worth +50
reputation from STF ending in 5 days.
The question is widely applicable to a large audience. A detailed canonical answer is required to address all the concerns.
This question has an open bounty worth +50
reputation from STF ending in 5 days.
The question is widely applicable to a large audience. A detailed canonical answer is required to address all the concerns.
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
up vote
0
down vote
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.
answered yesterday
LinAlg
7,5741520
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
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.
answered yesterday
LinAlg
7,5741520
add a comment |
up vote
0
down vote
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.
answered yesterday
LinAlg
7,5741520
add a comment |
up vote
0
down vote
up vote
0
down vote
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.
answered yesterday
LinAlg
7,5741520
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.
answered yesterday
LinAlg
7,5741520
answered yesterday
LinAlg
7,5741520
answered yesterday
LinAlg
7,5741520
answered yesterday
LinAlg
7,5741520
7,5741520
add a comment |
add a comment |
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3000451%2fmiqp-problem-slow-to-solve-how-to-rewrite-it%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
