Combining inequalities to not have coefficients

2

We have in input an inequality cons and a set of inequalities C and we want to find a way to sum them and simplify in a way that no variable has a coefficient and that the number of constraints that we took is maximal.

The input is always a constraint without any coefficient and it is always a <= k for a given k.

For example we can have in input:

cons = x1 + x2 + x3 <= 1

C:

   c1 = x1 + x2 + x4 <= 1

   c2 = x1 + x5 <= 1

   c3 = x3 + x4 <= 1

• If we sum: cons + c1, we obtain 2x1 + 2x2 + x3 + x4 <= 2 and we do not respect the condition that no variable should have a coefficient.




• If we sum cons + c2, we obtain 2x1 + x2 + x3 + x5 <= 2, so again it is not working.




• If we sum cons + c3, we obtain x1 + x2 + 2x3 + x4 <= 2, so again it is not working.




• However, if we sum cons + c1 + c3, we obtain 2x1 + 2x2 + 2x3 + 2x4 <= 3, thus it is x1 + x2 + x3 + x4 <= floor(3/2), and this time it works.

Does it exist an optimal way to solve this problem except going through all the possibilities?

Does this problem has a name in the literature?

inequality summation algorithms constraints

share|cite|improve this question

edited Nov 21 '18 at 15:16

asked Nov 21 '18 at 14:46

Valentin Montmirail

1365

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  It's not clear to me that it's possible in general. For example, take $C = {2x_1 + 3x_2 leq 1}$. Clearly nothing that we can do is going to get rid of those coefficients. So whatever general method you hope to find must make some use of whatever special properties those situations where it is possible have. A good first step, then, would be to determine when that happens. Secondly, note that the inequality is entirely irrelevant to the whole question: you're just talking about taking linear combinations of vectors to obtain a vector whose entries are all 0 or 1.
  – user3482749
  Nov 21 '18 at 15:01
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I will add more information but first: it is always a sum of variables without coefficient lower or equals than k. (xi + xj + ... + xn <= k). So the case "2x1 + 3x2 <= 1" cannot arrive. Thus, it the 'worst' case, I will just not perform any sum and return the input as it arrived. An extremely good point regarding the linear combinations of vectors, I will try to think in this way.
  – Valentin Montmirail
  Nov 21 '18 at 15:15
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  In that case, $2x_1 + 3x_2 leq 1000$. Again: $k$ is irrelevant. All of my comments still hold: any solution that you have must start by checking if it's possible, then exercise whatever special properties those vectors for which it works have that others don't. Start by finding out for which vectors it is possible.
  – user3482749
  Nov 21 '18 at 22:37
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Sorry, I was probably unclear. I meant that at the beginning, there are no equations with a coefficient, they all start with 1*x1 + 1*x2 + .... <= k. We cannot start with "2*x1 + 3*x2". So at the beginning, all vectors are possible
  – Valentin Montmirail
  Nov 23 '18 at 12:26
  

  
  
  
  

add a comment | 

2

We have in input an inequality cons and a set of inequalities C and we want to find a way to sum them and simplify in a way that no variable has a coefficient and that the number of constraints that we took is maximal.

The input is always a constraint without any coefficient and it is always a <= k for a given k.

For example we can have in input:

cons = x1 + x2 + x3 <= 1

C:

   c1 = x1 + x2 + x4 <= 1

   c2 = x1 + x5 <= 1

   c3 = x3 + x4 <= 1

• If we sum: cons + c1, we obtain 2x1 + 2x2 + x3 + x4 <= 2 and we do not respect the condition that no variable should have a coefficient.




• If we sum cons + c2, we obtain 2x1 + x2 + x3 + x5 <= 2, so again it is not working.




• If we sum cons + c3, we obtain x1 + x2 + 2x3 + x4 <= 2, so again it is not working.




• However, if we sum cons + c1 + c3, we obtain 2x1 + 2x2 + 2x3 + 2x4 <= 3, thus it is x1 + x2 + x3 + x4 <= floor(3/2), and this time it works.

Does it exist an optimal way to solve this problem except going through all the possibilities?

Does this problem has a name in the literature?

