Reduction of satisfiability to integer linear programming
up vote
0
down vote
favorite
Given an instance of SAT, how do I exhibit that instance of SAT into ILP? Do I have to find the satisfying assignment for f first or does this not matter?
computational-complexity
asked Nov 18 at 14:03
C.Lako
263
add a comment |
up vote
0
down vote
favorite
Given an instance of SAT, how do I exhibit that instance of SAT into ILP? Do I have to find the satisfying assignment for f first or does this not matter?
computational-complexity
asked Nov 18 at 14:03
C.Lako
263
You're going to produce an ILP whose solution (if it exists) can be transformed back into a solution of the original SAT problem. You don't need to find a satisfying assignment first (and one might not exist.)
– Brian Borchers
Nov 18 at 15:43
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Given an instance of SAT, how do I exhibit that instance of SAT into ILP? Do I have to find the satisfying assignment for f first or does this not matter?
computational-complexity
asked Nov 18 at 14:03
C.Lako
263
Given an instance of SAT, how do I exhibit that instance of SAT into ILP? Do I have to find the satisfying assignment for f first or does this not matter?
computational-complexity
computational-complexity
asked Nov 18 at 14:03
C.Lako
263
asked Nov 18 at 14:03
C.Lako
263
asked Nov 18 at 14:03
C.Lako
263
asked Nov 18 at 14:03
C.Lako
263
asked Nov 18 at 14:03
C.Lako
263
263
You're going to produce an ILP whose solution (if it exists) can be transformed back into a solution of the original SAT problem. You don't need to find a satisfying assignment first (and one might not exist.)
– Brian Borchers
Nov 18 at 15:43
add a comment |
You're going to produce an ILP whose solution (if it exists) can be transformed back into a solution of the original SAT problem. You don't need to find a satisfying assignment first (and one might not exist.)
– Brian Borchers
Nov 18 at 15:43
You're going to produce an ILP whose solution (if it exists) can be transformed back into a solution of the original SAT problem. You don't need to find a satisfying assignment first (and one might not exist.)
– Brian Borchers
Nov 18 at 15:43
You're going to produce an ILP whose solution (if it exists) can be transformed back into a solution of the original SAT problem. You don't need to find a satisfying assignment first (and one might not exist.)
– Brian Borchers
Nov 18 at 15:43
add a comment |
1 Answer
1
active
oldest
votes
up vote
0
down vote
Recall that in SAT, you are given a Boolean formula:
$F = (x_1 + x_2 + bar{x_2}) * (x_4 + x_5) + ... $
Note that $F$ is satisfiable iff every clause is satisfiable.
That is, for each clause, at least one of the $x_i$ is true.
If we represent true by 1 and false by 0, we can reduce SAT to ILP by creating a constraint for each clause:
$x_1 + + x_2 + bar{x_2} ge 1$
$x_4 + + x_5 ge 1$
...
answered Nov 25 at 0:02
user137481
1,7752921
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
Recall that in SAT, you are given a Boolean formula:
$F = (x_1 + x_2 + bar{x_2}) * (x_4 + x_5) + ... $
Note that $F$ is satisfiable iff every clause is satisfiable.
That is, for each clause, at least one of the $x_i$ is true.
If we represent true by 1 and false by 0, we can reduce SAT to ILP by creating a constraint for each clause:
$x_1 + + x_2 + bar{x_2} ge 1$
$x_4 + + x_5 ge 1$
...
answered Nov 25 at 0:02
user137481
1,7752921
add a comment |
up vote
0
down vote
Recall that in SAT, you are given a Boolean formula:
$F = (x_1 + x_2 + bar{x_2}) * (x_4 + x_5) + ... $
Note that $F$ is satisfiable iff every clause is satisfiable.
That is, for each clause, at least one of the $x_i$ is true.
If we represent true by 1 and false by 0, we can reduce SAT to ILP by creating a constraint for each clause:
$x_1 + + x_2 + bar{x_2} ge 1$
$x_4 + + x_5 ge 1$
...
answered Nov 25 at 0:02
user137481
1,7752921
add a comment |
up vote
0
down vote
up vote
0
down vote
Recall that in SAT, you are given a Boolean formula:
$F = (x_1 + x_2 + bar{x_2}) * (x_4 + x_5) + ... $
Note that $F$ is satisfiable iff every clause is satisfiable.
That is, for each clause, at least one of the $x_i$ is true.
If we represent true by 1 and false by 0, we can reduce SAT to ILP by creating a constraint for each clause:
$x_1 + + x_2 + bar{x_2} ge 1$
$x_4 + + x_5 ge 1$
...
answered Nov 25 at 0:02
user137481
1,7752921
Recall that in SAT, you are given a Boolean formula:
$F = (x_1 + x_2 + bar{x_2}) * (x_4 + x_5) + ... $
Note that $F$ is satisfiable iff every clause is satisfiable.
That is, for each clause, at least one of the $x_i$ is true.
If we represent true by 1 and false by 0, we can reduce SAT to ILP by creating a constraint for each clause:
$x_1 + + x_2 + bar{x_2} ge 1$
$x_4 + + x_5 ge 1$
...
answered Nov 25 at 0:02
user137481
1,7752921
answered Nov 25 at 0:02
user137481
1,7752921
answered Nov 25 at 0:02
user137481
1,7752921
answered Nov 25 at 0:02
user137481
1,7752921
1,7752921
add a comment |
add a comment |
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3003572%2freduction-of-satisfiability-to-integer-linear-programming%23new-answer', 'question_page');
}
);
Post as a guest
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
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
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
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
You're going to produce an ILP whose solution (if it exists) can be transformed back into a solution of the original SAT problem. You don't need to find a satisfying assignment first (and one might not exist.)
– Brian Borchers
Nov 18 at 15:43