Assignment round three

Objective

The goal is to solve two optimization problems by encoding them as integer programming problems which are then solved the MIP solver lp_solve.

For the first problem pick the optimization version of one of the problems, Circuit Board Partitioning, Frequency Allocation or Spin Glass, which you did not use in the rounds one and two. Create a program that takes a problem instance (a graph file) as input and prints a solution to the problem as output in the format described in the problem page.

For the second problem consider the DNA String Embedding problem. Create a program that takes a problem instance (a graph file) as input and prints a solution to the problem as output in the format described in the problem page.

The recommended language for the programs is Java, as you can use the provided Graph-classes to load problem instances and the examples of doing encodings given here. However, you may use any program language available on the computers at the Computing Centre at TKK.

Deliverable

Return the commented source code and a small report describing your approach and results to airusane(at)tcs.hut.fi. Measure the execution time.

Grading

For correct solution returned on first try: 2p
on second try: 1p
on third/subsequent tries: 0p