Improving Discrete Model Representations via Symmetry Considerations
指出离散优化建模中常忽略的对称性问题，通过电信网络设计、噪声污染和机器采购三个实例，展示在模型中施加决策层次可显著提升分支定界求解器的效率。
In this paper, we focus on a useful modeling concept that is frequently ignored while formu lating discrete optimization problems. Very often, there exists a natural symmetry inherent in the problem itself that, if propagated to the model, can hopelessly mire a branch-and-bound solver by burdening it to explore and eliminate such alternative symmetric solutions. We discuss three applications where such a symmetry arises: a telecommunications network design problem, a noise pollution problem, and a machine procurement and operation problem. For each case, we identify the indistinguishable objects in the model that create the problem symmetry and show how imposing certain decision hierarchies within the model significantly enhances its solvability, while using a popular modern-day commercial branch-and-cut software (CPLEX 6.5).