FENCHEL CUTTING PLANES FOR INTEGER PROGRAMS

• 成果类型: Article
• 署名作者: BOYD, EA
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.42.1.53
• 发表日期: 1994
• 页码: 53-64
• 关键词: programming; integer; algorithms; RELAXATION SUBGRADIENT; FENCHEL CUTTING PLANES

摘要

A technique for generating cutting planes for integer programs is introduced that is based on the ability to optimize a linear function on a polyhedron rather than explicit knowledge of the underlying polyhedral structure of the integer program. The theoretical properties of the cuts and their relationship to Lagrangian relaxation are discussed, the cut generation procedure is described, and computational results are presented.