Article ID Journal Published Year Pages File Type
5128271 Discrete Optimization 2017 26 Pages PDF
Abstract

We develop a general framework for linear intersection cuts for convex integer programs with full-dimensional feasible regions by studying integer points of their translated tangent cones, generalizing the idea of Balas (1971). For proper (i.e, full-dimensional, closed, convex, pointed) translated cones with fractional vertices, we show that under certain mild conditions all intersection cuts are indeed valid for the integer hull, and a large class of valid inequalities for the integer hull are intersection cuts, computable via polyhedral approximations. We also give necessary conditions for a class of valid inequalities to be tangent halfspaces of the integer hull of proper translated cones. We also show that valid inequalities for non-pointed regular translated cones can be derived as intersection cuts for associated proper translated cones under some mild assumptions.

Related Topics
Physical Sciences and Engineering Mathematics Control and Optimization
Authors
, ,