inequality summation algorithms constraints

share|cite|improve this question

edited Nov 21 '18 at 15:16

asked Nov 21 '18 at 14:46

Valentin Montmirail

1365

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  It's not clear to me that it's possible in general. For example, take $C = {2x_1 + 3x_2 leq 1}$. Clearly nothing that we can do is going to get rid of those coefficients. So whatever general method you hope to find must make some use of whatever special properties those situations where it is possible have. A good first step, then, would be to determine when that happens. Secondly, note that the inequality is entirely irrelevant to the whole question: you're just talking about taking linear combinations of vectors to obtain a vector whose entries are all 0 or 1.
  – user3482749
  Nov 21 '18 at 15:01
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I will add more information but first: it is always a sum of variables without coefficient lower or equals than k. (xi + xj + ... + xn <= k). So the case "2x1 + 3x2 <= 1" cannot arrive. Thus, it the 'worst' case, I will just not perform any sum and return the input as it arrived. An extremely good point regarding the linear combinations of vectors, I will try to think in this way.
  – Valentin Montmirail
  Nov 21 '18 at 15:15
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  In that case, $2x_1 + 3x_2 leq 1000$. Again: $k$ is irrelevant. All of my comments still hold: any solution that you have must start by checking if it's possible, then exercise whatever special properties those vectors for which it works have that others don't. Start by finding out for which vectors it is possible.
  – user3482749
  Nov 21 '18 at 22:37
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Sorry, I was probably unclear. I meant that at the beginning, there are no equations with a coefficient, they all start with 1*x1 + 1*x2 + .... <= k. We cannot start with "2*x1 + 3*x2". So at the beginning, all vectors are possible
  – Valentin Montmirail
  Nov 23 '18 at 12:26
  

  
  
  
  

add a comment | 

2

2

2

We have in input an inequality cons and a set of inequalities C and we want to find a way to sum them and simplify in a way that no variable has a coefficient and that the number of constraints that we took is maximal.

The input is always a constraint without any coefficient and it is always a <= k for a given k.

For example we can have in input:

cons = x1 + x2 + x3 <= 1

C:

   c1 = x1 + x2 + x4 <= 1

   c2 = x1 + x5 <= 1

   c3 = x3 + x4 <= 1

• If we sum: cons + c1, we obtain 2x1 + 2x2 + x3 + x4 <= 2 and we do not respect the condition that no variable should have a coefficient.




• If we sum cons + c2, we obtain 2x1 + x2 + x3 + x5 <= 2, so again it is not working.




• If we sum cons + c3, we obtain x1 + x2 + 2x3 + x4 <= 2, so again it is not working.




• However, if we sum cons + c1 + c3, we obtain 2x1 + 2x2 + 2x3 + 2x4 <= 3, thus it is x1 + x2 + x3 + x4 <= floor(3/2), and this time it works.

Does it exist an optimal way to solve this problem except going through all the possibilities?

Does this problem has a name in the literature?

inequality summation algorithms constraints

share|cite|improve this question

edited Nov 21 '18 at 15:16

asked Nov 21 '18 at 14:46

Valentin Montmirail

1365

We have in input an inequality cons and a set of inequalities C and we want to find a way to sum them and simplify in a way that no variable has a coefficient and that the number of constraints that we took is maximal.

The input is always a constraint without any coefficient and it is always a <= k for a given k.

For example we can have in input:

cons = x1 + x2 + x3 <= 1

C:

   c1 = x1 + x2 + x4 <= 1

   c2 = x1 + x5 <= 1

   c3 = x3 + x4 <= 1

• If we sum: cons + c1, we obtain 2x1 + 2x2 + x3 + x4 <= 2 and we do not respect the condition that no variable should have a coefficient.




• If we sum cons + c2, we obtain 2x1 + x2 + x3 + x5 <= 2, so again it is not working.




• If we sum cons + c3, we obtain x1 + x2 + 2x3 + x4 <= 2, so again it is not working.




• However, if we sum cons + c1 + c3, we obtain 2x1 + 2x2 + 2x3 + 2x4 <= 3, thus it is x1 + x2 + x3 + x4 <= floor(3/2), and this time it works.

