HQC-Bend

01 · 研究动机

（混合）整数线性规划无处不在，而且很难求解

03 · 工作原理

一个类，三个阶段，一个循环

HQC-Bend 把目标模型分解为二进制主问题（MAP）和连续子问题（SUB），并在两者之间迭代。

主要特点

• 混合量子-经典计算。QPU 求解二进制主问题，CPU 求解连续子问题。
• 模块化结构。预处理、主问题求解器和加割方案相互独立，便于扩展。
• 原生支持 Gurobi 和 Python。输入就是普通的 gurobipy 模型，可作为脚本运行，也可在 Jupyter Notebook 中运行。
• 子问题并行。多个二进制候选解在 CPU 集群上同时评估。
• 更强的割。Benders 对偶分解在二进制循环开始前，先在主问题的 LP 松弛上提升割。
• 多种量子后端。支持 D-Wave BQM 和 CQM 求解器，以及 OpenJij 和模拟分岔采样器。

05 · 加割方案

三种加割方式：Normal、L‑shaped 与 Benders 对偶分解

对于 MAP 给出的二进制候选解 \mathbf{x}^{*}，子问题会产生对偶解 \mathbf{w}^{*}，并据此生成以下两种割之一：

多割

量子采样器返回的不只是一个解，而是一整个低能量二进制状态的分布。设置 Mcut_flag: true 后，HQC-Bend 取最好的 Cutnums 个候选解，在 CPU 上并行求解它们的子问题，并在一次迭代中为每个候选解各添加一个割。每轮添加的割越多，λ 的上下界收紧得越快。

每个割都是一个从下方约束 λ 的平面。迭代持续进行，直到 λ 的上下界之差小于 threshold.gap。

07 · 快速上手

从 Gurobi 模型到混合求解

1. 1

   安装

   需要 Python 3.8+ 以及带有效许可证的 Gurobi 9.1.2+。HQCMCBD.py 在加载时会导入所有后端，因此即使只用一种模式，也需要全部安装。

   复制

   git clone https://github.com/djzts/HQCMCBD-API.git
   cd HQCMCBD-API
   pip install gurobipy numpy dimod dwave-system openjij torch simulated-bifurcation

   使用 D-Wave 模式（cqm、bqm_hybrid、bqm_quantum）时，请在环境变量中设置 DWAVE_API_TOKEN，不要把令牌提交到配置文件中。

   GPU 加速的模拟分岔（"bifurcation"）

   bifurcation 后端调用 simulated_bifurcation.minimize(..., device="cuda")，因此需要一块驱动支持 CUDA 11.8 的 NVIDIA 显卡。GPU_acced_Q 安装指南一步步介绍了环境搭建：Python 3.10（推荐用 conda 新建环境）、CUDA 11.8 版 PyTorch 2.6.0 以及 simulated-bifurcation 1.2.0。简要步骤如下，请在上面的安装命令之后运行，以免 GPU 版 PyTorch 被替换：

   复制

   pip install torch==2.6.0 torchvision==0.21.0 torchaudio==2.6.0 --index-url https://download.pytorch.org/whl/cu118
   pip install simulated-bifurcation==1.2.0
   python -c "import torch, simulated_bifurcation as sb; print(torch.__version__, torch.cuda.is_available())"

   最后一条命令应输出 2.6.0+cu118 True。PyTorch 的 cu118 安装包已自带 CUDA 运行库，无需另装 CUDA Toolkit。如果输出 False，请参考指南中的常见问题。

2. 2

   导入

   Python 脚本

   from HQCMCBD import HQCMCBD_algorithm

   Jupyter Notebook

   import warnings
   warnings.filterwarnings("ignore")
   %run HQCMCBD_notebook.ipynb

