提出基于展开的求解方法,显著提升整数规划中不确定性问题的求解效率。
An Expansion-Based Approach for Quantified Integer Programming
- 采用反例引导抽象精化(CEGAR)实现量化整数规划的展开求解
- 在特定实例上优于现有搜索型求解器,性能提升明显
- 适用于多阶段鲁棒优化问题,适合处理带线性约束的复杂决策
量化整数规划(QIP)通过将量化布尔公式(QBF)扩展至一般整数变量和线性约束,同时推广了整数规划的变量量化能力,成为处理复杂决策问题的通用框架。作为量化约束满足问题(QCSP)的特例,QIP还支持线性目标函数,有效建模多阶段鲁棒离散线性优化问题,是应对优化中不确定性的有力工具。尽管QBF已有搜索与展开两类求解范式,但此前仅探索过搜索型方法用于QIP和QCSP。本文提出基于展开的QIP求解方法,采用反例引导抽象精化(CEGAR),并将其拓展至含线性约束的多阶段鲁棒优化问题,嵌入优化框架以增强适用性。实验表明,该方法在特定实例上显著优于现有搜索型求解器;同时,利用线性约束建模能力,其性能也超越当前最先进的展开型QBF求解器。
原文摘要 · Abstract (English)
Quantified Integer Programming (QIP) bridges multiple domains by extending Quantified Boolean Formulas (QBF) to incorporate general integer variables and linear constraints while also generalizing Integer Programming through variable quantification. As a special case of Quantified Constraint Satisfaction Problems (QCSP), QIP provides a versatile framework for addressing complex decision-making scenarios. Additionally, the inclusion of a linear objective function enables QIP to effectively model multistage robust discrete linear optimization problems, making it a powerful tool for tackling uncertainty in optimization. While two primary solution paradigms exist for QBF -- search-based and expansion-based approaches -- only search-based methods have been explored for QIP and QCSP. We introduce an expansion-based approach for QIP using Counterexample-Guided Abstraction Refinement (CEGAR), adapting techniques from QBF. We extend this methodology to tackle multistage robust discrete optimization problems with linear constraints and further embed it in an optimization framework, enhancing its applicability. Our experimental results highlight the advantages of this approach, demonstrating superior performance over existing search-based solvers for QIP in specific instances. Furthermore, the ability to model problems using linear constraints enables notable performance gains over state-of-the-art expansion-based solvers for QBF.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。