用代数方法自动生成多项式对称破缺约束，显著提升整数规划求解效率。
Automatic Generation of Polynomial Symmetry Breaking Constraints
- 基于基多项式与置换群生成随机二次不等式作为对称破缺约束。
- 在0-1装箱问题上，简单约束可使求解时间持续降低。
- 适合需处理对称性的整数规划研究者与工程优化应用者。
整数规划中的对称性会导致搜索冗余，通常通过对称破缺约束来消除等价解。本文提出一种代数方法，可基于任意基多项式与特定置换群自动生成一组随机多项式不等式作为对称破缺约束。该方法可在主流符号计算软件中轻松实现。为验证效果，我们在近满容量0-1装箱实例上开展案例研究，静态生成随机二次破缺约束并加入基准整数规划模型，使用Gurobi求解。结果表明，简单的对称破缺约束（尤其是涉及少量变量与置换）能最一致地减少求解时间。
原文摘要 · Abstract (English)
Symmetry in integer programming causes redundant search and is often handled with symmetry breaking constraints that remove as many equivalent solutions as possible. We propose an algebraic method which allows to generate a random family of polynomial inequalities which can be used as symmetry breakers. The method requires as input an arbitrary base polynomial and a group of permutations which is specific to the integer program. The computations can be easily carried out in any major symbolic computation software. In order to test our approach, we describe a case study on near half-capacity 0-1 bin packing instances which exhibit substantial symmetries. We statically generate random quadratic breakers and add them to a baseline integer programming problem which we then solve with Gurobi. It turns out that simple symmetry breakers, especially combining few variables and permutations, most consistently reduce work time.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。