D Question 17 0-1 Integer Programming is similar to linear programming except th

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.

Explanation / Answer

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.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.