ABAmitabh Basu

Amitabh Basu

*This is an algorithmically generated author record based on publicly available information.

Amitabh Basu has a total of 10 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Unique lifting of integer variables in minimal inequalities

    by Amitabh Basu, Manoel Campelo, Michele Conforti, Gerard Cornuejols, Giacomo Zambelli

    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 tableau form where all the nonbasic variables are continuous; they are derived using the gauge function of maximal lattice-free convex sets. In this paper we study lifting functions for the nonbasic integer variables starting from such minimal valid inequalities. We characterize precisely when the lifted coefficient is equal to the coefficient of the corresponding continuous variable in every minimal lifting. The answer is a nonconvex region that can be obtained as a finite union of convex polyhedra. We then establish a necessary and sufficient condition for the uniqueness of the lifting function.

  • Open Access

    Unique Minimal Liftings for Simplicial Polytopes

    by Amitabh Basu, Gérard Cornuéjols, Matthias Köppe

    For a minimal inequality derived from a maximal lattice-free simplicial polytope in $\R^n$, we investigate the region where minimal liftings are uniquely defined, and we characterize when this region covers $\R^n$. We then use this characterization to show that a minimal inequality derived from a maximal lattice-free simplex in $\R^n$ with exactly one lattice point in the relative interior of each facet has a unique minimal lifting if and only if all the vertices of the simplex are lattice points.

  • Open Access

    Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. I. The One-Dimensional Case

    by Amitabh Basu, Robert Hildebrand, Matthias Köppe

    We give an algorithm for testing the extremality of minimal valid functions for Gomory and Johnson's infinite group problem that are piecewise linear (possibly discontinuous) with rational breakpoints. This is the first set of necessary and sufficient conditions that can be tested algorithmically for deciding extremality in this important class of minimal valid functions. We also present an extreme function that is a piecewise linear function with some irrational breakpoints, whose extremality follows from a new principle.

  • The triangle closure is a polyhedron

    by Amitabh Basu, Robert Hildebrand, Matthias Köppe


  • Open Access

    The Triangle Closure is a Polyhedron

    by Amitabh Basu, Robert Hildebrand, Matthias Köppe

    Recently, cutting planes derived from maximal lattice-free convex sets have been studied intensively by the integer programming community. An important question in this research area has been to decide whether the closures associated with certain families of lattice-free sets are polyhedra. For a long time, the only result known was the celebrated theorem of Cook, Kannan and Schrijver who showed that the split closure is a polyhedron. Although some fairly general results were obtained by Andersen, Louveaux and Weismantel [ An analysis of mixed integer linear sets based on lattice point free convex sets, Math. Oper. Res. 35 (2010), 233--256] and Averkov [On finitely generated closures in the theory of cutting planes, Discrete Optimization 9 (2012), no. 4, 209--215], some basic questions have remained unresolved. For example, maximal lattice-free triangles are the natural family to study beyond the family of splits and it has been a standing open problem to decide whether the triangle closure is a polyhedron. In this paper, we show that when the number of integer variables $m=2$ the triangle closure is indeed a polyhedron and its number of facets can be bounded by a polynomial in the size of the input data. The techniques of this proof are also used to give a refinement of necessary conditions for valid inequalities being facet-defining due to Cornu\'ejols and Margot [On the facets of mixed integer programs with two integer variables and two constraints, Mathematical Programming 120 (2009), 429--456] and obtain polynomial complexity results about the mixed integer hull.

  • Unique lifting of integer variables in minimal inequalities

    by Amitabh Basu, Manoel Campêlo, Michele Conforti, Gérard Cornuéjols, Giacomo Zambelli


  • Unique Minimal Liftings for Simplicial Polytopes

    by Amitabh Basu, Gérard Cornuéjols, Matthias Köppe

    For a minimal inequality derived from a maximal lattice-free simplicial polytope in ℝn, we investigate the region where minimal liftings are uniquely defined, and we characterize when this region covers ℝn. We then use this characterization to show that a minimal inequality derived from a maximal lattice-free simplex in ℝn with exactly one lattice point in the relative interior of each facet has a unique minimal lifting if and only if all the vertices of the simplex are lattice points.


  • Intersection Cuts with Infinite Split Rank

    by Amitabh Basu, Gérard Cornuéjols, François Margot

    We consider mixed-integer linear programs where free integer variables are expressed in terms of nonnegative continuous variables. When this model only has two integer variables, Dey and Louveaux characterized the intersection cuts that have infinite split rank. We show that, for any number of integer variables, the split rank of an intersection cut generated from a rational lattice-free polytope L is finite if and only if the integer points on the boundary of L satisfy a certain “2-hyperplane property.” The Dey–Louveaux characterization is a consequence of this more general result.


  • Experiments with Two-Row Cuts from Degenerate Tableaux

    by Amitabh Basu, Pierre Bonami, Gérard Cornuéjols, François Margot

    There has been a recent interest in cutting planes generated from two or more rows of the optimal simplex tableau. One can construct examples of integer programs for which a single cutting plane generated from two rows dominates the entire split closure. Motivated by these theoretical results, we study the effect of adding a family of cutting planes generated from two rows on a set of instances from the MIPLIB library. The conclusion of whether these cuts are competitive with Gomory mixed-integer cuts is very sensitive to the experimental setup. In particular, we consider the issue of reliability versus aggressiveness of the cut generators, an issue that is usually not addressed in the literature.


  • Open Access

    A (k+1)-Slope Theorem for the k-Dimensional Infinite Group Relaxation

    by Amitabh Basu, Robert Hildebrand, Matthias Köppe, Marco Molinaro

    We prove that any minimal valid function for the k-dimensional infinite group relaxation that is piecewise linear with at most k+1 slopes and does not factor through a linear map with non-trivial kernel is extreme. This generalizes a theorem of Gomory and Johnson for k=1, and Cornuejols and Molinaro for k=2.