Zobrazeno 1 - 10
of 23
pro vyhledávání: '"Amitabh Basu"'
Autor:
Amitabh Basu, Hongyi Jiang
Publikováno v:
Mathematical Programming. 197:411-426
We define a new cutting plane closure for pure integer programs called the two-halfspace closure. It is a natural generalization of the well-known Chv\'atal-Gomory closure. We prove that the two-halfspace closure is polyhedral. We also study the corr
Publikováno v:
Mathematics of Operations Research. 44:1264-1285
Jeroslow and Lowe gave an exact geometric characterization of subsets of [Formula: see text] that are projections of mixed-integer linear sets, also known as MILP-representable or MILP-R sets. We give an alternate algebraic characterization by showin
Publikováno v:
SIAM Journal on Discrete Mathematics. 33:755-783
We explore the lifting question in the context of cut-generating functions. Most of the prior literature on this question focuses on cut-generating functions that have the unique lifting property. ...
Autor:
Amitabh Basu
In the first part of this paper, we present a unified framework for analyzing the algorithmic complexity of any optimization problem, whether it be continuous or discrete in nature. This helps to formalize notions like "input", "size" and "complexity
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d1ecd8e7acae47ebae271d6715a7ee06
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 of BB and CP, when both are based on the same family of disjunctions.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::a4cc023898abe43c4adff47798e4925a
Publikováno v:
Mathematical Programming. 163:301-358
We develop foundational tools for classifying the extreme valid functions for the k-dimensional infinite group problem. In particular, we present the general regular solution to Cauchy's additive functional equation on restricted lower-dimensional co
Publikováno v:
Mathematical Programming. 161:451-485
Finite-dimensional linear programs satisfy strong duality (SD) and have the "dual pricing" (DP) property. The (DP) property ensures that, given a sufficiently small perturbation of the right-hand-side vector, there exists a dual solution that correct
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 valid function is dominated by some nonnegative valid function, modu
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::a41a8d5254ee025337d9d3473e679d69
http://arxiv.org/abs/1802.01499
http://arxiv.org/abs/1802.01499
We study quantitative criteria for evaluating the strength of valid inequalities for Gomory and Johnson’s finite and infinite group models, and we describe valid inequalities that are optimal for these criteria. We justify and focus on the criterio
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d71a84b1d630ffba45695b0307d0dbaa
http://arxiv.org/abs/1710.07672
http://arxiv.org/abs/1710.07672
Publikováno v:
Mathematical Programming. 151:153-189
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 form and Balas introduced intersection cuts for the corner polyhedron. T