Amitabh Basu
Amitabh Basu has a total of 10 co-authors. Here are the top co-authors by number of shared publications:
- Gérard Cornuéjols
Carnegie Mellon University
7 shared publications - Matthias Köppe
Department of Mathematics, University of California, Davis, California 95616
6 shared publications - Giacomo Zambelli
Department of Mathematics, London School of Economics and Political Science, London WC2A 2AE, United Kingdom
3 shared publications - Robert Hildebrand
University of California
3 shared publications - François Margot
Carnegie Mellon University
2 shared publications - Manoel Campêlo
Dep. Estatística e Matemática Aplicada Universidade Federal do Ceará Brazil
2 shared publications
Latest Publications
- Open Access
Unique lifting of integer variables in minimal inequalities
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 AccessUnique lifting of integer variables in minimal inequalities
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
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 AccessUnique Minimal Liftings for Simplicial Polytopes
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
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.
Open AccessEquivariant Perturbation in Gomory and Johnson's Infinite Group Problem. I. The One-Dimensional Case
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.
- 23 February 2013
- Published by Springer Nature in Mathematical Programming
- Vol. 145 (1-2) , 19-58
The triangle closure is a polyhedron
- 23 February 2013
- Published by Springer Nature in Mathematical Programming
- Vol. 145 (1-2) , 19-58
The triangle closure is a polyhedron
- Open Access
The Triangle Closure is a Polyhedron
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.Open AccessThe Triangle Closure is a Polyhedron
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. - 2 June 2012
- Published by Springer Nature in Mathematical Programming
- Vol. 141 (1-2) , 561-576
Unique lifting of integer variables in minimal inequalities
- 2 June 2012
- Published by Springer Nature in Mathematical Programming
- Vol. 141 (1-2) , 561-576
Unique lifting of integer variables in minimal inequalities
- 1 May 2012
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 37 (2) , 346-355
Unique Minimal Liftings for Simplicial Polytopes
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.
- 1 May 2012
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 37 (2) , 346-355
Unique Minimal Liftings for Simplicial Polytopes
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.
- 1 February 2012
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 37 (1) , 21-40
Intersection Cuts with Infinite Split Rank
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.
- 1 February 2012
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 37 (1) , 21-40
Intersection Cuts with Infinite Split Rank
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.
- 1 November 2011
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
- Vol. 23 (4) , 578-590
Experiments with Two-Row Cuts from Degenerate Tableaux
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.
- 1 November 2011
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
- Vol. 23 (4) , 578-590
Experiments with Two-Row Cuts from Degenerate Tableaux
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
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.
Open AccessA (k+1)-Slope Theorem for the k-Dimensional Infinite Group Relaxation
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.