MIP formulations for induced graph optimization problems: a tutorial

Rafael A. Melo

doi:10.1111/itor.13299

Return

MIP formulations for induced graph optimization problems: a tutorial

2023-04-17

PRE

Rafael A. Melo *

Celso C. Ribeiro

DOI：10.1111/itor.13299

Original

Original request for help

Save

Abstract

En 中文

Given a graph G = (V, E) and a subset of its vertices V ' subset of V, the subgraph induced by V ' in G is that with vertex set V ' and edge set E ' formed by all the edges in E linking two vertices in V '. Mixed integer programming (MIP) approaches are among the most successful techniques for solving induced graph optimization problems, that is, those related to obtaining maximum or minimum (weighted or not) induced subgraphs with certain properties. In this tutorial, we provide a literature review of some of these problems. Furthermore, we illustrate the use of MIP formulations and techniques for solving combinatorial optimization problems involving induced graphs. We focus on compact formulations and those with an exponential number of constraints that can be effectively solved using branch-and-cut procedures. More specifically, we revisit applications of their use for problems of finding induced forests (which correspond to the complement of feedback vertex sets), trees, paths, as well as quasi-clique partitionings.

Keywords:

combinatorial optimization

integer programming

induced graphs

feedback vertex set

induced paths

quasi-cliques

networks