The Gap Function: Evaluating Integer Programming Models over Multiple Right-Hand Sides
针对右端项不确定的整数规划模型，基于绝对和相对间隙函数构建了衡量模型质量的指标，并转化为线性规划问题来计算期望和极值，为评估模型在多个右端项下的表现提供了框架。
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, 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 hyperrectangles. 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.