iterative method

the task is to use an iterative method of calculation the best possible assignment for a propositional formula
to describe and implement.

Task :
A propositional formula is included in the material for this task sheet
n = 100 variables A1, A2, . . . , On given. The formula is in conjunctive normal form. A clause C of the formula is replaced by a subset
TC ⊆ {1, 2, . . . , n} ∪ {−1, −2, . . . , −n}

coded as follows:
• Ai occurs in C if and only if i ∈ TC.
• ¬Ai occurs in C if and only if −i ∈ TC.
An occupancy is sought
b : {A1, A2, . . . , On} → {true, false},
such that the number τ (b) of clauses in the formula that are true under the assignment b is as large as possible.
(a) First describe your idea for an iterative procedure for ¨
this optimization problem.

• How do you choose the starting allocation b0?
• How do you get an assignment bi+1 with τ (bi) < τ (bi+1) from an existing assignment bi?
• When do you stop the iteration?

(b) Implement what you described in subtask (a).
Process in a separate program.

(c) Apply your program from part (b) to the formula given in the material for this exercise sheet. Is yours
Program output occupancy b a global optimum? Document your approach to investigating this issue.