MAx2SAT is a computational problem with an input of k boolean clauses each consisting of 2 literals or ed together (eg z3VT5). The number of variables used will be called n. The goal is to find a truth assignment which maximizes the number of clauses that can be simultaneously satisfied. EXAMPLE: I (T1 v r2), (zi VT2), (T1 V z2), (T1 VT2) which satisfies 3 of the 4 clauses The solution for instance I is True, True TASK: For your project you will write a program which solves any given instance of MAx2SAT There is no known method to solve this problem in polynomial time So solutions with exponential time performance in the worst case are acceptable. However, it is expected that you will put a serious effort into beating the obvious brute force solution. In other words, writing a program that just performs a brute force search for the solution is a good place to start, but should not be where you end. In other words, you will not get full credit for only attempting a straightforward brute force search. Exactly what techniques you use are up to you. EG you might find a decent, but non-optimal solution using a greedy heuristic, improve it using local search, and then perform a branch and bound search. Your program should read the instance from a file called instance.txt which is formatted as 2 integers per line seperated by whitespace. Each line corresponds to a single clause. The absolute values of the variables are the two variables in the clause. If the first/second integer is negative it indicates that the first/second variable is negated. Using the example above the file instance.txt would contain 1 2 1 2 1 -2 MAx2SAT is a computational problem with an input of k boolean clauses each consisting of 2 literals or ed together (eg z3VT5). The number of variables used will be called n. The goal is to find a truth assignment which maximizes the number of clauses that can be simultaneously satisfied. EXAMPLE: I (T1 v r2), (zi VT2), (T1 V z2), (T1 VT2) which satisfies 3 of the 4 clauses The solution for instance I is True, True TASK: For your project you will write a program which solves any given instance of MAx2SAT There is no known method to solve this problem in polynomial time So solutions with exponential time performance in the worst case are acceptable. However, it is expected that you will put a serious effort into beating the obvious brute force solution. In other words, writing a program that just performs a brute force search for the solution is a good place to start, but should not be where you end. In other words, you will not get full credit for only attempting a straightforward brute force search. Exactly what techniques you use are up to you. EG you might find a decent, but non-optimal solution using a greedy heuristic, improve it using local search, and then perform a branch and bound search. Your program should read the instance from a file called instance.txt which is formatted as 2 integers per line seperated by whitespace. Each line corresponds to a single clause. The absolute values of the variables are the two variables in the clause. If the first/second integer is negative it indicates that the first/second variable is negated. Using the example above the file instance.txt would contain 1 2 1 2 1 -2
