Premium
Spherical cuts for integer programming problems
Author(s) -
Liberti Leo
Publication year - 2008
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.2008.00604.x
Subject(s) - intersection (aeronautics) , cutting plane method , integer programming , mathematics , integer (computer science) , mathematical optimization , point (geometry) , linear programming , plane (geometry) , type (biology) , computer science , geometry , ecology , engineering , biology , programming language , aerospace engineering
We introduce a new family of valid inequalities for general linear integer programming problems, based on the distance of the relaxed solution to the closest integral point. We show that these are valid cuts, establish some relations with Balas' intersection cuts, and show that a straightforward cutting plane algorithm derived from either spherical or intersection cuts will in general only converge if a suitable Gomory‐type strengthening is put in place.