ON THE CONVEX-HULL OF THE UNION OF CERTAIN POLYHEDRA

作     者：BALAS, E 

作者机构：Management Science Research Group Graduate School of Industrial Administration Carnegie Mellon University Pittsburgh PA 15213 USA 

出 版 物：《OPERATIONS RESEARCH LETTERS》 (运筹学快报)

年 卷 期：1988年第7卷第6期

页      面：279-283页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：Air Force Office of Scientific •R esearch National ~ence Foundation, (N00014-85-K-0198) Office of Naval Research, ONR Air Force Office of Scientific Research, AFOSR, (= 870292) 

主　　题：convex hull union of polyhedra disjunctive programming mixed integer representation 

摘      要：We consider a finite collection of polyhedra whose defining linear systems differ only in their right hand sides. Jeroslow [5] and Blair [4] specified conditions under which the convex hull of the union of these polyhedra is defined by a system whose left hand side is the common lefthand side of the individual systems, and whose right hand side is a convex combination of the individual right hand sides. We give a new sufficient condition for this property to hold, which is often easier to recognize. In particular, we show that the condition is satisfied for polyhedra whose defining systems involve the node-arc incidence matrices of directed graphs, with certain righ hand sides. We also derive as a special case the compact linear characterization of the two terminal Steiner tree polytope given in Ball, Liu and Pulleyblank [3].