Find minimum values of a linear system over $mathbb N$
$begingroup$
I have the following linear equations:
begin{align}
p &= 2(a-c)+b-d\
q &= 2(e-g)+f-h\
a+c &= f+h\
b+d &= e+g\
end{align}
where $p$ and $q$ are known, and $a$, $b$, $c$, $d$, $e$, $f$, $g$, $h$ are unknown. Also $p$, $q$, $a$, $b$, $c$, $d$, $e$, $f$, $g$, $h$ are all natural numbers (including zeros).
Obviously, this is a linear system with $4$ equations and $8$ unknowns that has infinitely many solutions.
Is there a way to find the minimum values of $a$, $b$, $c$, $d$, $e$, $f$, $g$, $h$ that solve the system? What I really want is the minimum value of the sum $a+b+c+d$ (which also happens to be equal with $e+f+g+h$).
linear-algebra systems-of-equations
edited Dec 8 '18 at 15:02
Rodrigo de Azevedo
12.9k41857
asked Dec 8 '18 at 12:20
George SavvidisGeorge Savvidis
62
$endgroup$
add a comment |
$begingroup$
I have the following linear equations:
begin{align}
p &= 2(a-c)+b-d\
q &= 2(e-g)+f-h\
a+c &= f+h\
b+d &= e+g\
end{align}
where $p$ and $q$ are known, and $a$, $b$, $c$, $d$, $e$, $f$, $g$, $h$ are unknown. Also $p$, $q$, $a$, $b$, $c$, $d$, $e$, $f$, $g$, $h$ are all natural numbers (including zeros).
Obviously, this is a linear system with $4$ equations and $8$ unknowns that has infinitely many solutions.
Is there a way to find the minimum values of $a$, $b$, $c$, $d$, $e$, $f$, $g$, $h$ that solve the system? What I really want is the minimum value of the sum $a+b+c+d$ (which also happens to be equal with $e+f+g+h$).
linear-algebra systems-of-equations
edited Dec 8 '18 at 15:02
Rodrigo de Azevedo
12.9k41857
asked Dec 8 '18 at 12:20
George SavvidisGeorge Savvidis
62
$endgroup$
$begingroup$
Is there a typo? Your $p$ and $q$ are the same.
$endgroup$
– Karn Watcharasupat
Dec 8 '18 at 12:25
$begingroup$
Yes, I'm sorry for that, now it's fixed.
$endgroup$
– George Savvidis
Dec 8 '18 at 12:32
$begingroup$
Of course, this can be formulated as an integer linear programming problem, but I assume that's not the answer you're looking for. I've written an answer with a couple of ideas that don't require specialized software, but if you have have access to ILP software, that would be the first thing to try.
$endgroup$
– saulspatz
Dec 8 '18 at 13:59
add a comment |
$begingroup$
I have the following linear equations:
begin{align}
p &= 2(a-c)+b-d\
q &= 2(e-g)+f-h\
a+c &= f+h\
b+d &= e+g\
end{align}
where $p$ and $q$ are known, and $a$, $b$, $c$, $d$, $e$, $f$, $g$, $h$ are unknown. Also $p$, $q$, $a$, $b$, $c$, $d$, $e$, $f$, $g$, $h$ are all natural numbers (including zeros).
Obviously, this is a linear system with $4$ equations and $8$ unknowns that has infinitely many solutions.
Is there a way to find the minimum values of $a$, $b$, $c$, $d$, $e$, $f$, $g$, $h$ that solve the system? What I really want is the minimum value of the sum $a+b+c+d$ (which also happens to be equal with $e+f+g+h$).
linear-algebra systems-of-equations
edited Dec 8 '18 at 15:02
Rodrigo de Azevedo
12.9k41857
asked Dec 8 '18 at 12:20
George SavvidisGeorge Savvidis
62
$endgroup$
I have the following linear equations:
begin{align}
p &= 2(a-c)+b-d\
q &= 2(e-g)+f-h\
a+c &= f+h\
b+d &= e+g\
end{align}
where $p$ and $q$ are known, and $a$, $b$, $c$, $d$, $e$, $f$, $g$, $h$ are unknown. Also $p$, $q$, $a$, $b$, $c$, $d$, $e$, $f$, $g$, $h$ are all natural numbers (including zeros).
Obviously, this is a linear system with $4$ equations and $8$ unknowns that has infinitely many solutions.
Is there a way to find the minimum values of $a$, $b$, $c$, $d$, $e$, $f$, $g$, $h$ that solve the system? What I really want is the minimum value of the sum $a+b+c+d$ (which also happens to be equal with $e+f+g+h$).
linear-algebra systems-of-equations
linear-algebra systems-of-equations
edited Dec 8 '18 at 15:02
Rodrigo de Azevedo
12.9k41857
asked Dec 8 '18 at 12:20
George SavvidisGeorge Savvidis
62
edited Dec 8 '18 at 15:02
Rodrigo de Azevedo
12.9k41857
asked Dec 8 '18 at 12:20
George SavvidisGeorge Savvidis
62
edited Dec 8 '18 at 15:02
Rodrigo de Azevedo
12.9k41857
edited Dec 8 '18 at 15:02
Rodrigo de Azevedo
12.9k41857
edited Dec 8 '18 at 15:02
Rodrigo de Azevedo
12.9k41857
12.9k41857
asked Dec 8 '18 at 12:20
George SavvidisGeorge Savvidis
62
asked Dec 8 '18 at 12:20
George SavvidisGeorge Savvidis
62
asked Dec 8 '18 at 12:20
George SavvidisGeorge Savvidis
62
62
$begingroup$
Is there a typo? Your $p$ and $q$ are the same.
$endgroup$
– Karn Watcharasupat
Dec 8 '18 at 12:25
$begingroup$
Yes, I'm sorry for that, now it's fixed.
$endgroup$
– George Savvidis
Dec 8 '18 at 12:32
$begingroup$
Of course, this can be formulated as an integer linear programming problem, but I assume that's not the answer you're looking for. I've written an answer with a couple of ideas that don't require specialized software, but if you have have access to ILP software, that would be the first thing to try.
$endgroup$
– saulspatz
Dec 8 '18 at 13:59
add a comment |
$begingroup$
Is there a typo? Your $p$ and $q$ are the same.
$endgroup$
– Karn Watcharasupat
Dec 8 '18 at 12:25
$begingroup$
Yes, I'm sorry for that, now it's fixed.
$endgroup$
– George Savvidis
Dec 8 '18 at 12:32
$begingroup$
Of course, this can be formulated as an integer linear programming problem, but I assume that's not the answer you're looking for. I've written an answer with a couple of ideas that don't require specialized software, but if you have have access to ILP software, that would be the first thing to try.
$endgroup$
– saulspatz
Dec 8 '18 at 13:59
$begingroup$
Is there a typo? Your $p$ and $q$ are the same.
$endgroup$
– Karn Watcharasupat
Dec 8 '18 at 12:25
$begingroup$
Is there a typo? Your $p$ and $q$ are the same.
$endgroup$
– Karn Watcharasupat
Dec 8 '18 at 12:25
$begingroup$
Yes, I'm sorry for that, now it's fixed.
$endgroup$
– George Savvidis
Dec 8 '18 at 12:32
$begingroup$
Yes, I'm sorry for that, now it's fixed.
$endgroup$
– George Savvidis
Dec 8 '18 at 12:32
$begingroup$
Of course, this can be formulated as an integer linear programming problem, but I assume that's not the answer you're looking for. I've written an answer with a couple of ideas that don't require specialized software, but if you have have access to ILP software, that would be the first thing to try.
$endgroup$
– saulspatz
Dec 8 '18 at 13:59
$begingroup$
Of course, this can be formulated as an integer linear programming problem, but I assume that's not the answer you're looking for. I've written an answer with a couple of ideas that don't require specialized software, but if you have have access to ILP software, that would be the first thing to try.
$endgroup$
– saulspatz
Dec 8 '18 at 13:59
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
This isn't a full solution, just an idea to get started. If we have a solution $(a,b,c,d,e,f,g,h),$ let $$
begin{align}
m&=min(a,c,f,h)\
n&=min(b,d,e,g)\
a'&=a-m\
c'&=c-m\
f'&=f-m\
h'&=h-m\
b'&=b-n\
d'&=d-n\
e'&=e-n\
g'&=g-n\
end{align}$$
Then $(a',b',c',d',e',f',g',h')$ is a solution in naturals and $$a'+b'+c+d'le a+b+c+d.$$ So, we can assume that one of $a,c,f,h$ is $0$ and one of $b,d,e,g$ is $0$. This gives $16$ systems of equations, but they only have $6$ variables instead of $8.$
The only other thing I've noticed so far is that we have $$
begin{align}
p&equiv b-dequiv b+dpmod{2}\
q&equiv f-hequiv f+hequiv a+cpmod{2}\
end{align}$$
So that
$$a+b+c+dequiv p+qpmod{2}$$
A possible approach is to try test values of $a+b+c+d$ adding it as another equation. The above fact eliminates half the test values. If you get a solution, you have an upper bound on the minimum. If the system doesn't have a solution, I don't see that you have a lower bound though.
answered Dec 8 '18 at 13:57
saulspatzsaulspatz
14.5k21329
$endgroup$
add a comment |
$begingroup$
Perhaps, at first, it would be useful to consider the relaxation of this problem, i.e. all variables are non-negative real! numbers. Then it is possible to use the simplex method with some kind of caution because $p,q$ are not given explicitly. For example, If I did not make a mistake then the solution of the relaxation LP problem is something like
$$
a=f=frac{2p-q}3, e=b=frac{2q-p}3, c=d=g=h=0
$$
and the corresponding minimum is
$$
frac{p+q}3.
$$
This looks true if $2p-q$ and $2q-p$ are both non-negative (if they also are divided by 3 then they are solutions of the original integer programming problem). if $2p-q$ or $2q-p$ can be negative then the solution is different...
Another idea is to try to rewrite it as a binary integer programming problem...
answered Dec 8 '18 at 14:52
AAKAAK
365
$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%2f3031046%2ffind-minimum-values-of-a-linear-system-over-mathbb-n%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$
This isn't a full solution, just an idea to get started. If we have a solution $(a,b,c,d,e,f,g,h),$ let $$
begin{align}
m&=min(a,c,f,h)\
n&=min(b,d,e,g)\
a'&=a-m\
c'&=c-m\
f'&=f-m\
h'&=h-m\
b'&=b-n\
d'&=d-n\
e'&=e-n\
g'&=g-n\
end{align}$$
Then $(a',b',c',d',e',f',g',h')$ is a solution in naturals and $$a'+b'+c+d'le a+b+c+d.$$ So, we can assume that one of $a,c,f,h$ is $0$ and one of $b,d,e,g$ is $0$. This gives $16$ systems of equations, but they only have $6$ variables instead of $8.$
The only other thing I've noticed so far is that we have $$
begin{align}
p&equiv b-dequiv b+dpmod{2}\
q&equiv f-hequiv f+hequiv a+cpmod{2}\
end{align}$$
So that
$$a+b+c+dequiv p+qpmod{2}$$
A possible approach is to try test values of $a+b+c+d$ adding it as another equation. The above fact eliminates half the test values. If you get a solution, you have an upper bound on the minimum. If the system doesn't have a solution, I don't see that you have a lower bound though.
answered Dec 8 '18 at 13:57
saulspatzsaulspatz
14.5k21329
$endgroup$
add a comment |
$begingroup$
This isn't a full solution, just an idea to get started. If we have a solution $(a,b,c,d,e,f,g,h),$ let $$
begin{align}
m&=min(a,c,f,h)\
n&=min(b,d,e,g)\
a'&=a-m\
c'&=c-m\
f'&=f-m\
h'&=h-m\
b'&=b-n\
d'&=d-n\
e'&=e-n\
g'&=g-n\
end{align}$$
Then $(a',b',c',d',e',f',g',h')$ is a solution in naturals and $$a'+b'+c+d'le a+b+c+d.$$ So, we can assume that one of $a,c,f,h$ is $0$ and one of $b,d,e,g$ is $0$. This gives $16$ systems of equations, but they only have $6$ variables instead of $8.$
The only other thing I've noticed so far is that we have $$
begin{align}
p&equiv b-dequiv b+dpmod{2}\
q&equiv f-hequiv f+hequiv a+cpmod{2}\
end{align}$$
So that
$$a+b+c+dequiv p+qpmod{2}$$
A possible approach is to try test values of $a+b+c+d$ adding it as another equation. The above fact eliminates half the test values. If you get a solution, you have an upper bound on the minimum. If the system doesn't have a solution, I don't see that you have a lower bound though.
answered Dec 8 '18 at 13:57
saulspatzsaulspatz
14.5k21329
$endgroup$
add a comment |
$begingroup$
This isn't a full solution, just an idea to get started. If we have a solution $(a,b,c,d,e,f,g,h),$ let $$
begin{align}
m&=min(a,c,f,h)\
n&=min(b,d,e,g)\
a'&=a-m\
c'&=c-m\
f'&=f-m\
h'&=h-m\
b'&=b-n\
d'&=d-n\
e'&=e-n\
g'&=g-n\
end{align}$$
Then $(a',b',c',d',e',f',g',h')$ is a solution in naturals and $$a'+b'+c+d'le a+b+c+d.$$ So, we can assume that one of $a,c,f,h$ is $0$ and one of $b,d,e,g$ is $0$. This gives $16$ systems of equations, but they only have $6$ variables instead of $8.$
The only other thing I've noticed so far is that we have $$
begin{align}
p&equiv b-dequiv b+dpmod{2}\
q&equiv f-hequiv f+hequiv a+cpmod{2}\
end{align}$$
So that
$$a+b+c+dequiv p+qpmod{2}$$
A possible approach is to try test values of $a+b+c+d$ adding it as another equation. The above fact eliminates half the test values. If you get a solution, you have an upper bound on the minimum. If the system doesn't have a solution, I don't see that you have a lower bound though.
answered Dec 8 '18 at 13:57
saulspatzsaulspatz
14.5k21329
$endgroup$
This isn't a full solution, just an idea to get started. If we have a solution $(a,b,c,d,e,f,g,h),$ let $$
begin{align}
m&=min(a,c,f,h)\
n&=min(b,d,e,g)\
a'&=a-m\
c'&=c-m\
f'&=f-m\
h'&=h-m\
b'&=b-n\
d'&=d-n\
e'&=e-n\
g'&=g-n\
end{align}$$
Then $(a',b',c',d',e',f',g',h')$ is a solution in naturals and $$a'+b'+c+d'le a+b+c+d.$$ So, we can assume that one of $a,c,f,h$ is $0$ and one of $b,d,e,g$ is $0$. This gives $16$ systems of equations, but they only have $6$ variables instead of $8.$
The only other thing I've noticed so far is that we have $$
begin{align}
p&equiv b-dequiv b+dpmod{2}\
q&equiv f-hequiv f+hequiv a+cpmod{2}\
end{align}$$
So that
$$a+b+c+dequiv p+qpmod{2}$$
A possible approach is to try test values of $a+b+c+d$ adding it as another equation. The above fact eliminates half the test values. If you get a solution, you have an upper bound on the minimum. If the system doesn't have a solution, I don't see that you have a lower bound though.
answered Dec 8 '18 at 13:57
saulspatzsaulspatz
14.5k21329
answered Dec 8 '18 at 13:57
saulspatzsaulspatz
14.5k21329
answered Dec 8 '18 at 13:57
saulspatzsaulspatz
14.5k21329
answered Dec 8 '18 at 13:57
saulspatzsaulspatz
14.5k21329
14.5k21329
add a comment |
add a comment |
$begingroup$
Perhaps, at first, it would be useful to consider the relaxation of this problem, i.e. all variables are non-negative real! numbers. Then it is possible to use the simplex method with some kind of caution because $p,q$ are not given explicitly. For example, If I did not make a mistake then the solution of the relaxation LP problem is something like
$$
a=f=frac{2p-q}3, e=b=frac{2q-p}3, c=d=g=h=0
$$
and the corresponding minimum is
$$
frac{p+q}3.
$$
This looks true if $2p-q$ and $2q-p$ are both non-negative (if they also are divided by 3 then they are solutions of the original integer programming problem). if $2p-q$ or $2q-p$ can be negative then the solution is different...
Another idea is to try to rewrite it as a binary integer programming problem...
answered Dec 8 '18 at 14:52
AAKAAK
365
$endgroup$
add a comment |
$begingroup$
Perhaps, at first, it would be useful to consider the relaxation of this problem, i.e. all variables are non-negative real! numbers. Then it is possible to use the simplex method with some kind of caution because $p,q$ are not given explicitly. For example, If I did not make a mistake then the solution of the relaxation LP problem is something like
$$
a=f=frac{2p-q}3, e=b=frac{2q-p}3, c=d=g=h=0
$$
and the corresponding minimum is
$$
frac{p+q}3.
$$
This looks true if $2p-q$ and $2q-p$ are both non-negative (if they also are divided by 3 then they are solutions of the original integer programming problem). if $2p-q$ or $2q-p$ can be negative then the solution is different...
Another idea is to try to rewrite it as a binary integer programming problem...
answered Dec 8 '18 at 14:52
AAKAAK
365
$endgroup$
add a comment |
$begingroup$
Perhaps, at first, it would be useful to consider the relaxation of this problem, i.e. all variables are non-negative real! numbers. Then it is possible to use the simplex method with some kind of caution because $p,q$ are not given explicitly. For example, If I did not make a mistake then the solution of the relaxation LP problem is something like
$$
a=f=frac{2p-q}3, e=b=frac{2q-p}3, c=d=g=h=0
$$
and the corresponding minimum is
$$
frac{p+q}3.
$$
This looks true if $2p-q$ and $2q-p$ are both non-negative (if they also are divided by 3 then they are solutions of the original integer programming problem). if $2p-q$ or $2q-p$ can be negative then the solution is different...
Another idea is to try to rewrite it as a binary integer programming problem...
answered Dec 8 '18 at 14:52
AAKAAK
365
$endgroup$
Perhaps, at first, it would be useful to consider the relaxation of this problem, i.e. all variables are non-negative real! numbers. Then it is possible to use the simplex method with some kind of caution because $p,q$ are not given explicitly. For example, If I did not make a mistake then the solution of the relaxation LP problem is something like
$$
a=f=frac{2p-q}3, e=b=frac{2q-p}3, c=d=g=h=0
$$
and the corresponding minimum is
$$
frac{p+q}3.
$$
This looks true if $2p-q$ and $2q-p$ are both non-negative (if they also are divided by 3 then they are solutions of the original integer programming problem). if $2p-q$ or $2q-p$ can be negative then the solution is different...
Another idea is to try to rewrite it as a binary integer programming problem...
answered Dec 8 '18 at 14:52
AAKAAK
365
edited Dec 8 '18 at 15:16
answered Dec 8 '18 at 14:52
AAKAAK
365
answered Dec 8 '18 at 14:52
AAKAAK
365
answered Dec 8 '18 at 14:52
AAKAAK
365
365
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%2f3031046%2ffind-minimum-values-of-a-linear-system-over-mathbb-n%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$
Is there a typo? Your $p$ and $q$ are the same.
$endgroup$
– Karn Watcharasupat
Dec 8 '18 at 12:25
$begingroup$
Yes, I'm sorry for that, now it's fixed.
$endgroup$
– George Savvidis
Dec 8 '18 at 12:32
$begingroup$
Of course, this can be formulated as an integer linear programming problem, but I assume that's not the answer you're looking for. I've written an answer with a couple of ideas that don't require specialized software, but if you have have access to ILP software, that would be the first thing to try.
$endgroup$
– saulspatz
Dec 8 '18 at 13:59