Linearization of a product of two decision variables
$begingroup$
I am trying to solve a problem that involves constraints in which products of two decision variables appear.
So far, I read that such products can be reformulated to a difference of two quadratic terms:
$x_1cdot x_2=y_1^2-y_2^2$
Where $y_1 = 0.5 cdot left( x_1+x_2 right)$ and $y_2 = 0.5 cdot left( x_1-x_2 right)$
As stated in "Model building in mathematical programming" by H.P. Williams, I tried to linearize $y_1^2$ and $y_2^2$ by piecewise approximation. When I only use two node points (one interval) for the piecewise approximation, my solvers (Gurobi 5.6.3 and CPLEX 12.5.1) are able to solve the problem, but when I introduce more node points, both conclude that the problem becomes infeasible.
I already tried SOS2 variables as well as a binary approach for the linearization of $y_1^2$ and $y_2^2$.
I also used Taylor series to directly approximate $x_1cdot x_2$ which resulted in similar results as the approximation using two node points. Since this method succeeded, I suppose that the rest of my model is feasible and only this product makes things complicated.
So my questions are:
- What can cause the infeasibility? I thought that adding more node points would be beneficial to the problem.
- Are there better ways to approximate such products? I have also experimented with a reformulation using logarithms, but this caused more computational effort and did not solve the infeasibility problem.
optimization linear-programming nonlinear-optimization
asked Jun 18 '14 at 10:55
ThomasThomas
3112
$endgroup$
add a comment |
$begingroup$
I am trying to solve a problem that involves constraints in which products of two decision variables appear.
So far, I read that such products can be reformulated to a difference of two quadratic terms:
$x_1cdot x_2=y_1^2-y_2^2$
Where $y_1 = 0.5 cdot left( x_1+x_2 right)$ and $y_2 = 0.5 cdot left( x_1-x_2 right)$
As stated in "Model building in mathematical programming" by H.P. Williams, I tried to linearize $y_1^2$ and $y_2^2$ by piecewise approximation. When I only use two node points (one interval) for the piecewise approximation, my solvers (Gurobi 5.6.3 and CPLEX 12.5.1) are able to solve the problem, but when I introduce more node points, both conclude that the problem becomes infeasible.
I already tried SOS2 variables as well as a binary approach for the linearization of $y_1^2$ and $y_2^2$.
I also used Taylor series to directly approximate $x_1cdot x_2$ which resulted in similar results as the approximation using two node points. Since this method succeeded, I suppose that the rest of my model is feasible and only this product makes things complicated.
So my questions are:
- What can cause the infeasibility? I thought that adding more node points would be beneficial to the problem.
- Are there better ways to approximate such products? I have also experimented with a reformulation using logarithms, but this caused more computational effort and did not solve the infeasibility problem.
optimization linear-programming nonlinear-optimization
asked Jun 18 '14 at 10:55
ThomasThomas
3112
$endgroup$
$begingroup$
Are your decision variables of any specific type (continuous, integer, binary)? Do they have upper and/or lower bounds?
$endgroup$
– Axel Kemper
Jun 19 '14 at 19:44
$begingroup$
Both decision variables are continuous. They are also both bounded: $0le x_1 le 0.5$ and $20 le x_2 le 80$. I also tried to scale both to be between 1 and 2, but this did not help either.
$endgroup$
– Thomas
Jun 20 '14 at 6:10
add a comment |
$begingroup$
I am trying to solve a problem that involves constraints in which products of two decision variables appear.
So far, I read that such products can be reformulated to a difference of two quadratic terms:
$x_1cdot x_2=y_1^2-y_2^2$
Where $y_1 = 0.5 cdot left( x_1+x_2 right)$ and $y_2 = 0.5 cdot left( x_1-x_2 right)$
As stated in "Model building in mathematical programming" by H.P. Williams, I tried to linearize $y_1^2$ and $y_2^2$ by piecewise approximation. When I only use two node points (one interval) for the piecewise approximation, my solvers (Gurobi 5.6.3 and CPLEX 12.5.1) are able to solve the problem, but when I introduce more node points, both conclude that the problem becomes infeasible.
I already tried SOS2 variables as well as a binary approach for the linearization of $y_1^2$ and $y_2^2$.
I also used Taylor series to directly approximate $x_1cdot x_2$ which resulted in similar results as the approximation using two node points. Since this method succeeded, I suppose that the rest of my model is feasible and only this product makes things complicated.
So my questions are:
- What can cause the infeasibility? I thought that adding more node points would be beneficial to the problem.
- Are there better ways to approximate such products? I have also experimented with a reformulation using logarithms, but this caused more computational effort and did not solve the infeasibility problem.
optimization linear-programming nonlinear-optimization
asked Jun 18 '14 at 10:55
ThomasThomas
3112
$endgroup$
I am trying to solve a problem that involves constraints in which products of two decision variables appear.
So far, I read that such products can be reformulated to a difference of two quadratic terms:
$x_1cdot x_2=y_1^2-y_2^2$
Where $y_1 = 0.5 cdot left( x_1+x_2 right)$ and $y_2 = 0.5 cdot left( x_1-x_2 right)$
As stated in "Model building in mathematical programming" by H.P. Williams, I tried to linearize $y_1^2$ and $y_2^2$ by piecewise approximation. When I only use two node points (one interval) for the piecewise approximation, my solvers (Gurobi 5.6.3 and CPLEX 12.5.1) are able to solve the problem, but when I introduce more node points, both conclude that the problem becomes infeasible.
I already tried SOS2 variables as well as a binary approach for the linearization of $y_1^2$ and $y_2^2$.
I also used Taylor series to directly approximate $x_1cdot x_2$ which resulted in similar results as the approximation using two node points. Since this method succeeded, I suppose that the rest of my model is feasible and only this product makes things complicated.
So my questions are:
- What can cause the infeasibility? I thought that adding more node points would be beneficial to the problem.
- Are there better ways to approximate such products? I have also experimented with a reformulation using logarithms, but this caused more computational effort and did not solve the infeasibility problem.
optimization linear-programming nonlinear-optimization
optimization linear-programming nonlinear-optimization
asked Jun 18 '14 at 10:55
ThomasThomas
3112
asked Jun 18 '14 at 10:55
ThomasThomas
3112
asked Jun 18 '14 at 10:55
ThomasThomas
3112
asked Jun 18 '14 at 10:55
ThomasThomas
3112
asked Jun 18 '14 at 10:55
ThomasThomas
3112
3112
$begingroup$
Are your decision variables of any specific type (continuous, integer, binary)? Do they have upper and/or lower bounds?
$endgroup$
– Axel Kemper
Jun 19 '14 at 19:44
$begingroup$
Both decision variables are continuous. They are also both bounded: $0le x_1 le 0.5$ and $20 le x_2 le 80$. I also tried to scale both to be between 1 and 2, but this did not help either.
$endgroup$
– Thomas
Jun 20 '14 at 6:10
add a comment |
$begingroup$
Are your decision variables of any specific type (continuous, integer, binary)? Do they have upper and/or lower bounds?
$endgroup$
– Axel Kemper
Jun 19 '14 at 19:44
$begingroup$
Both decision variables are continuous. They are also both bounded: $0le x_1 le 0.5$ and $20 le x_2 le 80$. I also tried to scale both to be between 1 and 2, but this did not help either.
$endgroup$
– Thomas
Jun 20 '14 at 6:10
$begingroup$
Are your decision variables of any specific type (continuous, integer, binary)? Do they have upper and/or lower bounds?
$endgroup$
– Axel Kemper
Jun 19 '14 at 19:44
$begingroup$
Are your decision variables of any specific type (continuous, integer, binary)? Do they have upper and/or lower bounds?
$endgroup$
– Axel Kemper
Jun 19 '14 at 19:44
$begingroup$
Both decision variables are continuous. They are also both bounded: $0le x_1 le 0.5$ and $20 le x_2 le 80$. I also tried to scale both to be between 1 and 2, but this did not help either.
$endgroup$
– Thomas
Jun 20 '14 at 6:10
$begingroup$
Both decision variables are continuous. They are also both bounded: $0le x_1 le 0.5$ and $20 le x_2 le 80$. I also tried to scale both to be between 1 and 2, but this did not help either.
$endgroup$
– Thomas
Jun 20 '14 at 6:10
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
The AIMMS Modelling Guide in section 7.7 provides the following hint for bounded variables:
answered Jun 20 '14 at 6:51
Axel KemperAxel Kemper
3,30111418
$endgroup$
$begingroup$
Well, this is pretty much exactly what I did. As mentioned above, this works fine for me, when I only use 2 node points for approximating $y_1^2$ and $y_2^2$. But the problem does not solve any more, if I introduce more node points, attempting to approximate the parabolas better.
$endgroup$
– Thomas
Jun 20 '14 at 9:29
$begingroup$
And things don't improve if you make use of the bounds?
$endgroup$
– Axel Kemper
Jun 20 '14 at 10:05
$begingroup$
The above mentioned approximation with two points used these bounds. The larger valued node point represented the upper bound, the lower valued node point the lower bound. Since this approximation suffers from a large error between the real function and the approximation, I tried to introduce more node points (I used an equidistant grid), but as soon as I introduced even one more point, the problem became infeasible (according to CPLEX and GUROBI)
$endgroup$
– Thomas
Jun 20 '14 at 11:39
add a comment |
$begingroup$
Have a look on enter link description here. This article introduces 10 methods for your problem. on page 5, the authors introduce SOS procedure for bilinear terms.
answered Jul 9 '17 at 5:05
Esmaeel FazeliEsmaeel Fazeli
62
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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%2f838340%2flinearization-of-a-product-of-two-decision-variables%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The AIMMS Modelling Guide in section 7.7 provides the following hint for bounded variables:
answered Jun 20 '14 at 6:51
Axel KemperAxel Kemper
3,30111418
$endgroup$
$begingroup$
Well, this is pretty much exactly what I did. As mentioned above, this works fine for me, when I only use 2 node points for approximating $y_1^2$ and $y_2^2$. But the problem does not solve any more, if I introduce more node points, attempting to approximate the parabolas better.
$endgroup$
– Thomas
Jun 20 '14 at 9:29
$begingroup$
And things don't improve if you make use of the bounds?
$endgroup$
– Axel Kemper
Jun 20 '14 at 10:05
$begingroup$
The above mentioned approximation with two points used these bounds. The larger valued node point represented the upper bound, the lower valued node point the lower bound. Since this approximation suffers from a large error between the real function and the approximation, I tried to introduce more node points (I used an equidistant grid), but as soon as I introduced even one more point, the problem became infeasible (according to CPLEX and GUROBI)
$endgroup$
– Thomas
Jun 20 '14 at 11:39
add a comment |
$begingroup$
The AIMMS Modelling Guide in section 7.7 provides the following hint for bounded variables:
answered Jun 20 '14 at 6:51
Axel KemperAxel Kemper
3,30111418
$endgroup$
$begingroup$
Well, this is pretty much exactly what I did. As mentioned above, this works fine for me, when I only use 2 node points for approximating $y_1^2$ and $y_2^2$. But the problem does not solve any more, if I introduce more node points, attempting to approximate the parabolas better.
$endgroup$
– Thomas
Jun 20 '14 at 9:29
$begingroup$
And things don't improve if you make use of the bounds?
$endgroup$
– Axel Kemper
Jun 20 '14 at 10:05
$begingroup$
The above mentioned approximation with two points used these bounds. The larger valued node point represented the upper bound, the lower valued node point the lower bound. Since this approximation suffers from a large error between the real function and the approximation, I tried to introduce more node points (I used an equidistant grid), but as soon as I introduced even one more point, the problem became infeasible (according to CPLEX and GUROBI)
$endgroup$
– Thomas
Jun 20 '14 at 11:39
add a comment |
$begingroup$
The AIMMS Modelling Guide in section 7.7 provides the following hint for bounded variables:
answered Jun 20 '14 at 6:51
Axel KemperAxel Kemper
3,30111418
$endgroup$
The AIMMS Modelling Guide in section 7.7 provides the following hint for bounded variables:
answered Jun 20 '14 at 6:51
Axel KemperAxel Kemper
3,30111418
answered Jun 20 '14 at 6:51
Axel KemperAxel Kemper
3,30111418
answered Jun 20 '14 at 6:51
Axel KemperAxel Kemper
3,30111418
answered Jun 20 '14 at 6:51
Axel KemperAxel Kemper
3,30111418
3,30111418
$begingroup$
Well, this is pretty much exactly what I did. As mentioned above, this works fine for me, when I only use 2 node points for approximating $y_1^2$ and $y_2^2$. But the problem does not solve any more, if I introduce more node points, attempting to approximate the parabolas better.
$endgroup$
– Thomas
Jun 20 '14 at 9:29
$begingroup$
And things don't improve if you make use of the bounds?
$endgroup$
– Axel Kemper
Jun 20 '14 at 10:05
$begingroup$
The above mentioned approximation with two points used these bounds. The larger valued node point represented the upper bound, the lower valued node point the lower bound. Since this approximation suffers from a large error between the real function and the approximation, I tried to introduce more node points (I used an equidistant grid), but as soon as I introduced even one more point, the problem became infeasible (according to CPLEX and GUROBI)
$endgroup$
– Thomas
Jun 20 '14 at 11:39
add a comment |
$begingroup$
Well, this is pretty much exactly what I did. As mentioned above, this works fine for me, when I only use 2 node points for approximating $y_1^2$ and $y_2^2$. But the problem does not solve any more, if I introduce more node points, attempting to approximate the parabolas better.
$endgroup$
– Thomas
Jun 20 '14 at 9:29
$begingroup$
And things don't improve if you make use of the bounds?
$endgroup$
– Axel Kemper
Jun 20 '14 at 10:05
$begingroup$
The above mentioned approximation with two points used these bounds. The larger valued node point represented the upper bound, the lower valued node point the lower bound. Since this approximation suffers from a large error between the real function and the approximation, I tried to introduce more node points (I used an equidistant grid), but as soon as I introduced even one more point, the problem became infeasible (according to CPLEX and GUROBI)
$endgroup$
– Thomas
Jun 20 '14 at 11:39
$begingroup$
Well, this is pretty much exactly what I did. As mentioned above, this works fine for me, when I only use 2 node points for approximating $y_1^2$ and $y_2^2$. But the problem does not solve any more, if I introduce more node points, attempting to approximate the parabolas better.
$endgroup$
– Thomas
Jun 20 '14 at 9:29
$begingroup$
Well, this is pretty much exactly what I did. As mentioned above, this works fine for me, when I only use 2 node points for approximating $y_1^2$ and $y_2^2$. But the problem does not solve any more, if I introduce more node points, attempting to approximate the parabolas better.
$endgroup$
– Thomas
Jun 20 '14 at 9:29
$begingroup$
And things don't improve if you make use of the bounds?
$endgroup$
– Axel Kemper
Jun 20 '14 at 10:05
$begingroup$
And things don't improve if you make use of the bounds?
$endgroup$
– Axel Kemper
Jun 20 '14 at 10:05
$begingroup$
The above mentioned approximation with two points used these bounds. The larger valued node point represented the upper bound, the lower valued node point the lower bound. Since this approximation suffers from a large error between the real function and the approximation, I tried to introduce more node points (I used an equidistant grid), but as soon as I introduced even one more point, the problem became infeasible (according to CPLEX and GUROBI)
$endgroup$
– Thomas
Jun 20 '14 at 11:39
$begingroup$
The above mentioned approximation with two points used these bounds. The larger valued node point represented the upper bound, the lower valued node point the lower bound. Since this approximation suffers from a large error between the real function and the approximation, I tried to introduce more node points (I used an equidistant grid), but as soon as I introduced even one more point, the problem became infeasible (according to CPLEX and GUROBI)
$endgroup$
– Thomas
Jun 20 '14 at 11:39
add a comment |
$begingroup$
Have a look on enter link description here. This article introduces 10 methods for your problem. on page 5, the authors introduce SOS procedure for bilinear terms.
answered Jul 9 '17 at 5:05
Esmaeel FazeliEsmaeel Fazeli
62
$endgroup$
add a comment |
$begingroup$
Have a look on enter link description here. This article introduces 10 methods for your problem. on page 5, the authors introduce SOS procedure for bilinear terms.
answered Jul 9 '17 at 5:05
Esmaeel FazeliEsmaeel Fazeli
62
$endgroup$
add a comment |
$begingroup$
Have a look on enter link description here. This article introduces 10 methods for your problem. on page 5, the authors introduce SOS procedure for bilinear terms.
answered Jul 9 '17 at 5:05
Esmaeel FazeliEsmaeel Fazeli
62
$endgroup$
Have a look on enter link description here. This article introduces 10 methods for your problem. on page 5, the authors introduce SOS procedure for bilinear terms.
answered Jul 9 '17 at 5:05
Esmaeel FazeliEsmaeel Fazeli
62
answered Jul 9 '17 at 5:05
Esmaeel FazeliEsmaeel Fazeli
62
answered Jul 9 '17 at 5:05
Esmaeel FazeliEsmaeel Fazeli
62
answered Jul 9 '17 at 5:05
Esmaeel FazeliEsmaeel Fazeli
62
62
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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%2f838340%2flinearization-of-a-product-of-two-decision-variables%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
$begingroup$
Are your decision variables of any specific type (continuous, integer, binary)? Do they have upper and/or lower bounds?
$endgroup$
– Axel Kemper
Jun 19 '14 at 19:44
$begingroup$
Both decision variables are continuous. They are also both bounded: $0le x_1 le 0.5$ and $20 le x_2 le 80$. I also tried to scale both to be between 1 and 2, but this did not help either.
$endgroup$
– Thomas
Jun 20 '14 at 6:10