New finite relaxation hierarchies for concavo-convex, disjoint bilinear programs, and facial disjunctions

• 成果类型: Article
• 署名作者: Tawarmalani, Mohit
• 署名单位: Purdue University System; Purdue University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-026-02326-4
• 发表日期: 2026-07
• 页码: 5-55
• 关键词: Disjoint bilinear program; concave minimization; convexification; Double Description; Barycentric Coordinates; Reformulation Linearization Technique; Facial Disjunctions; adjustable robust optimization; algorithm; MODEL

摘要

This paper introduces novel relaxation hierarchies for concavo-convex programs (CXP), a class of problems that includes disjoint bilinear programming (DBP) and concave minimization (CM) as special cases. At the core of these hierarchies is an algorithm based on double-description (DD) that computes the barycentric coordinates of a polyhedral cone as rational, non-negative functions representing multipliers associated with the cone's rays. These hierarchies combine geometric structure derived from barycentric coordinates with algebraic techniques via rational functions, achieving the convex hull in m iterations, where m is the number of inequalities that a subset of the variables must satisfy. Our framework offers the first unified approach to analyze and tighten relaxations from disjunctive programming (DP) and reformulation-linearization technique (RLT) for CXP. We also demonstrate that our methods extend to facial disjunctive programs (FDP), where solutions are constrained to lie on faces of a Cartesian product of polytopes, generalizing known hierarchies for 0-1 programs.