Does it exist an optimal way to solve this problem except going through all the possibilities?

Does this problem has a name in the literature?

inequality summation algorithms constraints

inequality summation algorithms constraints

share|cite|improve this question

edited Nov 21 '18 at 15:16

asked Nov 21 '18 at 14:46

Valentin Montmirail

1365

share|cite|improve this question

edited Nov 21 '18 at 15:16

asked Nov 21 '18 at 14:46

Valentin Montmirail

1365

share|cite|improve this question

share|cite|improve this question

edited Nov 21 '18 at 15:16

edited Nov 21 '18 at 15:16

edited Nov 21 '18 at 15:16

asked Nov 21 '18 at 14:46

Valentin Montmirail

1365

asked Nov 21 '18 at 14:46

Valentin Montmirail

1365

asked Nov 21 '18 at 14:46

Valentin Montmirail

1365

1365

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  It's not clear to me that it's possible in general. For example, take $C = {2x_1 + 3x_2 leq 1}$. Clearly nothing that we can do is going to get rid of those coefficients. So whatever general method you hope to find must make some use of whatever special properties those situations where it is possible have. A good first step, then, would be to determine when that happens. Secondly, note that the inequality is entirely irrelevant to the whole question: you're just talking about taking linear combinations of vectors to obtain a vector whose entries are all 0 or 1.
  – user3482749
  Nov 21 '18 at 15:01
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I will add more information but first: it is always a sum of variables without coefficient lower or equals than k. (xi + xj + ... + xn <= k). So the case "2x1 + 3x2 <= 1" cannot arrive. Thus, it the 'worst' case, I will just not perform any sum and return the input as it arrived. An extremely good point regarding the linear combinations of vectors, I will try to think in this way.
  – Valentin Montmirail
  Nov 21 '18 at 15:15
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  In that case, $2x_1 + 3x_2 leq 1000$. Again: $k$ is irrelevant. All of my comments still hold: any solution that you have must start by checking if it's possible, then exercise whatever special properties those vectors for which it works have that others don't. Start by finding out for which vectors it is possible.
  – user3482749
  Nov 21 '18 at 22:37
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Sorry, I was probably unclear. I meant that at the beginning, there are no equations with a coefficient, they all start with 1*x1 + 1*x2 + .... <= k. We cannot start with "2*x1 + 3*x2". So at the beginning, all vectors are possible
  – Valentin Montmirail
  Nov 23 '18 at 12:26
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  It's not clear to me that it's possible in general. For example, take $C = {2x_1 + 3x_2 leq 1}$. Clearly nothing that we can do is going to get rid of those coefficients. So whatever general method you hope to find must make some use of whatever special properties those situations where it is possible have. A good first step, then, would be to determine when that happens. Secondly, note that the inequality is entirely irrelevant to the whole question: you're just talking about taking linear combinations of vectors to obtain a vector whose entries are all 0 or 1.
  – user3482749
  Nov 21 '18 at 15:01
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I will add more information but first: it is always a sum of variables without coefficient lower or equals than k. (xi + xj + ... + xn <= k). So the case "2x1 + 3x2 <= 1" cannot arrive. Thus, it the 'worst' case, I will just not perform any sum and return the input as it arrived. An extremely good point regarding the linear combinations of vectors, I will try to think in this way.
  – Valentin Montmirail
  Nov 21 '18 at 15:15
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  In that case, $2x_1 + 3x_2 leq 1000$. Again: $k$ is irrelevant. All of my comments still hold: any solution that you have must start by checking if it's possible, then exercise whatever special properties those vectors for which it works have that others don't. Start by finding out for which vectors it is possible.
  – user3482749
  Nov 21 '18 at 22:37
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Sorry, I was probably unclear. I meant that at the beginning, there are no equations with a coefficient, they all start with 1*x1 + 1*x2 + .... <= k. We cannot start with "2*x1 + 3*x2". So at the beginning, all vectors are possible
  – Valentin Montmirail
  Nov 23 '18 at 12:26
  

  
  
  
  

1

1