3. 3

   构建模型

   任何包含二进制变量和非负连续变量的 gurobipy 模型都可以。下面是包中的示例问题（Example.ipynb）。

   复制

   import gurobipy as gp
   from gurobipy import GRB
   import numpy as np
   
   A = np.array([[0, 0], [0, 0], [0, 0], [0, 0],
                 [-1, -1], [-1, 0], [-1, 0], [0, -1], [0, -1]])
   G = np.array([[1, 0, 1, 0], [1, 0, 0, 1], [0, 1, 1, 0], [0, 1, 0, 1],
                 [0, 0, 0, 0], [1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]])
   b = np.array([1, 1, 1, 1, -1, 0, 0, 0, 0])
   c = np.hstack(np.array([-15.0, -10.0]))
   h = np.hstack(np.array([8, 9, 5, 6]))
   
   # 创建 Gurobi 模型
   model = gp.Model("MILP")
   
   # 添加变量
   x = model.addMVar(shape=len(c), vtype=GRB.BINARY, name="x")
   y = model.addMVar(shape=len(h), vtype=GRB.CONTINUOUS, lb=0, name="y")
   z = model.addVar(vtype=GRB.CONTINUOUS, lb=0, name="z")
   p = model.addVar(vtype=GRB.BINARY, name="p")
   
   # 目标函数与约束
   model.setObjective(c @ x + h @ y, GRB.MAXIMIZE)
   model.addConstr(A @ x + G @ y <= b, name="constraints")
   model.addConstr(z == 1, name="constraints_eq")
   model.addConstr(p == 1, name="constraints_eq2")
   
   model.optimize()

   最大化模型会在内部转换为最小化问题，结果仍按原始符号约定输出。

4. 4

   运行（只需两行）

   自定义方法 · config.json

   solver = HQCMCBD_algorithm(model, mode="manual")
   solver.run()

   默认设置 · config_default.json

   solver = HQCMCBD_algorithm(model, mode="default")
   solver.run()

5. 5

   查看收敛过程

   每一轮都会输出目标值、λ 的上下界以及相对和绝对间隙。间隙达到阈值时停止运行。

   输出 · Example-3bin-output.ipynb，manual 模式（节选）

   Benders decomposition Round - 2
   The 2-th Config file of quantum sampling is created successfully at .\data_output\Gurobi_info-round-2.json.
   create optimality cut
   Round 2:
       Current Objective value is 12.0;
       lambda_upper is 20.0;
       lambda_lower is 11.0;
       Relative gap is 81.818%.
       Absolute gap is 9.0
   Benders decomposition Round - 3
   create optimality cut
   Round 3:
       Current Objective value is 6.0;
       lambda_upper is 19.0;
       lambda_lower is 17.0;
       Relative gap is 11.765%.
       Absolute gap is 2.0
   Benders decomposition Round - 4
   create optimality cut
   Round 4:
       Current Objective value is 5.0;
       lambda_upper is 17.0;
       lambda_lower is 17.0;
       Relative gap is 0.0%.
       Absolute gap is 0.0
   optimal found, it takes 4  Rounds.

   data_output/每一轮的目标值、λ 上下界、求解器元数据和 MAP 解。

   LP_output/开启 debug_mode 时导出的 MAP 和子问题的 Gurobi LP 文件。

   LP_output_dwave/量子和量子启发式求解器的输出文件。

09 · 应用

数据中心能源管理

配套仓库 djzts/HQCMBD 中有一个为 HQC-Bend 构建的数据中心模型。它与 HQC-Bend 天然契合：启停决策是二进制变量，交给量子主问题；功率和温度是连续变量，交给 CPU 子问题。

• 9个服务器区域（3 × 3 网格）
• 150 kWh电池，充/放电功率上限 60 / 90 kW
• 15–24 °C区域允许温度
• 2.5 kW/m²IT 与服务器负载密度

11 · 引用

引用 HQC-Bend

如果你在工作中使用了 HQC-Bend，请引用 QCNC 2025 论文：

@inproceedings{zhao2025hqc,
  title={HQC-Bend: A Python Package of Hybrid Quantum-Classical Multi-cuts Benders' Decomposition Algorithm},
  author={Zhao, Zhongqi and Li, Mingze and Fan, Lei and Han, Zhu},
  booktitle={2025 International Conference on Quantum Communications, Networking, and Computing (QCNC)},
  pages={591--597},
  year={2025},
  organization={IEEE},
  url={https://github.com/djzts/HQCMCBD-API}
}