组合优化与凸优化实验：从建模到可复现的求解全流程

简介：哈工大组合优化与凸优化研究生课程实验资料包，面向计算机、数学等方向的研究生与进阶学习者，旨在通过动手实验理解优化理论中的核心算法，并顺利完成课程任务。包内共262个文件，整体约47.1MB，以Python脚本（.py/.pyc）和大量实验截图（.bmp/.png）为主，同时包含XML/IML工程配置、all-data数据及MAT文件，方便复现运行环境与核对中间结果。已有294人浏览学习。内容覆盖组合优化经典策略（动态规划、贪心、回溯）与凸优化主流算法（梯度下降、牛顿、拟牛顿），并拆分为Lab1无约束优化、Lab2有约束优化两大实验模块，涉及线性规划、惩罚函数、内点法等求解思路。配套实验报告与说明书细致记录问题背景、方法步骤、结果分析和预期输出，读者可对照源码理解参数调整逻辑，借助截图检查可视化效果，节省环境搭建与排错时间，适合作为研读优化理论、准备同类研究生课程实验的参考。

1. 组合优化与凸优化实验包：先跑通再讲理论

拿到一个“组合优化与凸优化研究生课程实验”的zip包，里面通常是一组实验报告、说明书和代码骨架。这类课程实验真正考验的不是背公式，而是能否把问题描述快速变成可执行的求解流程：组合优化要求你在离散解空间里搜出最优或近似最优，凸优化则要求你把连续问题写成标准形式并让求解器稳定收敛。对刚入门的研究生和转算法的工程师来说，最大的障碍往往不是数学，而是环境适配、数据对比和报告呈现——测试集一换，结果就完全不可复现。下面按我自己拿到这类工程包时的做法，从解压、建模、调参到写报告，给出一条能直接照做的路线。

2. 组合优化实验的建模与求解——用Python把模型变成代码

组合优化的实验通常会围绕0-1背包、旅行商、最小生成树或最大流这类经典问题展开。实验报告里真正要解释的是：为什么选这个算法，它在不同规模上的行为如何。所以动手写代码之前，先要判断这个实验要求的是精确解还是近似解。

2.1 先分出种类：精确算法、近似算法、元启发式

我一般先把问题按理论框架分类。如果问题是P类且规模小，直接用动态规划或专用网络流算法；如果是NP-hard但实例规模可控，用分支定界或整数规划求解器；规模大到无法保证最优时，才引入近似比或元启发式。组合优化实验的评分点不只是“跑出了结果”，还要看你有没有给出复杂度分析和不同规模下的行为。因此报告里至少要有三组实验：小规模验证正确性，中规模看趋势，大规模看稳定性。

2.2 最小可复现实验：用OR-Tools解0-1背包

0-1背包是组合优化最经典的入门问题。我常用Google OR-Tools的CP-SAT求解器，建模直观，能精确求解中小规模实例，也方便后续和贪心、动态规划等算法做gap对比。下面是最小完整示例：

from ortools.sat.python import cp_model # 物品重量和价值 weights = [3, 2, 5, 4, 1] values = [10, 5, 12, 8, 3] capacity = 8 n = len(weights) model = cp_model.CpModel() x = [model.NewBoolVar(f"item_{i}") for i in range(n)] model.Add(sum(weights[i] * x[i] for i in range(n)) <= capacity) model.Maximize(sum(values[i] * x[i] for i in range(n))) solver = cp_model.CpSolver() status = solver.Solve(model) if status in (cp_model.OPTIMAL, cp_model.FEASIBLE): total_v = solver.ObjectiveValue() picked = [i for i in range(n) if solver.Value(x[i]) > 0] print("目标值:", total_v) print("选择的物品:", picked) else: print("无解")

这段代码里，NewBoolVar为每个物品生成0-1决策变量，容量约束通过model.Add写入，优化目标用Maximize声明，问题以整数线性规划的形式交给CP-SAT。参数上要注意capacity必须是整数，物品数量变大时求解时间可能指数增长；实验时建议给solver.parameters.max_time_in_seconds设定时限，避免单个实例卡死整个批量实验。

2.3 实验报告里最有说服力的对比表

无论是背包还是TSP，最终都要靠数据说话。我习惯在实验报告里固定一张表格：同一份测试数据下，列出算法名称、解质量、运行时间和与最优解的gap。

这个表的核心价值在于gap列，它保证了算法之间可比。只要规模在几万以内，精确解都能求出来；规模上涨后，动态规划的空间复杂度会先失控，这时再去看CP-SAT或元启发式，结论就很明显。表下方一定要写清楚数据集的生成规则，比如“重量均匀分布在U(1,100)，容量为总重量的60%”，否则数值没有任何意义。

3. 凸优化实验的落地——从目标函数到求解器

凸优化实验不像组合优化那样强调离散状态，它更考验建模与调参能力。课程里经常把组合优化和凸优化并列，本质上一个是离散搜索，一个是连续优化，但都遵循“建模—求解—验证”这条链路。

3.1 凸优化的标准形式与实验命题套路

