Persistency in Multilinear Optimization

• 成果类型: Article; Early Access
• 署名作者: Lassiter, Julie Bowers; Hadavas, Paul T.; Adams, Warren P.
• 署名单位: Clemson University; University System of Georgia; Georgia Southern University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2022.0171
• 发表日期: 2025
• 关键词: roof duality; relaxations; hierarchy; variables; bounds

摘要

We define a multilinear program to be persistent if every variable realizing a value at either its lower or upper bound in an optimum to a specified linear relaxation persists in retaining that same value in an optimum to the original problem. Few persistency results are known, and all deal with binary or mixed 0-1 problems, reformulating nonlinear instances as equivalent mixed 0-1 linear programs and showing the preference of a binary variable over its complement. We extend the knowledge of persistency in two respects: we present the most general known family of constraints that allows persistency for 0-1 polynomial programs, and we provide sufficient conditions for recognizing more general multilinear problems as persistent. Our approach differs from previous work in that (i) as opposed to the binary case, we show the preference of a variable value over all permissible realizations, here sometimes infinitely many of them, and (ii) our linearizations are not required to be equivalent.