This Article Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Google Scholar Articles by Trapp, A. C. Articles by Prokopyev, O. A.

Solving the Order-Preserving Submatrix Problem via Integer Programming

Department of Industrial Engineering, University of Pittsburgh, Pittsburgh, Pennsylvania 15261
Department of Industrial Engineering, University of Pittsburgh, Pittsburgh, Pennsylvania 15261
act25{at}pitt.edu
prokopyev{at}engr.pitt.edu

In this paper we consider the order-preserving submatrix (OPSM) problem. This problem is known to be NP-hard. Although in recent years some heuristic methods have been presented to find OPSMs, they lack the guarantee of optimality. We present exact solution approaches based on linear mixed 0–1 programming formulations and develop algorithmic enhancements to aid in solvability. Encouraging computational results are reported both for synthetic and real biological data. In addition, we discuss theoretical computational complexity issues related to finding fixed patterns in matrices.

Key words: biclustering; order-preserving submatrix; data mining; integer programming
History: received August 2008; revised March 2009; accepted July 2009.