0

I have these equations and I want to find one solution for them

0<=x1+x2+x3+x4+x5+x6<=3                
0<=x7+x8<=2   
2<=x1+x2+x3+x4<=4   
2<=x3+x4+x5<=3   
2<=x6+x7+x8<=3   

the values of xi is 0 or 1 ( xi is binary variable)

is there any algorithm for solving this kind of equation and similar ones

1

2 Answers 2

4

Are you sure your problem is not a binary integer programming?

If you just want to solve this in-equation with such small amount of variables, brute-force search may just work....Construct 2^8 8*1 vectors, and verify if every vector satisfy your in-equation (you can write your equation in matrix form for sure).

If you just want ONE solution....you can even do it by hand: 10101011

But the general solution is not easy. Check this post. To solve the binary integer linear equation in polynomial time, there is one paper that you may take some time digging.

EDIT: update from @Ben Voigt

branch-and-bound is typically effective for efficiently solving (large) integer (incl. binary) and mixed-integer problems. Of course this problem is too small to be worth the overhead -- exhaustive search is quite adequate.

Sign up to request clarification or add additional context in comments.

6 Comments

thanks for your help .. I am searching for polynomial algorithm for solving this problem.
update one publication for you, the pseudo-code is included in the paper,but it takes time to understand the principle.
there is special form in my problem , first the matrix A is totally uni modular and also the variable in each equation are neighbours , maybe this make the problem easer to solve.
Your solution does not satisfy 2<=x6+x7+x8
branch-and-bound is typically effective for efficiently solving (large) integer (incl. binary) and mixed-integer problems. Of course this problem is too small to be worth the overhead -- exhaustive search is quite adequate. (Though lennon, you may want to use the correct therm, either exhaustive or brute force rather than brutal)
|
1

Regardless of the algorithm you may use, I would do some preprocessing to reduce the complexity. The sum of binary variables is always >=0:

x1+x2+x3+x4+x5+x6<=3                
x7+x8<=2   
2<=x1+x2+x3+x4<=4   
2<=x3+x4+x5<=3   
2<=x6+x7+x8<=3  

The sum of binary variables is always <= num of variables:

x1+x2+x3+x4+x5+x6<=3                
2<=x1+x2+x3+x4   
2<=x3+x4+x5   
2<=x6+x7+x8

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.