It's not clear to me that it's possible in general. For example, take $C = {2x_1 + 3x_2 leq 1}$. Clearly nothing that we can do is going to get rid of those coefficients. So whatever general method you hope to find must make some use of whatever special properties those situations where it is possible have. A good first step, then, would be to determine when that happens. Secondly, note that the inequality is entirely irrelevant to the whole question: you're just talking about taking linear combinations of vectors to obtain a vector whose entries are all 0 or 1.
– user3482749
Nov 21 '18 at 15:01

It's not clear to me that it's possible in general. For example, take $C = {2x_1 + 3x_2 leq 1}$. Clearly nothing that we can do is going to get rid of those coefficients. So whatever general method you hope to find must make some use of whatever special properties those situations where it is possible have. A good first step, then, would be to determine when that happens. Secondly, note that the inequality is entirely irrelevant to the whole question: you're just talking about taking linear combinations of vectors to obtain a vector whose entries are all 0 or 1.
– user3482749
Nov 21 '18 at 15:01

I will add more information but first: it is always a sum of variables without coefficient lower or equals than k. (xi + xj + ... + xn <= k). So the case "2x1 + 3x2 <= 1" cannot arrive. Thus, it the 'worst' case, I will just not perform any sum and return the input as it arrived. An extremely good point regarding the linear combinations of vectors, I will try to think in this way.
– Valentin Montmirail
Nov 21 '18 at 15:15

I will add more information but first: it is always a sum of variables without coefficient lower or equals than k. (xi + xj + ... + xn <= k). So the case "2x1 + 3x2 <= 1" cannot arrive. Thus, it the 'worst' case, I will just not perform any sum and return the input as it arrived. An extremely good point regarding the linear combinations of vectors, I will try to think in this way.
– Valentin Montmirail
Nov 21 '18 at 15:15

In that case, $2x_1 + 3x_2 leq 1000$. Again: $k$ is irrelevant. All of my comments still hold: any solution that you have must start by checking if it's possible, then exercise whatever special properties those vectors for which it works have that others don't. Start by finding out for which vectors it is possible.
– user3482749
Nov 21 '18 at 22:37

In that case, $2x_1 + 3x_2 leq 1000$. Again: $k$ is irrelevant. All of my comments still hold: any solution that you have must start by checking if it's possible, then exercise whatever special properties those vectors for which it works have that others don't. Start by finding out for which vectors it is possible.
– user3482749
Nov 21 '18 at 22:37

Sorry, I was probably unclear. I meant that at the beginning, there are no equations with a coefficient, they all start with 1*x1 + 1*x2 + .... <= k. We cannot start with "2*x1 + 3*x2". So at the beginning, all vectors are possible
– Valentin Montmirail
Nov 23 '18 at 12:26

Sorry, I was probably unclear. I meant that at the beginning, there are no equations with a coefficient, they all start with 1*x1 + 1*x2 + .... <= k. We cannot start with "2*x1 + 3*x2". So at the beginning, all vectors are possible
– Valentin Montmirail
Nov 23 '18 at 12:26

add a comment | 

0

active

oldest

votes

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
});


}
});

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.

Some of your past answers have not been well-received, and you're in danger of being blocked from answering.

Please pay close attention to the following guidance:

• 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.

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

Name

Email

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3007809%2fcombining-inequalities-to-not-have-coefficients%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

0

active

oldest

votes

0

active

oldest

votes

active

oldest

votes

active

oldest

votes

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.

Some of your past answers have not been well-received, and you're in danger of being blocked from answering.

Please pay close attention to the following guidance:

• 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.

To learn more, see our tips on writing great answers.

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.

Some of your past answers have not been well-received, and you're in danger of being blocked from answering.

Please pay close attention to the following guidance:

• 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.

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

Name

Email

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3007809%2fcombining-inequalities-to-not-have-coefficients%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

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

Name

Email

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

Name

Email

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

Name

Email

Required, but never shown

Name

Name

Email

Required, but never shown

Email

Required, but never shown

Email

Required, but never shown

Email

Required, but never shown

Name

Name

Email

Required, but never shown

Email

Required, but never shown

Email

Required, but never shown

Email

Required, but never shown

This page is only for reference, If you need detailed information, please check here