Mixing
Why is the following not a a linear programming problem?
3
$begingroup$
$$begin{array}{ll} text{maximize} & 3x + 3y − 30\ text{subject to} & |x−2|−|y| leq 5end{array}$$
This is totally a LLP to me, just not in its standard form. I really don't know why it is not? What I am missing? Thanks!
linear-programming
edited Feb 3 at 9:56
Rodrigo de Azevedo
13.1k41962
asked Feb 2 at 21:50
Cathy Cathy
30529
$endgroup$
add a comment |
3
$begingroup$
$$begin{array}{ll} text{maximize} & 3x + 3y − 30\ text{subject to} & |x−2|−|y| leq 5end{array}$$
This is totally a LLP to me, just not in its standard form. I really don't know why it is not? What I am missing? Thanks!
linear-programming
edited Feb 3 at 9:56
Rodrigo de Azevedo
13.1k41962
asked Feb 2 at 21:50
Cathy Cathy
30529
$endgroup$
$begingroup$
Notice that the constraint is not a linear function of your decision variables.
$endgroup$
– VHarisop
Feb 2 at 21:59
$begingroup$
@VHarisop Why the constraint is not linear? Is it because the absolute value? If it is, why can not remove the absolute value by some tricks?
$endgroup$
– Cathy
Feb 2 at 22:02
$begingroup$
Yes, the absolute values are the reason. You can't rely on any tricks to "remove" the absolute value (e.g. if you try equating it with a linear function you will end up with multiple coefficients depending on the values of $x$, $y$).
$endgroup$
– VHarisop
Feb 2 at 22:09
$begingroup$
@VHarisop I'm confused. Since it gives an example that maximize 3x + 3y − 30 subject to |x−2|+|y|≤5 is a LLP. Why only change the "+" to "-", then it is not?
$endgroup$
– Cathy
Feb 2 at 22:15
1
$begingroup$
I would say that neither problem (with the + or the -) "is" a linear programming problem. It's just that the one with the + coincidentally happens to be equivalent to a LPP, and (as the answer shows) the one with the - does not.
$endgroup$
– Micah
Feb 3 at 0:32
add a comment |
3
3
3
$begingroup$
$$begin{array}{ll} text{maximize} & 3x + 3y − 30\ text{subject to} & |x−2|−|y| leq 5end{array}$$
This is totally a LLP to me, just not in its standard form. I really don't know why it is not? What I am missing? Thanks!
linear-programming
edited Feb 3 at 9:56
Rodrigo de Azevedo
13.1k41962
asked Feb 2 at 21:50
Cathy Cathy
30529
$endgroup$
$$begin{array}{ll} text{maximize} & 3x + 3y − 30\ text{subject to} & |x−2|−|y| leq 5end{array}$$
This is totally a LLP to me, just not in its standard form. I really don't know why it is not? What I am missing? Thanks!
linear-programming
linear-programming
edited Feb 3 at 9:56
Rodrigo de Azevedo
13.1k41962
asked Feb 2 at 21:50
Cathy Cathy
30529
edited Feb 3 at 9:56
Rodrigo de Azevedo
13.1k41962
asked Feb 2 at 21:50
Cathy Cathy
30529
edited Feb 3 at 9:56
Rodrigo de Azevedo
13.1k41962
edited Feb 3 at 9:56
Rodrigo de Azevedo
13.1k41962
edited Feb 3 at 9:56
Rodrigo de Azevedo
13.1k41962
13.1k41962
asked Feb 2 at 21:50
Cathy Cathy
30529
asked Feb 2 at 21:50
Cathy Cathy
30529
asked Feb 2 at 21:50
Cathy Cathy
30529
30529
$begingroup$
Notice that the constraint is not a linear function of your decision variables.
$endgroup$
– VHarisop
Feb 2 at 21:59
$begingroup$
@VHarisop Why the constraint is not linear? Is it because the absolute value? If it is, why can not remove the absolute value by some tricks?
$endgroup$
– Cathy
Feb 2 at 22:02
$begingroup$
Yes, the absolute values are the reason. You can't rely on any tricks to "remove" the absolute value (e.g. if you try equating it with a linear function you will end up with multiple coefficients depending on the values of $x$, $y$).
$endgroup$
– VHarisop
Feb 2 at 22:09
$begingroup$
@VHarisop I'm confused. Since it gives an example that maximize 3x + 3y − 30 subject to |x−2|+|y|≤5 is a LLP. Why only change the "+" to "-", then it is not?
$endgroup$
– Cathy
Feb 2 at 22:15
1
$begingroup$
I would say that neither problem (with the + or the -) "is" a linear programming problem. It's just that the one with the + coincidentally happens to be equivalent to a LPP, and (as the answer shows) the one with the - does not.
$endgroup$
– Micah
Feb 3 at 0:32
add a comment |
$begingroup$
Notice that the constraint is not a linear function of your decision variables.
$endgroup$
– VHarisop
Feb 2 at 21:59
$begingroup$
@VHarisop Why the constraint is not linear? Is it because the absolute value? If it is, why can not remove the absolute value by some tricks?
$endgroup$
– Cathy
Feb 2 at 22:02
$begingroup$
Yes, the absolute values are the reason. You can't rely on any tricks to "remove" the absolute value (e.g. if you try equating it with a linear function you will end up with multiple coefficients depending on the values of $x$, $y$).
$endgroup$
– VHarisop
Feb 2 at 22:09
$begingroup$
@VHarisop I'm confused. Since it gives an example that maximize 3x + 3y − 30 subject to |x−2|+|y|≤5 is a LLP. Why only change the "+" to "-", then it is not?
$endgroup$
– Cathy
Feb 2 at 22:15
1
$begingroup$
I would say that neither problem (with the + or the -) "is" a linear programming problem. It's just that the one with the + coincidentally happens to be equivalent to a LPP, and (as the answer shows) the one with the - does not.
$endgroup$
– Micah
Feb 3 at 0:32
$begingroup$
Notice that the constraint is not a linear function of your decision variables.
$endgroup$
– VHarisop
Feb 2 at 21:59
$begingroup$
Notice that the constraint is not a linear function of your decision variables.
$endgroup$
– VHarisop
Feb 2 at 21:59
$begingroup$
@VHarisop Why the constraint is not linear? Is it because the absolute value? If it is, why can not remove the absolute value by some tricks?
$endgroup$
– Cathy
Feb 2 at 22:02
$begingroup$
@VHarisop Why the constraint is not linear? Is it because the absolute value? If it is, why can not remove the absolute value by some tricks?
$endgroup$
– Cathy
Feb 2 at 22:02
$begingroup$
Yes, the absolute values are the reason. You can't rely on any tricks to "remove" the absolute value (e.g. if you try equating it with a linear function you will end up with multiple coefficients depending on the values of $x$, $y$).
$endgroup$
– VHarisop
Feb 2 at 22:09
$begingroup$
Yes, the absolute values are the reason. You can't rely on any tricks to "remove" the absolute value (e.g. if you try equating it with a linear function you will end up with multiple coefficients depending on the values of $x$, $y$).
$endgroup$
– VHarisop
Feb 2 at 22:09
$begingroup$
@VHarisop I'm confused. Since it gives an example that maximize 3x + 3y − 30 subject to |x−2|+|y|≤5 is a LLP. Why only change the "+" to "-", then it is not?
$endgroup$
– Cathy
Feb 2 at 22:15
$begingroup$
@VHarisop I'm confused. Since it gives an example that maximize 3x + 3y − 30 subject to |x−2|+|y|≤5 is a LLP. Why only change the "+" to "-", then it is not?
$endgroup$
– Cathy
Feb 2 at 22:15
1
1
$begingroup$
I would say that neither problem (with the + or the -) "is" a linear programming problem. It's just that the one with the + coincidentally happens to be equivalent to a LPP, and (as the answer shows) the one with the - does not.
$endgroup$
– Micah
Feb 3 at 0:32
$begingroup$
I would say that neither problem (with the + or the -) "is" a linear programming problem. It's just that the one with the + coincidentally happens to be equivalent to a LPP, and (as the answer shows) the one with the - does not.
$endgroup$
– Micah
Feb 3 at 0:32
add a comment |
1 Answer
1
active
oldest
votes
2
$begingroup$
The optimisation problem in the question is NOT an LPP because an LPP has convex feasible region. We can easily check that
$$S = {(x,y)inBbb{R}^2 mid |x-2|-|y| le 5}$$ is not convex as $(10,pm3) in S$, but $(10,0) notin S$.
This problem can be converted into an LPP by the usual trick in (2).
- make the substitution $u = x-2$
- split each decision variables into its positive and negative components.
begin{alignat}{2}
y^+ &:= frac{|y|+y}{2} &qquad y^- &:= frac{|y|-y}{2} \
u^+ &:= frac{|u|+u}{2} & u^- &:= frac{|u|-u}{2} \
therefore y &= y^+ - y^- & |y| &= y^+ + y^- \
u &= u^+ - u^- & |u| &= u^+ + u^-
end{alignat}
Then the objective function and the constraints become $3u^+ - 3u^- + 3y^+ - 3y^- - 24$ and
begin{cases}
u^+ + u^- - y^+ - y^- &le 5 \
u^+, u^-, y^+, y^- &ge 0 \
u^+ u^- = y^+ y^- = 0
end{cases}
respectively.
answered Feb 2 at 23:34
GNUSupporter 8964民主女神 地下教會GNUSupporter 8964民主女神 地下教會
14.1k82651
$endgroup$
1
$begingroup$
your 'trick' is wrong (you can let $y^+ to infty$), you cannot convert it into an LPP without introducing binaries
$endgroup$
– LinAlg
Feb 3 at 1:24
$begingroup$
@LinAlg I've a careless mistake when splitting variables in the middle. I meant $u$ instead of $x$. Apart from that, the trick is a usual one. You may see this, for example, in math.stackexchange.com/a/432029/290189.
$endgroup$
– GNUSupporter 8964民主女神 地下教會
Feb 3 at 9:36
$begingroup$
The original maximisation problem is unbounded (by fixing $x$ and letting $y to +infty$). Your suggestion ($y^+ to +infty$) also leads to the same result. I don't see how this shows that my trick is wrong. I'm missing something?
$endgroup$
– GNUSupporter 8964民主女神 地下教會
Feb 3 at 9:46
$begingroup$
that your reformulation is wrong becomes more apparent when you add an extra constraint that $y=0$ ($y^+ - y^- = 0$). The original problem is bounded but your reformulated problem is not (set $y^+ = y^-$, letting those go to infinity, the first constraint no longer restricts $x$).
$endgroup$
– LinAlg
Feb 3 at 13:30
$begingroup$
@LinAlg Why you say that the original problem bounded? An arbitrarily large $y$ satisfies the orginal constraint. Since the coefficient of $y$ in the objective function is positive, the problem is unbounded. I've never introduced $y=0$ as a constraint. It's $y^+ y^-=0$.
$endgroup$
– GNUSupporter 8964民主女神 地下教會
Feb 3 at 15:24
|
show 2 more comments
Your Answer
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
});
}
});
draft saved
draft discarded
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%2f3097850%2fwhy-is-the-following-not-a-a-linear-programming-problem%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
2
$begingroup$
The optimisation problem in the question is NOT an LPP because an LPP has convex feasible region. We can easily check that
$$S = {(x,y)inBbb{R}^2 mid |x-2|-|y| le 5}$$ is not convex as $(10,pm3) in S$, but $(10,0) notin S$.
This problem can be converted into an LPP by the usual trick in (2).
- make the substitution $u = x-2$
- split each decision variables into its positive and negative components.
begin{alignat}{2}
y^+ &:= frac{|y|+y}{2} &qquad y^- &:= frac{|y|-y}{2} \
u^+ &:= frac{|u|+u}{2} & u^- &:= frac{|u|-u}{2} \
therefore y &= y^+ - y^- & |y| &= y^+ + y^- \
u &= u^+ - u^- & |u| &= u^+ + u^-
end{alignat}
Then the objective function and the constraints become $3u^+ - 3u^- + 3y^+ - 3y^- - 24$ and
begin{cases}
u^+ + u^- - y^+ - y^- &le 5 \
u^+, u^-, y^+, y^- &ge 0 \
u^+ u^- = y^+ y^- = 0
end{cases}
respectively.
answered Feb 2 at 23:34
GNUSupporter 8964民主女神 地下教會GNUSupporter 8964民主女神 地下教會
14.1k82651
$endgroup$
1
$begingroup$
your 'trick' is wrong (you can let $y^+ to infty$), you cannot convert it into an LPP without introducing binaries
$endgroup$
– LinAlg
Feb 3 at 1:24
$begingroup$
@LinAlg I've a careless mistake when splitting variables in the middle. I meant $u$ instead of $x$. Apart from that, the trick is a usual one. You may see this, for example, in math.stackexchange.com/a/432029/290189.
$endgroup$
– GNUSupporter 8964民主女神 地下教會
Feb 3 at 9:36
$begingroup$
The original maximisation problem is unbounded (by fixing $x$ and letting $y to +infty$). Your suggestion ($y^+ to +infty$) also leads to the same result. I don't see how this shows that my trick is wrong. I'm missing something?
$endgroup$
– GNUSupporter 8964民主女神 地下教會
Feb 3 at 9:46
$begingroup$
that your reformulation is wrong becomes more apparent when you add an extra constraint that $y=0$ ($y^+ - y^- = 0$). The original problem is bounded but your reformulated problem is not (set $y^+ = y^-$, letting those go to infinity, the first constraint no longer restricts $x$).
$endgroup$
– LinAlg
Feb 3 at 13:30
$begingroup$
@LinAlg Why you say that the original problem bounded? An arbitrarily large $y$ satisfies the orginal constraint. Since the coefficient of $y$ in the objective function is positive, the problem is unbounded. I've never introduced $y=0$ as a constraint. It's $y^+ y^-=0$.
$endgroup$
– GNUSupporter 8964民主女神 地下教會
Feb 3 at 15:24
|
show 2 more comments
2
$begingroup$
The optimisation problem in the question is NOT an LPP because an LPP has convex feasible region. We can easily check that
$$S = {(x,y)inBbb{R}^2 mid |x-2|-|y| le 5}$$ is not convex as $(10,pm3) in S$, but $(10,0) notin S$.
This problem can be converted into an LPP by the usual trick in (2).
- make the substitution $u = x-2$
- split each decision variables into its positive and negative components.
begin{alignat}{2}
y^+ &:= frac{|y|+y}{2} &qquad y^- &:= frac{|y|-y}{2} \
u^+ &:= frac{|u|+u}{2} & u^- &:= frac{|u|-u}{2} \
therefore y &= y^+ - y^- & |y| &= y^+ + y^- \
u &= u^+ - u^- & |u| &= u^+ + u^-
end{alignat}
Then the objective function and the constraints become $3u^+ - 3u^- + 3y^+ - 3y^- - 24$ and
begin{cases}
u^+ + u^- - y^+ - y^- &le 5 \
u^+, u^-, y^+, y^- &ge 0 \
u^+ u^- = y^+ y^- = 0
end{cases}
respectively.
answered Feb 2 at 23:34
GNUSupporter 8964民主女神 地下教會GNUSupporter 8964民主女神 地下教會
14.1k82651
$endgroup$
1
$begingroup$
your 'trick' is wrong (you can let $y^+ to infty$), you cannot convert it into an LPP without introducing binaries
$endgroup$
– LinAlg
Feb 3 at 1:24
$begingroup$
@LinAlg I've a careless mistake when splitting variables in the middle. I meant $u$ instead of $x$. Apart from that, the trick is a usual one. You may see this, for example, in math.stackexchange.com/a/432029/290189.
$endgroup$
– GNUSupporter 8964民主女神 地下教會
Feb 3 at 9:36
$begingroup$
The original maximisation problem is unbounded (by fixing $x$ and letting $y to +infty$). Your suggestion ($y^+ to +infty$) also leads to the same result. I don't see how this shows that my trick is wrong. I'm missing something?
$endgroup$
– GNUSupporter 8964民主女神 地下教會
Feb 3 at 9:46
$begingroup$
that your reformulation is wrong becomes more apparent when you add an extra constraint that $y=0$ ($y^+ - y^- = 0$). The original problem is bounded but your reformulated problem is not (set $y^+ = y^-$, letting those go to infinity, the first constraint no longer restricts $x$).
$endgroup$
– LinAlg
Feb 3 at 13:30
$begingroup$
@LinAlg Why you say that the original problem bounded? An arbitrarily large $y$ satisfies the orginal constraint. Since the coefficient of $y$ in the objective function is positive, the problem is unbounded. I've never introduced $y=0$ as a constraint. It's $y^+ y^-=0$.
$endgroup$
– GNUSupporter 8964民主女神 地下教會
Feb 3 at 15:24
|
show 2 more comments
2
2
2
$begingroup$
The optimisation problem in the question is NOT an LPP because an LPP has convex feasible region. We can easily check that
$$S = {(x,y)inBbb{R}^2 mid |x-2|-|y| le 5}$$ is not convex as $(10,pm3) in S$, but $(10,0) notin S$.
This problem can be converted into an LPP by the usual trick in (2).
- make the substitution $u = x-2$
- split each decision variables into its positive and negative components.
begin{alignat}{2}
y^+ &:= frac{|y|+y}{2} &qquad y^- &:= frac{|y|-y}{2} \
u^+ &:= frac{|u|+u}{2} & u^- &:= frac{|u|-u}{2} \
therefore y &= y^+ - y^- & |y| &= y^+ + y^- \
u &= u^+ - u^- & |u| &= u^+ + u^-
end{alignat}
Then the objective function and the constraints become $3u^+ - 3u^- + 3y^+ - 3y^- - 24$ and
begin{cases}
u^+ + u^- - y^+ - y^- &le 5 \
u^+, u^-, y^+, y^- &ge 0 \
u^+ u^- = y^+ y^- = 0
end{cases}
respectively.
answered Feb 2 at 23:34
GNUSupporter 8964民主女神 地下教會GNUSupporter 8964民主女神 地下教會
14.1k82651
$endgroup$
The optimisation problem in the question is NOT an LPP because an LPP has convex feasible region. We can easily check that
$$S = {(x,y)inBbb{R}^2 mid |x-2|-|y| le 5}$$ is not convex as $(10,pm3) in S$, but $(10,0) notin S$.
This problem can be converted into an LPP by the usual trick in (2).
- make the substitution $u = x-2$
- split each decision variables into its positive and negative components.
begin{alignat}{2}
y^+ &:= frac{|y|+y}{2} &qquad y^- &:= frac{|y|-y}{2} \
u^+ &:= frac{|u|+u}{2} & u^- &:= frac{|u|-u}{2} \
therefore y &= y^+ - y^- & |y| &= y^+ + y^- \
u &= u^+ - u^- & |u| &= u^+ + u^-
end{alignat}
Then the objective function and the constraints become $3u^+ - 3u^- + 3y^+ - 3y^- - 24$ and
begin{cases}
u^+ + u^- - y^+ - y^- &le 5 \
u^+, u^-, y^+, y^- &ge 0 \
u^+ u^- = y^+ y^- = 0
end{cases}
respectively.
answered Feb 2 at 23:34
GNUSupporter 8964民主女神 地下教會GNUSupporter 8964民主女神 地下教會
14.1k82651
edited Feb 3 at 9:35
answered Feb 2 at 23:34
GNUSupporter 8964民主女神 地下教會GNUSupporter 8964民主女神 地下教會
14.1k82651
answered Feb 2 at 23:34
GNUSupporter 8964民主女神 地下教會GNUSupporter 8964民主女神 地下教會
14.1k82651
answered Feb 2 at 23:34
GNUSupporter 8964民主女神 地下教會GNUSupporter 8964民主女神 地下教會
14.1k82651
14.1k82651
1
$begingroup$
your 'trick' is wrong (you can let $y^+ to infty$), you cannot convert it into an LPP without introducing binaries
$endgroup$
– LinAlg
Feb 3 at 1:24
$begingroup$
@LinAlg I've a careless mistake when splitting variables in the middle. I meant $u$ instead of $x$. Apart from that, the trick is a usual one. You may see this, for example, in math.stackexchange.com/a/432029/290189.
$endgroup$
– GNUSupporter 8964民主女神 地下教會
Feb 3 at 9:36
$begingroup$
The original maximisation problem is unbounded (by fixing $x$ and letting $y to +infty$). Your suggestion ($y^+ to +infty$) also leads to the same result. I don't see how this shows that my trick is wrong. I'm missing something?
$endgroup$
– GNUSupporter 8964民主女神 地下教會
Feb 3 at 9:46
$begingroup$
that your reformulation is wrong becomes more apparent when you add an extra constraint that $y=0$ ($y^+ - y^- = 0$). The original problem is bounded but your reformulated problem is not (set $y^+ = y^-$, letting those go to infinity, the first constraint no longer restricts $x$).
$endgroup$
– LinAlg
Feb 3 at 13:30
$begingroup$
@LinAlg Why you say that the original problem bounded? An arbitrarily large $y$ satisfies the orginal constraint. Since the coefficient of $y$ in the objective function is positive, the problem is unbounded. I've never introduced $y=0$ as a constraint. It's $y^+ y^-=0$.
$endgroup$
– GNUSupporter 8964民主女神 地下教會
Feb 3 at 15:24
|
show 2 more comments
1
$begingroup$
your 'trick' is wrong (you can let $y^+ to infty$), you cannot convert it into an LPP without introducing binaries
$endgroup$
– LinAlg
Feb 3 at 1:24
$begingroup$
@LinAlg I've a careless mistake when splitting variables in the middle. I meant $u$ instead of $x$. Apart from that, the trick is a usual one. You may see this, for example, in math.stackexchange.com/a/432029/290189.
$endgroup$
– GNUSupporter 8964民主女神 地下教會
Feb 3 at 9:36
$begingroup$
The original maximisation problem is unbounded (by fixing $x$ and letting $y to +infty$). Your suggestion ($y^+ to +infty$) also leads to the same result. I don't see how this shows that my trick is wrong. I'm missing something?
$endgroup$
– GNUSupporter 8964民主女神 地下教會
Feb 3 at 9:46
$begingroup$
that your reformulation is wrong becomes more apparent when you add an extra constraint that $y=0$ ($y^+ - y^- = 0$). The original problem is bounded but your reformulated problem is not (set $y^+ = y^-$, letting those go to infinity, the first constraint no longer restricts $x$).
$endgroup$
– LinAlg
Feb 3 at 13:30
$begingroup$
@LinAlg Why you say that the original problem bounded? An arbitrarily large $y$ satisfies the orginal constraint. Since the coefficient of $y$ in the objective function is positive, the problem is unbounded. I've never introduced $y=0$ as a constraint. It's $y^+ y^-=0$.
$endgroup$
– GNUSupporter 8964民主女神 地下教會
Feb 3 at 15:24
1
1
$begingroup$
your 'trick' is wrong (you can let $y^+ to infty$), you cannot convert it into an LPP without introducing binaries
$endgroup$
– LinAlg
Feb 3 at 1:24
$begingroup$
your 'trick' is wrong (you can let $y^+ to infty$), you cannot convert it into an LPP without introducing binaries
$endgroup$
– LinAlg
Feb 3 at 1:24
$begingroup$
@LinAlg I've a careless mistake when splitting variables in the middle. I meant $u$ instead of $x$. Apart from that, the trick is a usual one. You may see this, for example, in math.stackexchange.com/a/432029/290189.
$endgroup$
– GNUSupporter 8964民主女神 地下教會
Feb 3 at 9:36
$begingroup$
@LinAlg I've a careless mistake when splitting variables in the middle. I meant $u$ instead of $x$. Apart from that, the trick is a usual one. You may see this, for example, in math.stackexchange.com/a/432029/290189.
$endgroup$
– GNUSupporter 8964民主女神 地下教會
Feb 3 at 9:36
$begingroup$
The original maximisation problem is unbounded (by fixing $x$ and letting $y to +infty$). Your suggestion ($y^+ to +infty$) also leads to the same result. I don't see how this shows that my trick is wrong. I'm missing something?
$endgroup$
– GNUSupporter 8964民主女神 地下教會
Feb 3 at 9:46
$begingroup$
The original maximisation problem is unbounded (by fixing $x$ and letting $y to +infty$). Your suggestion ($y^+ to +infty$) also leads to the same result. I don't see how this shows that my trick is wrong. I'm missing something?
$endgroup$
– GNUSupporter 8964民主女神 地下教會
Feb 3 at 9:46
$begingroup$
that your reformulation is wrong becomes more apparent when you add an extra constraint that $y=0$ ($y^+ - y^- = 0$). The original problem is bounded but your reformulated problem is not (set $y^+ = y^-$, letting those go to infinity, the first constraint no longer restricts $x$).
$endgroup$
– LinAlg
Feb 3 at 13:30
$begingroup$
that your reformulation is wrong becomes more apparent when you add an extra constraint that $y=0$ ($y^+ - y^- = 0$). The original problem is bounded but your reformulated problem is not (set $y^+ = y^-$, letting those go to infinity, the first constraint no longer restricts $x$).
$endgroup$
– LinAlg
Feb 3 at 13:30
$begingroup$
@LinAlg Why you say that the original problem bounded? An arbitrarily large $y$ satisfies the orginal constraint. Since the coefficient of $y$ in the objective function is positive, the problem is unbounded. I've never introduced $y=0$ as a constraint. It's $y^+ y^-=0$.
$endgroup$
– GNUSupporter 8964民主女神 地下教會
Feb 3 at 15:24
$begingroup$
@LinAlg Why you say that the original problem bounded? An arbitrarily large $y$ satisfies the orginal constraint. Since the coefficient of $y$ in the objective function is positive, the problem is unbounded. I've never introduced $y=0$ as a constraint. It's $y^+ y^-=0$.
$endgroup$
– GNUSupporter 8964民主女神 地下教會
Feb 3 at 15:24
|
show 2 more comments
draft saved
draft discarded
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.
draft saved
draft discarded
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%2f3097850%2fwhy-is-the-following-not-a-a-linear-programming-problem%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$
Notice that the constraint is not a linear function of your decision variables.
$endgroup$
– VHarisop
Feb 2 at 21:59
$begingroup$
@VHarisop Why the constraint is not linear? Is it because the absolute value? If it is, why can not remove the absolute value by some tricks?
$endgroup$
– Cathy
Feb 2 at 22:02
$begingroup$
Yes, the absolute values are the reason. You can't rely on any tricks to "remove" the absolute value (e.g. if you try equating it with a linear function you will end up with multiple coefficients depending on the values of $x$, $y$).
$endgroup$
– VHarisop
Feb 2 at 22:09
$begingroup$
@VHarisop I'm confused. Since it gives an example that maximize 3x + 3y − 30 subject to |x−2|+|y|≤5 is a LLP. Why only change the "+" to "-", then it is not?
$endgroup$
– Cathy
Feb 2 at 22:15
1
$begingroup$
I would say that neither problem (with the + or the -) "is" a linear programming problem. It's just that the one with the + coincidentally happens to be equivalent to a LPP, and (as the answer shows) the one with the - does not.
$endgroup$
– Micah
Feb 3 at 0:32