论文标题
带有互补性约束的线性程序的放松和切割飞机
Relaxations and Cutting Planes for Linear Programs with Complementarity Constraints
论文作者
论文摘要
我们研究具有互补性约束的线性程序的放松，尤其是互补变量并非独立的实例。我们的表述基于识别实例冲突图的顶点覆盖物，并将Nguyen，Richard和Tawarmalani的扩展重新印刷线性化技术推广到变量之间具有一般互补条件的实例。我们演示了如何从稳定的套件和与完整的两部分图相关的稳定套件和布尔二极管多层室中获得强大的切割平面。通过针对三种实际问题的广泛计算研究，我们根据最佳差距封闭了提议的线性松弛和新的切皮平面的性能。
We study relaxations for linear programs with complementarity constraints, especially instances whose complementary pairs of variables are not independent. Our formulation is based on identifying vertex covers of the conflict graph of the instance and generalizes the extended reformulation-linearization technique of Nguyen, Richard, and Tawarmalani to instances with general complementarity conditions between variables. We demonstrate how to obtain strong cutting planes for our formulation from both the stable set polytope and the boolean quadric polytope associated with a complete bipartite graph. Through an extensive computational study for three types of practical problems, we assess the performance of our proposed linear relaxation and new cutting-planes in terms of the optimality gap closed.
