DM811 - Heuristics for Combinatorial Optimization
Exercise Sheet 1, Autumn 2011 [pdf format]

Prepare the following exercises for discussion in class on Monday September 12.

Exercise 1

Definition 1  Travelling Salesman Problem

Input: A graph G=(V,E) and a cost function ω: V× V ↦ R.

Task: Find an Hamiltonian cycle of minimum cost.

Design at least one construction heuristic and at least one local search (solution representation + neighborhood + evaluation function).

Exercise 2

Definition 2  (Maximum) K-Satisfiability (SAT)

Input: A set U of variables, a collection C of disjunctive clauses of at most k literals, where a literal is a variable or a negated variable in U. k is a constant, k≥ 2.

Task: A truth assignment for U or an truth assignment that maximizes the number of clauses satisfied.

  1. design one or more construction heuristics for the problem
  2. show how the decision version of the graph coloring problem (GCP) can be encoded in a SAT problem
  3. show how the constraint satisfaction problem (CSP) can be encoded in a SAT problem
  4. are the results of the two previous points proves of the NP-completeness of the CSP and GCP?
  5. devise preprocessing rules, ie, polynomial time simplification rules