  


The Gap Function: Evaluating Integer Programming Models over Multiple Righthand Sides
Temitayo Ajayi (temitayo.ajayirice.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 righthand side is not known exactly, one must assess a model based on its behavior over many righthand sides. Gap functions are the linear programming relaxation gaps parametrized by the righthand 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 righthand 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 righthand sides. Keywords: Gap function, linear programming relaxation, philosophy of modeling, superadditive duality Category 1: Integer Programming (Other ) Citation: Download: [PDF] Entry Submitted: 10/29/2018 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  