凸优化实验里最常出现的是最小二乘、岭回归、LASSO、逻辑回归和SVM对偶。它们都可以写成或近似写成：

minimize f0(x) subject to fi(x) <= 0 (i=1,...,m) Ax = b

判断目标函数是否凸，只需看Hessian是否半正定。实验里给的损失函数大多是凸的，比如最小二乘的平方损失。你要做的是把数据、初值、终止条件设计好。最常见的翻车点是把非凸损失硬套凸优化框架，结果收敛到局部极小值，报告却还在按凸问题写结论。

3.2 用梯度下降实现线性最小二乘并调参

为了理解求解器内部发生了什么，我会先用纯NumPy实现一版梯度下降，作为全过程的“对照组”。

import numpy as np # 生成线性回归实验数据 np.random.seed(42) m, n = 1000, 5 X = np.random.randn(m, n) true_w = np.array([1.0, -2.0, 0.5, 3.0, -1.0]) y = X @ true_w + 0.1 * np.random.randn(m) # 梯度下降求解 min ||Xw - y||^2 def gradient_descent(X, y, lr=0.01, epochs=500, tol=1e-6): w = np.zeros(X.shape[1]) for i in range(epochs): grad = 2 * X.T @ (X @ w - y) / len(y) w -= lr * grad if np.linalg.norm(grad) < tol: break return w w_fit = gradient_descent(X, y) print("拟合权重:", w_fit) print("真实权重:", true_w)

这里的核心参数是学习率lr、迭代轮数epochs和停止阈值tol。学习率太大会发散，太小收敛很慢。工程上我会先取lr=0.1，观察前100轮目标函数下降曲线，再按十倍步长上下调整。

3.3 凸优化的三个数值坑：学习率、条件数、停止条件

第一个坑是学习率，不需要从极小值试起。第二个坑是特征尺度差异：如果X的条件数很大，梯度下降会很慢，实验前应当对特征做标准化。第三个坑是停止条件：不要只用目标函数差值，因为接近最优时目标差值会小于浮点误差。我更习惯同时看梯度范数。下面是个检查学习过程的片段：

loss_history = [] for i in range(epochs): grad = 2 * X.T @ (X @ w - y) / len(y) w -= lr * grad if i % 50 == 0: obj = np.mean((X @ w - y) ** 2) loss_history.append(obj) print(f"epoch {i:4d}, obj = {obj:.8f}")

看到目标值持续下降进入平台，基本可以判断收敛；如果出现无规律跳动，先检查学习率，而不是目标函数。

3.4 用cvxpy快速验证实验结果

实验报告里应当有一个权威对照。我通常用cvxpy在同一组数据上求一次参考解，用来和自写梯度下降结果对比。最小二乘的cvxpy写法如下：

import cvxpy as cp w_var = cp.Variable(X.shape[1]) objective = cp.Minimize(cp.sum_squares(X @ w_var - y)) prob = cp.Problem(objective) prob.solve(solver=cp.OSQP) print("cvxpy解:", w_var.value)

OSQP适合中等规模稀疏问题，速度比SDP快；如果你想验证SVM对偶，可以用cp.quad_form或cp.kl_div。最终报告里可以放一张自写梯度下降与cvxpy结果差异的对比表：

这张表能直接显示自写算法的数值精度和收敛代价。

4. 从zip到能跑的实验环境——解压、完整性与一键配置

实验包以zip格式分发，第一步往往不是打开报告，而是确认文件完整性。很多人卡在“could not find eocd”或“bad CRC”这类压缩包错误，问题往往不在算法，而在下载或解压环节。为了尽早排错，我会先把环境整治干净，再跑代码。

4.1 解压之前先验证zip完整性

处理zip压缩包，我固定用7-Zip的“测试压缩包”功能检查CRC错误，或者用命令行校验。Windows下7-Zip最顺手，Linux下直接跑：

zip -T student_experiments.zip

zip -T会把压缩包内每个文件解压到内存做CRC校验，输出“OK”说明没有损坏。如果出现“bad CRC”或找不到EOCD结束标记，说明文件截断或头部损坏。这时不要立刻重下，先检查网络工具是否把文件名改成非ASCII；大多数情况下需要重新下载。如果只是本机拷贝造成的小损坏，可以用zip -F尝试修复，但源压缩包本身损坏时修复不回来。整个过程中不需要额外工具。

提示：unzip -t file.zip在Windows和Linux下都可以用，输出比7-Zip更详细，但速度稍慢。

另一个经常出现的情况是IDE或资源管理器解压时提示“导入资源包失败”，实际原因是文件路径过长或包含中文字符。遇到这种问题，我习惯用7-Zip的命令行模式解压到纯英文目录，例如7z x student_experiments.zip -o./experiments，这样可以绕开Windows自带解压的路径解析限制。解压后第一时间检查目录结构，确认实验说明书和代码目录在同一层级，避免相对路径失效。

4.2 一次性搭好组合优化与凸优化的运行环境

实验代码通常依赖numpy、scipy、ortools、cvxpy。我会把环境依赖写进requirements.txt，而不是手动一条条装。

