Extended formulations from separation oracles

Matheus Ota

Abstract

I will present part of the results in the paper “Using separation algorithms to generate mixed integer model reformulations” by R. Kipp Martin (1991). We will see a general technique for obtaining extended formulations for problems whose separation problem can be formulated as a linear program. Throughout the whole discussion we will keep revisiting the Minimum Spanning Tree (MST) case. In the end, we will also see a connection between the obtained extended formulation for MSTs and slack matrices. This last part is based on the classical paper of Yannakakis “Expressing Combinatorial Optimization Problems by Linear Programs”.

Date
Mar 10, 2023 12:00 PM
Location
MC6029 or Zoom
Paper(s)
Link and link