Date

2017

Document Type

Thesis

Degree

Master of Science

Department

Management Science

First Adviser

Takáč, Martin

Other advisers/committee members

Terlaky, Tamás

Abstract

Seriation problem is widely used in many fields like archeology\cite{robinson1951method} and shotgun gene sequencing\cite{garriga2011banded,meidanis1998consecutive}. It aims to reorder a linear permutation based on given similarity information and it is an optimization problem over the set of permutation. Due to the large size of feasible set and the variable type, the seriation is an NP-hard quadratic mixed integer programming(MIP) problem. In order to solve this problem efficiently, a construction proposed recently by Goemans\cite{goemans2015smallest}, sorting network is used to constrain the solutions of the problem to be permutation and reformulate the problem. And we solve the MIP problem using heuristic method and branch and bound method and compare their performance.

Share

COinS