Rice Header
CAAM Header

Graduate Seminar - 3/22, 12:00PM Duncan Hall 1064

Tayo Ajayi

"Assessing the Tightness of Linear Programming Relaxations"

We provide formulations to compute exact bounds on the gap function, the difference between an integer program and linear programming relaxation, over a set of right-hand sides. The gap function, which can evaluate the quality of the model, is foundational to integer programming theory, but the few studies over the past half-century either do not provide exact bounds or use abstract algebraic techniques that require large pre-calculations. Our formulation to compute the supremum of the gap function over an integer lattice incorporates the superadditive dual and extends to continuous sets of right-hand sides.

Department of Computational and Applied Mathematics
6100 Main MS-134   Houston, TX 77005   713.348.4805

Rice University   |   School of Engineering   |   J. Joyce Young Memorial Fund   |   Pearlman Memorial Fund   |   Weiser Memorial Fund   |   Contact