DM841 (E23) -  Heuristics and Constraint Programming for
Discrete Optimization

Sheet 5

Task 1

Convert the following propositional logic sentence in conjunctive normal form:

\[x_{1} \iff (x_{2} \lor x_{3})\]

Task 2

For the CNF formula attained at the previous task, design an efficient backtracking algorithm. Start with a basic structure and then try to refine it by adding forward checking mechanisms, that is, after the assignment of a variable consider how to simplify the problem that is left or how to detect an early termination of the branch, that is, before all variables are assigned.

Task 3

Implement in Python the backtracking algorithm designed at Task 2 and use it to solve the SAT instance in CNF from Task 1.

Use the DIMACS-CNF format for encoding the instance in an input file. In this format, each line represents a single disjunction. For example, a file with the two lines

1 -5 4 0 
-1 5 3 4 0

represents the formula

\[(x_1 \lor \neg x_5 \lor x_4) \land (\neg x_1 \lor x_5 \lor x_3 \lor x_4)\]

Alternatively, use the format for this formula in the 7-bit ASCII representation

(x1 | ~x5 | x4) & (~x1 | x5 | x3 | x4)

Retrieve and use the SAT solvers: MiniSAT, Lingeling, or others listed at the SAT Competition page to solve the same instance from Task 1 and compare the results with your solution.

Task 4

You have received two reports to review in your git repository. Reviews are done by annotating the PDF files that you have received. The submission is done by pushing the annotations via git.

Deadeline: Friday 10th at noon.

Here you find some motivations and instructions on how to provide feedback.

The effect of peer feedback is two-fold:

  1. learners receive feedback from their peers, which they can use as much as they would use feedback from an instructor, and
  2. learners provide feedback to others, developing their metacognitive skills in evaluating their own work as well as important communication and teamwork skills.

Some studies have shown that giving feedback is just as effective, or more so, for improving a learner’s understanding and communication of a topic than receiving feedback.

The literature identifies good feedback as that which allows the receiver to improve their self-regulation, and further describes it based on three characteristics: Informativeness, Polarity, and Timelines.

  • Polarity refers to the tone of the feedback, whether it is reinforcing good practice, or correcting a mistake.
  • Timeliness, meanwhile, refers to when the feedback is received, for example, in the moment, end of class, or the following day.
  • Informativeness refers to the extent to which the comments contain both feed-back and feed-forward components.
    • Feed-back elements communicate to a learner their progress toward a certain goal or expected outcome. These elements can also reinforce successful strategies or methods used towards the goal.
    • Feed-forward elements direct the learner on possible future behaviors. This may include suggesting strategies or alternate approaches.

A problem solving process can be divided into four phases that include: exploration, planning, solving, communicating, and reviewing (critical thinking in concluding remarks). Feedback on this work can be organized in tiers.

Feedback tiers

  1. Least Robust Annotations of this tier are generic and lack constructive feedback for the author. They are not relating to any specific part of the problem solving phase. Example: “it was good”.

  2. Somewhat Robust These annotations lack specific details and provide little or no elaboration aside from the mathematics. The feedback is vague and not clearly explained. Example: “I hadn’t thought of the way you modelled the problem. Although while you were explaining it, it became clear.”

  3. Robust These annotations attempt to elaborate on a specific part of the problem solving process. Feedback may attempt to connect to the problem solving phases, with specificity. Example: “I agree with your answer but maybe next time make present the problem using more precise mathematical symbols and models.”

  4. More Robust These annotations also identify specific components of the problem solving process or issues related with them. Feedback may connect specific components of the work in the solving phases but lack recommendations for next steps. Example: “My model was exactly like yours. I think I just used the global constraint alldiff for ensuring everybody is allocated.”

  5. Most Robust These annotations identify relevant components of the problem-solving process in a more elaborate fashion while also providing helpful feedback that is likely to support peer-to-peer learning. Example: “I respectfully disagree with you on the last pieces of your model. The constraint (3) that should have modeled the fact that a room is used only by one class at a time does not forbid this to happen. You should have reversed the ineqaulity and asked instead that the left hand side be smaller or equal than one (instead of larger or equal).