python >= 3.10 numpy >= 1.26 scipy >= 1.11 cvxpy >= 1.4 ortools >= 9.8 matplotlib >= 3.8

用conda创建干净环境并安装：

conda create -n opt_course python=3.10 -y conda activate opt_course pip install -r requirements.txt

选择Python 3.10是为了兼容OR-Tools和cvxpy的二进制轮子。安装完成后跑一个冒烟测试：

python -c "import cvxpy, ortools, numpy; print(cvxpy.__version__)"

如果这一行能通过，环境基本可用。若导入时报错，多数是依赖冲突，优先用pip check定位。

4.3 用Makefile和固定随机种子保证复现

实验报告里最容易缺失的是如何让别人复现。我会把解压、装依赖、跑实验三个入口统一到一个Makefile：

venv: python -m venv .venv install: venv .venv/bin/pip install -r requirements.txt run: install .venv/bin/python experiments/run_all.py

之后只需要make run就能一键跑完。代码里涉及随机性的部分都固定numpy.random.seed(42)，输出文件命名带上数据集规模和运行时间。评审者不需要看说明书，也能从头复现结果。

5. 组合优化与凸优化实验结果怎么对比才不踩坑

这一章处理“出数据不等于结论正确”的问题。实验报告里真正拉分的部分是对照实验的设计。无论是组合优化里的贪心与精确解对比，还是凸优化里的自写梯度下降与cvxpy解析解对比，都要在同一数据、同一指标上衡量。

5.1 收敛曲线怎么画才不误导

画收敛曲线最容易犯的错误是纵轴用线性尺度。凸优化接近最优解时下降幅度往往是指数级的，线性尺度会让曲线“看起来已经平了”，实际还没收敛。我会让横轴是epoch，纵轴是对数目标值：

import matplotlib.pyplot as plt plt.figure(figsize=(6, 4)) plt.plot(range(len(loss_history)), loss_history) plt.yscale('log') plt.xlabel('epoch') plt.ylabel('objective (log)') plt.grid(True, which='both', alpha=0.3) plt.savefig('convergence.pdf', bbox_inches='tight')

这样能清晰展示拐点。更进一步，把不同学习率下的收敛曲线画在同一张图里，就是一组很有说服力的消融实验。

5.2 对比表必须带数据集和参数列

很多人写对比表只放算法名和时间，却漏掉数据集规模、迭代次数、超参数。我会在表格下方加一段说明，列出测试实例生成方式：n的范围、稠密度、噪声方差。以组合优化为例，用“物品重量均匀分布”还是“重量偏斜分布”生成的数据，贪心算法的gap会差别很大。所以对比表要在显著位置标数据集ID，并把生成器代码放进附录，才能保证可复现。

5.3 稳定性验证：换随机种子，不只看单次运行

实验报告里不能只跑一次。常规做法是至少跑10组随机种子或10个不同规模实例，报告均值和方差。组合优化里报告最优gap的均值，凸优化里报告目标值的标准差。原因是启发式算法和梯度下降都对初值和数据敏感，单次成功说明不了鲁棒性。

稳定性结果最好用箱线图展示。对同一算法跑10个随机种子，把每个种子的最终目标值或gap收集成列表，用plt.boxplot画出来。如果箱体很宽，说明算法对初值敏感，报告讨论部分就要说明原因的来源。

6. 用热启动和敏感性分析把实验报告再做深一层

这一章讲一个我在处理这类课程实验时常用的进阶技巧：当求解器已经能跑出结果后，不要停在“跑通”，而是做热启动和敏感性分析。这个技巧只花很少的代码，但能把组合优化和凸优化两个主题串联起来。

6.1 CP-SAT里的热启动

在OR-Tools的CP-SAT中，可以用model.AddHint把上一轮可行解作为初值置入新实例。多组对比实验时，下一组实例往往和上一组相似，热启动能显著减少搜索时间。示例：

if last_solution is not None: for i in range(n): if last_solution[i] is not None: model.AddHint(x[i], last_solution[i])

这里last_solution是上一实例的选择结果，AddHint不是硬约束，但求解器会优先朝这个方向搜索，收敛明显加快。

6.2 凸优化里的敏感性分析

凸优化部分，我会对目标函数中的某个约束项系数做扰动，比如把损失函数里的正则系数乘上1+ε，观察最优解变化。具体做法是先用cvxpy参数化模型：

eps = cp.Parameter(nonneg=True) eps.value = 0.0 coefficient = 1.0 + eps

然后循环求解并记录目标值。用这段代码把扰动幅度和最优目标值画成曲线。如果曲线平缓，说明模型对数据误差不敏感；如果曲线在某一点出现突变，这个点就是模型的瓶颈约束。

需要注意的是，敏感性分析不能只改变一个参数后看完数值就结束，还要记录求解状态。如果prob.status是infeasible或infeasible_or_unbounded，说明扰动越过了可行域边界，此时不能把目标值拿来比较，而要在报告中注明约束集被破坏。这个记录本身也是实验结论。敏感性曲线会直接暴露哪些约束是模型真正的短板。

本文还有配套的精品资源，点击获取