My Ph.D. thesis was on constrained submodular function maximization. We introduced the notion of curvature of a submodular function, a concept that became popular, and related it to the performance of the greedy algorithm.
Together with M. R. Rao I started the study of the structure of Balanced matrices, characterized a subclass and found a polynomial recognition algorithm. With Gérard Cornuéjols and M.R. Rao we undertook the (ambitious) project of characterizing the structure of balanced matrices.
With Gérard, Ajay Kapoor and Kristina Vuskovic we proved a characterization of the balanced hypergraphs that have a perfect matching, that is in the spirit of Hall's condition. We then studied balanced matrices whose entries are 0,1,-1 and proved polyhedral characterizations (in terms of generalized set covering) together with min-max results. We characterized their structure and found an efficient recognition algorithm.
We also characterized the graphs that do not contain a hole of even length. This characterization gives a polynomial algorithm to test membership in such a class. We have a structural theorem for graphs that do not contain a hole of odd length. For graphs with bounded clique size, we have a polynomial algorithm to test membership in this class.
All these results rely on a theorem of Truemper on signed graphs. With Bert Gerards we gave a simple proof of this theorem. With Bert and Kanstantsin Pashkovic we investigated the use of decomposition theorems in constructing efficient optimization algorithms.
Together with Gérard we formulated a "replication" conjecture for matrices with the maxflow-mincut property that is still unsettled and is the counterpart of the (weak) perfect graph conjecture of Berge.
With Laurence Wolsey we investigated some (complicated) polyhedra that arise in Mixed-Integer Programming that are the projection of polyhedra defined by a Totally Unimodular system of inequalities, a quite unexpected application of TU. We also used Balas extended formulation for the union of polytopes to construct extended formulations for some mixed-integer polyhedra. Recently, with Marco Di Summa and Yuri Faenza we showed that Balas extended formulation for the union of polytopes is essentially the smallest.
With Marco di Summa we investigated Helly numbers, that relate the largest size of a minimal system of inequalities that is infeasible (in the reals, the integers..). This theory is used to construct geometric certificates for optimality for minimization of convex functions over sets with bounded Helly number.
Together with Gérard, Giacomo Zambelli, Amitabh Basu, Marco Di Summa, Joseph Paat, I have worked on the infinite models in Integer Programming. We have given several constructions for "complicated" extreme cut-generating functions. With Amitabh, Marco, and Joseph we have studied internal and external representations of various infinite models, a paper that (I think) is fundamental in this field. With Amitabh and Marco we have introduced a "volume" criterion to measure the quality of a cut-generating function and showed that the Gomory function is optimal in this respect.
The convex-analysis perspective of this theory was studied by Gérard, Aris Daniilidis, Claude Lemarechal, Jerome Malik and myself.
With Laurence and Giovanni Rinaldi we studied the cut-dominant polyhedron. Many more results were obtained with Samuel Fiorini and Kanstantsin Pashkovic.