0-1 Linear Programming

4.14.3 0-1 Linear Programming

Definition

Given a matrix of constraint coefficient, and an integer b. There exists a n-vector -→x with elements in the set {0,1}, such that A ⋅ x_i ≤ b1 ≤ i ≤ n.

Polynomial Certifier

Given a matrix of constraint coefficient, and an integer b. Does there exist a n-vector -→x with elements in the set {0,1}, such that A ⋅ x_i ≤ b, where 1 ≤ i ≤ n?

Input: Given a matrix of constraint coefficient, and an integer b.
Certificate: A n-vector with elements in the set {0,1}.
Certifier: We verify it by doing the multiplication with the values provided for x and compare between each element of Ax and b. This can be done in polynomial time
Time Complexity: Same as the polynomial running time of Matrix Multiplication.

Reduction from 3-SAT from simple case to general case

In the 3-SAT, suppose that there are n variables x₁,x₂,…,x_n and m clauses in the CNF formula. The variables x₁,x₂,…,x_n in 3-SAT are all Boolean variables, so they are in the set {0,1} already. Each clause c_j = (x_j1 ∨x_j2 ∨x_j3) in 3-SAT can be transformed to a linear constraint x_j1 + x_j2 + x_j3 ≥ 1. If a variable appears like x_i, then we change it to 1 - x_i. Then, to be uniform, we turn ≥ into ≤. For instance,

xi ∨xj ∨xk ⇒ xi + xj + xk ≥ 1 ⇒ - xi - xj - xk ≤ - 1 xi ∨xj ∨xk ⇒ 1- xi + xj + xk ≥ 1 ⇒ xi - xj - xk ≤ 0

Following the above method, we can change every clause to a linear constraint on x and there are totally m constraints on n variables x_k. Let A be the coefficient matrix of every constraints, and b be the right hand side vector, then A is m × n and b is n × 1 and A ⋅ x ≤ b. So the 3-SAT problem is transformed into the 0-1 integer programming problem. Since there are m clauses, the transformation can be done in polynomial time O(m).

Claim 4.14.3.1. 3-SAT ≤ _p 0-1 Linear Programming (This construction of 3-SAT leads to is a special case of 0-1 Linear Programming)
Φ is satisfiable if and only if there is an n-vector x that solves A ⋅ x ≤ b where the values of x are either 0 or 1.

Φ is satisfiable ⇒ there is an n-vector x that solves A⋅x ≤ b where the values of x are either 0 or 1.

Proof. If 3-SAT has a satisfying truth assignment, at least one literal in each clause evaluates to be true. For each literal that evaluates to be true in any given clause, the corresponding term in the corresponding inequality evaluates to 1 (If x_i = 1 in the clause, so it is in the inequality; if x_i = 1 in the clause, 1 - x_i = 1 in the inequality). For each literal that evaluates to be false in any given clause, the corresponding term in the corresponding inequality evaluates to 0 (If x_i = 0 in the clause, so it is in the inequality; if x_i = 0 in the clause, 1 - x_i = 0 in the inequality). Therefore, x_i + x_j + x_k ≥ 1 always holds and so does every inequality constraint. Hence, there is an n-vector x of {0,1} so that A ⋅ x ≤ b. __

There is an n-vector x that solves A⋅x ≤ b where the values of x are either 0 or 1 ⇒ Φ is satisfiable

Proof. if A⋅x ≤ b has a solution where the values of x are either 0 or 1, use this value to set the corresponding variables in the clauses. Since the inequalities are satisfied, x_i + x_j + x_k ≥ 1 always holds, there is at least one 3 literal (x_i or 1 - x_i) evaluates to 1, and the corresponding xi or x_i evaluates to 1. So each clause is satisfied and 3-SAT has a satisfying truth assignment. __

[prev] [prev-tail] [front] [up]