  Graph theory has been a powerful tool in solving difficult and complex
problems arising in all disciplines. In particular, graph matching is a
classical problem in pattern analysis with enormous applications. Many graph
problems have been formulated as a mathematical program and then solved using
exact, heuristic, and/or approximated-guaranteed procedures. On the other hand,
graph theory has been a powerful tool in visualizing and understanding complex
mathematical programming problems, especially integer programs. Formulating a
graph problem as a natural integer program (IP) is often a challenging task.
However, an IP formulation of the problem has many advantages. Several
researchers have noted the need for natural IP formulation of graph theoretic
problems. The present study aims to provide a unified framework for IP
formulation of graph-matching problems. Although there are many surveys on
graph matching problems, none is concerned with IP formulation. This paper is
the first to provide a comprehensive IP formulation for such problems. The
framework includes a variety of graph optimization problems in the literature.
While these problems have been studied by different research communities,
however, the framework presented here helps to bring efforts from different
disciplines to tackle such diverse and complex problems. We hope the present
study can significantly help to simplify some of the difficult problems arising
in practice, especially in pattern analysis.
