On integer programs with irrational data

• 成果类型: Article; Early Access
• 署名作者: Hosseinian, Seyedmohammadhossein; Schaefer, Andrew J.
• 署名单位: North Carolina State University; Rice University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-026-02421-6
• 发表日期: 2026-09-10
• 关键词: integer programming; Irrational parameters; Number theory; Polynomial system; PHILOSOPHY OF MODELING; optimization

摘要

An integer program (IP) with a finite number of feasible solutions may have an unbounded continuous relaxation if it contains irrational parameters, due to implicit constraints induced by those irrational numbers. For IPs with polynomial constraints, we show that these implicit constraints can be derived explicitly when the irrational parameters belong to an extension field of the rational numbers by roots of integers, leading to a rational reformulation. We also present a weaker result for IPs involving the broader class of algebraic irrational numbers, which extends to IPs containing a particular form of transcendental numbers.