DM811 - Heuristics for Combinatorial Optimization
Sheet 2, Autumn 2010 [pdf format]

Prepare the following exercises for discussion in class on Friday November 26.

Exercise 1

Definition 1  (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. show how the decision version of the graph coloring problem (GCP) can be encoded in a SAT problem
  2. show how the constraint satisfaction problem (CSP) can be encoded in a SAT problem
  3. are the results of the two previous points proves of the NP-completeness of the CSP and GCP?
  4. devise preprocessing rules, ie, polynomial time simplification rules
  5. design one or more construction heuristics for the problem
  6. apply the methods devised in the two previous points on the instances available at the SATLIB repository: http://www.cs.ubc.ca/~hoos/SATLIB/benchm.html

Exercise 2

Definition 2  Bin Packing Problem

Input: A finite set U of items, a size s(u) ∈ Z+ for each u∈ U, and a positive integer bin capacity B.

Task: Find the minimal number of bins K for which there exits a partition of U into disjoint sets U1, U2, …,Uk and the sum of the sizes of the items in each Ui is B or less.

Definition 3  Two-dimensional bin packing

Input: A finite set U of rectangular items, each with a width wu ∈ Z+ and a height hu ∈ Z+, u ∈ U, and an unlimited number of identical rectangular bins of width W ∈ Z+ and height H ∈ Z+.

Task: Allocate all the items into a minimum number of bins, such that the bin widths and heights are not exceeded and the original orientation is respected (no rotation of the items is allowed).

  1. Discuss differences between the Bin packing problem and the Knapsack problem.
  2. Design construction heuristics for the 1D and 2D Bin Packing problems
  3. Consider the extension of the Bin Packing problem in which bins have variable size. More precisely, each bin in the set B is of a different type k and for each type we are given a cost ck and a capacity Wk. We are asked to minimize the total cost of used bins. Modify the heuristics at the previous point to handle this version of the problem.