OR Seminar - Francesco Pisanu

Francesco Pisanu (CORE)

will give a presentation on :

Hard problems on box-totally dual integral polyhedra

Abstract : 

A rational linear system is Totally Dual Integral (TDI) if for every integer linear function for which the optimum is finite the associated dual problem has an integer optimal solution. A TDI system is box-TDI if adding any rational bounds on the variables preserves its TDIness. Box-TDI systems are systems that yield strong min-max relations such as the one involved in the Max Flow-Min Cut Theorem of Ford and Fulkerson.  Cook proved that box-TDIness is a polyhedral property, therefore polyhedra that can be described by box-TDI systems are called box-TDI polyhedra. 

Box-TDI polyhedra characterize the following generalization of the well-known totally unimodular matrices. A matrix is totally equimodular (TE) if for each subset of linearly independent rows, the corresponding nonzero maximal minors have the same absolute value. A matrix A is TE if and only if any polyhedron described by A is box-TDI for each rational RHS.

In this work, we prove that the problem of deciding whether a given polyhedron is box-TDI is co-NP-complete. We also prove that the edge-vertex incidence matrix of any graph is TE. As a consequence of Karp's hardness result on the maximum stable set problem, this implies that integer programming over box-TDI polyhedra is NP-hard.

This is a joint work with Patrick Chervet, Roland Grappe, Mathieu Lacroix, and Roberto Wolfler Calvo.