77 citations · 221 across the 23 of their papers we have counts for
29 papers
Steiner Cut Dominants
Michele Conforti, Volker Kaibel
For a subset T of nodes of an undirected graph G, a T-Steiner cut is a cut δ(S) where S intersects both T and the complement of T. The T-Steiner cut dominant} of G is the dominant…
Helly systems and certificates in optimization
Amitabh Basu, Tongtong Chen, Michele Conforti +1
Inspired by branch-and-bound and cutting plane proofs in mixed-integer optimization and proof complexity, we develop a general approach via Hoffman's Helly systems. This helps to d…
Slack matrices, -products, and -level polytopes
Manuel Aprile, Michele Conforti, Yuri Faenza +3
In this paper, we study algorithmic questions concerning products of matrices and their consequences for recognition algorithms for polyhedra. The 1-product of matrices , $S_2…
Binary extended formulations and sequential convexification
Manuel Aprile, Michele Conforti, Marco Di Summa
A binarization of a bounded variable is a linear formulation with variables and additional binary variables , so that integrality of is implied by the i…
Complexity of branch-and-bound and cutting planes in mixed-integer optimization -- II
Amitabh Basu, Michele Conforti, Marco Di Summa +1
We study the complexity of cutting planes and branching schemes from a theoretical point of view. We give some rigorous underpinnings to the empirically observed phenomenon that co…
Complexity of branch-and-bound and cutting planes in mixed-integer optimization
Amitabh Basu, Michele Conforti, Marco Di Summa +1
We investigate the theoretical complexity of branch-and-bound (BB) and cutting plane (CP) algorithms for mixed-integer optimization. In particular, we study the relative efficiency…
Split cuts in the plane
Amitabh Basu, Michele Conforti, Marco Di Summa +1
We provide a polynomial time cutting plane algorithm based on split cuts to solve integer programs in the plane. We also prove that the split closure of a polyhedron in the plane h…
Recognizing Cartesian products of matrices and polytopes
Manuel Aprile, Michele Conforti, Yuri Faenza +3
The 1-product of matrices and is the matrix in whose columns ar…
Extended Formulations for Stable Set Polytopes of Graphs Without Two Disjoint Odd Cycles
Michele Conforti, Samuel Fiorini, Tony Huynh +1
Let be an -node graph without two disjoint odd cycles. The algorithm of Artmann, Weismantel and Zenklusen (STOC'17) for bimodular integer programs can be used to find a maxi…
The stable set problem in graphs with bounded genus and bounded odd cycle packing number
Michele Conforti, Samuel Fiorin, Tony Huynh +2
Consider the family of graphs without node-disjoint odd cycles, where is a constant. Determining the complexity of the stable set problem for such graphs is a lon…
Scanning integer points with lex-inequalities: A finite cutting plane algorithm for integer programming with linear objective
Michele Conforti, Marianna De Santis, Marco Di Summa +1
We consider the integer points in a unimodular cone K ordered by a lexicographic rule defined by a lattice basis. To each integer point x in K we associate a family of inequalities…
An extreme function which is nonnegative and discontinuous everywhere
Amitabh Basu, Michele Conforti, Marco Di Summa
We consider Gomory and Johnson's infinite group model with a single row. Valid inequalities for this model are expressed by valid functions and it has been recently shown that any…
Balas formulation for the union of polytopes is optimal
Michele Conforti, Marco Di Summa, Yuri Faenza
A celebrated theorem of Balas gives a linear mixed-integer formulation for the union of two nonempty polytopes whose relaxation gives the convex hull of this union. The number of i…
Optimal cutting planes from the group relaxations
Amitabh Basu, Michele Conforti, Marco Di Summa +1
We study quantitative criteria for evaluating the strength of valid inequalities for Gomory and Johnson's finite and infinite group models and we describe the valid inequalities th…
A geometric approach to cut-generating functions
Amitabh Basu, Michele Conforti, Marco Di Summa
The cutting-plane approach to integer programming was initiated more that 40 years ago: Gomory introduced the corner polyhedron as a relaxation of a mixed integer set in tableau fo…
Unique lifting of integer variables in minimal inequalities
Amitabh Basu, Manoel Campelo, Michele Conforti +2
This paper contributes to the theory of cutting planes for mixed integer linear programs (MILPs). Minimal valid inequalities are well understood for a relaxation of an MILP in tabl…
A Counterexample to a Conjecture of Gomory and Johnson
Amitabh Basu, Michele Conforti, Gerard Cornuejols +1
In Mathematical Programming 2003, Gomory and Johnson conjecture that the facets of the infinite group problem are always generated by piecewise linear functions. In this paper we g…
Maximal lattice-free convex sets in linear subspaces
Amitabh Basu, Michele Conforti, Gerard Cornuejols +1
We consider a model that arises in integer programming, and show that all irredundant inequalities are obtained from maximal lattice-free convex sets in an affine subspace. We also…
Minimal inequalities for an infinite relaxation of integer programs
Amitabh Basu, Michele Conforti, Gerard Cornuejols +1
We show that maximal -free convex sets are polyhedra when is the set of integral points in some rational polyhedron of . This result extends a theorem of Lovás…
Extreme functions with an arbitrary number of slopes
Amitabh Basu, Michele Conforti, Marco Di Summa +1
For the one dimensional infinite group relaxation, we construct a sequence of extreme valid functions that are piecewise linear and such that for every natural number , th…
The structure of the infinite models in integer programming
Amitabh Basu, Michele Conforti, Marco Di Summa +1
The infinite models in integer programming can be described as the convex hull of some points or as the intersection of halfspaces derived from valid functions. In this paper we st…
Optimality certificates for convex minimization and Helly numbers
Amitabh Basu, Michele Conforti, Gérard Cornuéjols +2
We consider the problem of minimizing a convex function over a subset of R^n that is not necessarily convex (minimization of a convex function over the integer points in a polytope…
Cut dominants and forbidden minors
Michele Conforti, Samuel Fiorini, Kanstantsin Pashkovich
The cut dominant of a graph is the unbounded polyhedron whose points are all those that dominate some convex combination of proper cuts. Minimizing a nonnegative linear function ov…
Subgraph Polytopes and Independence Polytopes of Count Matroids
Michele Conforti, Volker Kaibel, Matthias Walter +1
Given an undirected graph, the non-empty subgraph polytope is the convex hull of the characteristic vectors of pairs (F, S) where S is a non-empty subset of nodes and F is a subset…