Paper Info
Title
How tight is the corner relaxation?
Abstract
Given a mixed-integer linear programming (MILP) model and an optimal basis of the associated linear programming relaxation, the Gomory's corner relaxation is obtained by dropping nonnegativity constraints on the basic variables. Although this relaxation received a considerable attention in the literature in the last 40 years, the crucial issue of evaluating the practical quality of the corner-relaxation bound was not addressed so far. In the present paper we report, for the first time, the optimal value of the corner relaxation (in two possible variants) for a very large set of MILP instances from the literature, thus providing a missing yet very important piece of information about the practical relevance of this relaxation. The outcome of our experiments is that the corner relaxation often gives a tight approximation of the integer hull, the main so for MILPs with general-integer variables-the approximation tends to be less satisfactory when a consistent number of binary variables exists.
Year
DOI
Venue
2008
10.1016/j.disopt.2006.11.010
Discrete Optimization
Keywords
Field
DocType
optimal value,computational analysis.,gomory’s corner polyhedron,tight approximation,practical quality,computational analysis,gomory's corner polyhedron,mixed-integer linear programming,corner relaxation,milp instance,mixed-integer linear program,general-integer variables-the approximation,practical relevance,mixed integer linear program,optimal basis,linear programming relaxation
Integer,Mathematical optimization,Linear programming,Linear programming relaxation,Hull,Mathematics,Computational analysis,Binary number
Journal
Volume
Issue
ISSN
5
2
Discrete Optimization
Citations 
PageRank 
References 
8
0.57
11
Authors
2
Name
Order
Citations
PageRank
Matteo Fischetti12505260.53
Michele Monaci2104960.78