MIP formulations for induced graph optimization problems: a tutorial

Given a graph G=(V,E)$G=(V,E)$ and a subset of its vertices V′⊆V$V^{\prime }\subseteq V$, the subgraph induced by V′$V^{\prime }$ in G is that with vertex set V′$V^{\prime }$ and edge set E′$E^{\prime }$ formed by all the edges in E linking two vertices in V′$V^{\prime }$. Mixed integer programming...

Full description

Saved in:
Bibliographic Details
Published in:International transactions in operational research 2023-11, Vol.30 (6), p.3159-3200
Main Authors: Melo, Rafael A., Ribeiro, Celso C.
Format: Article
Language:English
Subjects:
Apexes
Combinatorial analysis
combinatorial optimization
feedback vertex set
Graph theory
induced graphs
induced paths
Integer programming
Linear programming
Literature reviews
Mixed integer
networks
Operations research
Optimization
quasi‐cliques
Trees (mathematics)
Vertex sets
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Given a graph G=(V,E)$G=(V,E)$ and a subset of its vertices V′⊆V$V^{\prime }\subseteq V$, the subgraph induced by V′$V^{\prime }$ in G is that with vertex set V′$V^{\prime }$ and edge set E′$E^{\prime }$ formed by all the edges in E linking two vertices in V′$V^{\prime }$. 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.
ISSN:0969-6016
1475-3995
DOI:10.1111/itor.13299