Question

D Question 17 0-1 Integer Programming is similar to linear programming except the variables can only be O and 1. Consider the 0-1 Integer Programming Decision Problem (0-1 IPD) as defined below: Instance: A set X of 0-1 integer variables (x O or x, 1), a set of inequalities over these variables, a function f(x) to maximize and integer K. Question: Does there exist an assignment of values to X such that all inequalities are true and fx) K? xample -1x2-0, x3 =0} of an instance of 0-1 P-D:x2+ x 3, x-x3 1, fx) 4x1 + X3. K 2. The answer is yes, given certificate (x1 Prove that 0-1 IPD Problem is NP-Complete.

0 0
Add a comment Improve this question Transcribed image text
Answer #1

Binary linear programming (BinLP) resembles linear programming, with the extra requirement that all variables must take on values either 0 or 1. The decision form of binary linear programming asks whether or not there exists a point fulfilling every one of the constraints. (For the choice form there is no objective function).

Claim: BinLP is NP-finished.

Evidence:

(1) BinLP is in NP. (What is the witness? The solution.)

(2) We can reduce 3SAT to BinLP:

Let the variables in the 3SAT equation be x_1, x_2, ..., x_n. We will have to compare factors z_1, z_2, ..., z_n in our integer linear program. In the first place, limit every factor to be 0 or 1:

z_i in {0,1} for all i

Doling out z_i=1 in the integer program represents setting x_i=true in the equation, and assigning z_i=0 represents setting x_i=false.

For every proviso like (x_1 OR not(x_2) OR x_3), have a constraint like:

z_1 + (1-z_2) + z_3 >= 1.

To fulfill this inequality we should either set z_1=1 or z_2=0 or z_3=1, which implies we either set x_1=true or x_2=false or x_3=true in the relating truth assignment. All the more for the most part, for every clause in the 3SAT occurrence, we create the constraint that the whole of literals, utilizing z_i to speak to x_i and (1-z_i) to speak to NOT(x_i), is no less than 1.

In the event that the given occurrence I was a YES-occasion of 3SAT then f(I) is a YES-instance for BinLP: simply take a satisfying assignment A to the variables x_i and set each z_i to 0 or 1 in like manner. Since A fulfilled no less than one literal in each clause, this implies the related aggregate is >= 1. In the other direction, any answer for the BinLP must set no less than one of the related literals to 1, since each is a whole number 0 or 1.

Add a comment
Know the answer?
Add Answer to:
D Question 17 0-1 Integer Programming is similar to linear programming except the variables can only...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions
  • QUESTION 13 A company has decided to use 0-1 (binary) integer programming to help to make...

    QUESTION 13 A company has decided to use 0-1 (binary) integer programming to help to make some investment decisions. There are three possible investment alternatives from which to choose, but if it is decided that a particular alternative is to be selected, the entire cost of that alternative will be incurred (i.e., it is impossible to build one-half of a factory). The integer programming model is as follows: Max 5000X1+7000X2+9000X3 S.t. X1+X2+X3<=2 (only 2 may be chosen) 25000X1+32000X2+29000X3<=62000 (budget limit)...

  • QUESTION 13 A company has decided to use 0-1 (binary) integer programming to help to make...

    QUESTION 13 A company has decided to use 0-1 (binary) integer programming to help to make some investment decisions. There are three possible investment alternatives from which to choose, but if it is decided that a particular alternative is to be selected, the entire cost of that alternative will be incurred (i.e., it is impossible to build one-half of a factory). The integer programming model is as follows: Max 5000X1+7000X2+9000X3 S.t.     X1+X2+X3<=2  (only 2 may be chosen) 25000X1+32000X2+29000X3<=62000 (budget limit)    16X1+14X2+19X3<=36  (resource...

  • A company has decided to use 0-1 (binary) integer programming to help to make some investment...

    A company has decided to use 0-1 (binary) integer programming to help to make some investment decisions. There are three possible investment alternatives from which to choose, but if it is decided that a particular alternative is to be selected, the entire cost of that alternative will be incurred (i.e., it is impossible to build one-half of a factory). The integer programming model is as follows: Max 5000X1 +7000X2+9000X3 S.t. X1+X2+X3<=2 (only 2 may be chosen) 25000X1+32000X2+29000X3<=62000 (budget limit) 16X1+14X2+19X3<=36...

  • Introduce slack variables as necessary and then write the initial simplex tableau for the given linear...

    Introduce slack variables as necessary and then write the initial simplex tableau for the given linear programming problem. Complete the initial simplex tableau. 1 1 X, X2 X3 s, 3 8 5 0 2 2 0 0 ONN S2 S3 0 0 0 0 0 0 NOOO 1 12 9 9 1 0 Z= X1 +8X2 +3X3 Maximize subject to X1 8X4 +2x2 +X2 +3x3 12 + 5x3 39 + 2x3 = 9 20, X3 20. 2x X1 20, X2

  • please Question 1 Convert the constraints into linear equations by using slack variables. Maximize z =...

    please Question 1 Convert the constraints into linear equations by using slack variables. Maximize z = 2X1 +8X2 Subject to:X1 + 6x2 s 15 2x1 + 9x2 s 25 X120,X220 X1 + 6x2 +51 s 15 2X1 + 9x2525 25 x1 +6X2+S1 = 15 2X1 +9x2 +52 = 25 O X1 +6X2 + 512 15 2X1 + 9x2 +522 25 X1 +6x2 = S1 +15 2x1 + 9x2 = S2 + 25 Question 2 Introduce slack variables as necessary and...

  • Question 12 Convert the constraints into linear equations by using slack variables. Maximize z = X1...

    Question 12 Convert the constraints into linear equations by using slack variables. Maximize z = X1 + 2x2 + 3x3 Subject to: X1 + 9x2 + 3x3 = 40 6X1 + X2 + 6x3 s 50 X120,X220, X320 O X1 + 9x2 + 3x3 = 51 +40 6x1 + x2 +6x3 = S2 + 50 O X1 +9x2 + 3x3 +51 = 40 6x1 + x2 + 6x3 +S2 = 50 X1 +9x2 + 3x3 +51 = 40 6X1 +...

  • Question 6: Let n 2 1 be an integer and let A[1...n] be an array that...

    Question 6: Let n 2 1 be an integer and let A[1...n] be an array that stores a permutation of the set { 1, 2, . .. , n). If the array A s sorted. then Ak] = k for k = 1.2. .., n and, thus. TL k-1 If the array A is not sorted and Ak-i, where iメk, then Ak-서 is equal to the "distance" that the valuei must move in order to make the array sorted. Thus,...

  • same question just A through D steps (A) Introduce slack, surplus, and artificial variables and form...

    same question just A through D steps (A) Introduce slack, surplus, and artificial variables and form the modified problem. (B) Write the preliminary simplex tableau for the modified problem and find the initial simplex tableau. () Find the optimal solution of the modified problem by applying the simplex method to the initial simplex tableau. (D) Find the optimal solution of the original problem, it it exists. Maximize P-3xı + 5x2 subject to 2x1 + x2 58 X1 + X2 =...

  • 1. Solving the linear programming problem Maximize z 3r1 2r2 3, subject to the constraints using ...

    1. Solving the linear programming problem Maximize z 3r1 2r2 3, subject to the constraints using the simplex algorithm gave the final tableau T4 T5 #210 1-1/4 3/8-1/812 0 0 23/4 3/8 7/8 10 (a) (3 points) Add the constraint -221 to the final tableau and use the dual simplex algorithm to find a new optimal solution. (b) (3 points) After adding the constraint of Part (a), what happens to the optimal solution if we add the fourth constraint 2+...

  • Use the simplex method to solve the linear programming problem. Maximize z = xy + 3x2...

    Use the simplex method to solve the linear programming problem. Maximize z = xy + 3x2 + x3 + 9x4 subject to Xy+ 7x2 + x3 + X4 5 10 8xy + x2 + 4x3 + X4 180 Xy 20,X220, X3 20,X420 Select the correct choice below and, if necessary, fill in the answer boxes to complete your choice. O A. The maximum is when xy = X2 s, -and s2 = B. There is no maximum. The initial simplex...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT