Scholarlink

<p>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 <i>m</i> iterations, where <i>m</i> 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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

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

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年3月26日

查看全文
  • Mohit Tawarmalani

摘要

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.