Optimization Online


The Gap Function: Evaluating Integer Programming Models over Multiple Right-hand Sides

Temitayo Ajayi (temitayo.ajayi***at***rice.edu)
Christopher Thomas (cthomas***at***bazean.com)
Andrew Schaefer (andrew.schaefer***at***rice.edu)

Abstract: For an integer programming model with fixed data, the linear programming relaxation gap is considered one of the most important measures of model quality. There is no consensus, however, on appropriate measures of model quality that account for data variation. In particular, when the right-hand side is not known exactly, one must assess a model based on its behavior over many right-hand sides. Gap functions are the linear programming relaxation gaps parametrized by the right-hand side. Despite drawing research interest in the early days of integer programming (Gomory 1965), the properties and applications of these functions have been little studied. In this paper, we construct measures of integer programming model quality over sets of right-hand sides based on the absolute and relative gap functions. In particular, we formulate optimization problems to compute the expectation and extrema of gap functions over finite discrete sets and bounded hyper-rectangles. These optimization problems are linear programs (albeit of an exponentially large size) that contain at most one special ordered set constraint. These measures for integer programming models, along with their associated formulations, provide a framework for determining a modelís quality over a range of right-hand sides.

Keywords: Gap function, linear programming relaxation, philosophy of modeling, superadditive duality

Category 1: Integer Programming (Other )


Download: [PDF]

Entry Submitted: 10/29/2018
Entry Accepted: 10/30/2018
Entry Last Modified: 06/18/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society