Intersection cuts for convex mixed integer programs from translated cones |
| |
Affiliation: | Industrial Engineering and Operations Research, Indian Institute of Technology Bombay, Powai, Mumbai 400076, India |
| |
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. |
| |
Keywords: | Intersection cut Translated cone |
本文献已被 ScienceDirect 等数据库收录! |
|