Cone superadditivity of discrete convex functions

• 成果类型: Article
• 署名作者: Kobayashi, Yusuke; Murota, Kazuo; Weismantel, Robert
• 署名单位: University of Tokyo; Swiss Federal Institutes of Technology Domain; ETH Zurich
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-011-0447-1
• 发表日期: 2012
• 页码: 25-44
• 关键词: continuous-variables; integer programs; test sets

摘要

A function f is said to be cone superadditive if there exists a partition of R (n) into a family of polyhedral convex cones such that f(z + x) + f(z + y) a parts per thousand currency sign f(z) + f(z + x + y) holds whenever x and y belong to the same cone in the family. This concept is useful in nonlinear integer programming in that, if the objective function is cone superadditive, the global minimality can be characterized by local optimality criterion involving Hilbert bases. This paper shows cone superadditivity of L-convex and M-convex functions with respect to conic partitions that are independent of particular functions. L-convex and M-convex functions in discrete variables (integer vectors) as well as in continuous variables (real vectors) are considered.