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

简介：提供开箱即用的Python整数规划教学实验资源，含四个独立可运行模块：branch_and_bound.py实现带剪枝策略的分支定界法，支持搜索树构建与最优解动态追踪；cutting_plane.py基于单纯形法迭代添加割平面约束，逐步收紧可行域至整数解；hungarian_assignment.py专用于标准指派问题，保证多项式时间复杂度与精确解；monte_carlo.py采用随机采样结合可行性校验的启发式流程，适合大规模或结构不规则问题。所有脚本均附详细注释、明确输入输出格式，并通过experiment.py统一调度演示。配套HTML文档覆盖各算法核心逻辑、关键函数接口及典型调用示例，其中bnb_Tree.html可视化分支过程，cutting_plane.html动态展示约束切割迭代，其余页面分别对应各模块原理说明与代码片段。项目包含完整目录结构、LICENSE声明、README使用指南及基础环境配置提示，适配高校线性规划课程实验、课堂演示与学生自主编程训练。

1. 这不是“调个库就完事”的整数规划课——而是一套能让你亲手拆开算法骨架的教学实践包

我带线性规划实验课七年，每年都会遇到同一个问题：学生抄完 scipy.optimize.linprog 或 pulp 的例程，跑通一个例题，就以为自己懂了整数规划。直到期末项目里让他们手动实现分支定界法的节点剪枝逻辑，或者解释为什么割平面必须满足“不砍掉任何整数可行解”这个条件时，才真正暴露问题——他们没看见算法在“动”，只记住了函数名和参数顺序。

这套名为“Python整数规划四算法实践包”的资源，就是为解决这个教学断层而生的。它不提供黑盒求解器，而是把分支定界（Branch and Bound）、割平面法（Cutting Plane）、匈牙利算法（Hungarian Algorithm） 和蒙特卡洛随机采样（Monte Carlo Sampling） 四种核心思想，全部用纯 Python 从零实现，不依赖任何高级优化库（除 numpy 和基础 scipy.linalg 外），所有关键步骤——比如单纯形表的基变换、割平面的Gomory分数切割生成、指派问题的行/列约减与覆盖线构造、随机解的可行性快速校验——都写在明处、注释在旁、可视化在案。

它面向的不是竞赛选手或工业优化工程师，而是大三本科生、研究生初学者，以及需要给学生讲清楚“为什么分支定界比穷举快”“为什么割平面能收敛到整数解”的一线教师。你打开 branch_and_bound.py，看到的不是 solver.solve()，而是 self._create_child_nodes()、self._prune_by_bound()、self._update_best_solution() 这样的方法名；你运行 experiment.py，终端输出的不只是最终目标值，还有每轮迭代的节点数、当前上界/下界变化、被剪掉的子问题规模；你点开 bnb_Tree.html，一棵动态生长的搜索树实时渲染出来，红色节点标出被剪枝的无效分支，绿色叶子显示已确认的整数可行解——这才是“看见算法在呼吸”。

关键词里的“分支定界”“割平面法”“匈牙利算法”“蒙特卡洛法”“整数规划”，在这里不是PPT上的名词，而是你键盘敲出来的循环、条件判断和矩阵运算。它不承诺工业级性能，但保证每一行代码都在回答一个问题：“这一步，到底在数学上做了什么？”如果你正为课程实验发愁，或想真正搞懂整数规划的底层逻辑，而不是停留在 pip install pulp 的层面，那这个包就是为你写的。它不开箱即用，但开箱即“可理解”、可调试、可修改、可教学。

2. 算法选型背后的教学逻辑：为什么是这四种？为什么这样实现？

2.1 四种算法的定位分工与教学价值分层

整数规划算法浩如烟海，但教学必须做减法。我们严格筛选这四种，并非因为它们“最先进”，而是因为它们各自承担不可替代的教学角色，构成一条从确定性精确解→启发式近似解的认知进阶链：

• 分支定界法（Branch and Bound） 是整数规划的“通用引擎”。它不依赖问题结构，适用于任意混合整数线性规划（MILP）问题。教学价值在于：它把抽象的“枚举+剪枝”思想具象化为一棵可观察、可干预的搜索树。学生通过手动控制分支变量选择策略（如最大分数变量优先）、剪枝阈值（上界更新时机）、节点探索顺序（深度优先 vs 广度优先），能直观理解“计算复杂度”与“问题结构”的关系。我们实现中强制要求用户显式传入 branching_strategy 参数，就是为了杜绝“默认策略掩盖原理”的教学陷阱。

• 割平面法（Cutting Plane） 是“连续松弛→整数收紧”的典范。它揭示了一个深刻事实：许多整数约束其实可以由一组线性不等式（割平面）隐式表达。教学价值在于训练学生对“可行域几何”的直觉——为什么添加一个新约束会“切掉”一部分非整数解，却不碰触任何整数点？我们基于标准单纯形法实现，每次迭代后检查最优解各分量是否为整数；若否，则针对某个非整数基变量，用Gomory分数切割公式生成一个新约束，并重新求解松弛问题。整个过程完全透明，cutting_plane.py 中 generate_gomory_cut() 函数的每一步计算（取小数部分、构造系数向量、生成不等式）都附有数学推导注释。

• 匈牙利算法（Hungarian Algorithm） 是“结构特化→高效求解”的标杆。它专用于标准指派问题（n人n任务，一人一任务，最小化总成本），时间复杂度稳定在 O(n³)。教学价值在于展示“问题结构如何赋能算法设计”：利用成本矩阵的行/列加减不变性，通过系统性约减将零元素“逼”到对角线位置，再用最小覆盖线判定最优性。我们实现中完整复现了Kuhn原始论文的四步流程（Step 1: 行约减；Step 2: 列约减；Step 3: 用最少直线覆盖所有零；Step 4: 若直线数=n则得解，否则调整矩阵），并用 hungarian_assignment.py 中的 visualize_step() 函数生成中间矩阵快照，方便学生对照课本图示理解每一步的代数意义。

• 蒙特卡洛随机采样（Monte Carlo Sampling） 是“大规模现实问题”的务实入口。当问题规模达到数千变量，或约束结构松散（如含大量逻辑条件），前三种确定性算法可能陷入组合爆炸。此时，随机采样+可行性检验提供了一条“够用就好”的路径。教学价值在于破除“最优解万能论”，引入工程权衡思维：如何定义“足够好”的解？如何设计高效的可行性校验器（避免全约束遍历）？我们实现中采用分层采样策略——先对整数变量进行均匀随机采样，再用快速线性插值估算连续变量范围，最后仅对采样点做轻量级约束检查。monte_carlo.py 的 sample_feasible_point() 方法内嵌了多种采样分布选项（uniform, normal, log-uniform），让学生亲身体验不同分布对收敛速度的影响。

提示：这四种算法并非互斥，而是构成一个认知光谱。分支定界是“通用但慢”，割平面是“几何但依赖松弛”，匈牙利是“快但窄”，蒙特卡洛是“快但不保优”。教学中应引导学生对比：对同一指派问题，匈牙利给出精确解只需0.01秒，分支定界需0.5秒，蒙特卡洛采样1000次可能得到98%精度解耗时0.05秒——差异背后是数学本质与工程妥协的生动教材。

2.2 为什么拒绝黑盒求解器？——我们的“最小依赖”原则

市面上不乏封装精良的整数规划库（如 pulp, ortools, cvxpy），它们强大、稳定、文档齐全。但它们恰恰是教学的“敌人”：一行 prob.solve() 隐藏了成千上万行代码，学生无法追问“solve() 内部发生了什么？”。

因此，本实践包恪守“最小依赖”原则：
- 仅依赖 numpy（1.21+）与 scipy（1.7+）的基础模块：numpy 用于矩阵运算与数组管理；scipy.linalg 用于求解线性方程组（单纯形法中的基矩阵求逆）；scipy.optimize.linprog 仅作为连续松弛问题的求解器被调用一次（在分支定界和割平面中），且其调用被明确封装在 solve_relaxation() 函数内，学生可随时替换为自研单纯形法。
- 所有核心算法逻辑 100% 手写：分支定界的搜索树节点类（BNBNode）包含 variables, bounds, objective_value, is_integer 等属性，其 __init__ 方法清晰展示如何从父节点派生子节点；割平面法的 CuttingPlaneSolver 类中，add_cut() 方法接收一个 np.array 形式的切割约束，并手动更新约束矩阵 A_ub 和右端向量 b_ub；匈牙利算法的 HungarianSolver 类中，step_one() 至 step_four() 方法严格对应教科书四步，无任何跳步或合并。
- 所有输入输出格式统一、可读性强：无论哪个模块，输入均为标准 dict 结构，包含 c（目标系数向量）、A_ub（不等式约束矩阵）、b_ub（不等式右端向量）、A_eq（等式约束矩阵）、b_eq（等式右端向量）、bounds（变量上下界元组列表）、int_vars（整数变量索引列表）。输出均为 dict，含 solution（最优解向量）、objective_value（最优值）、status（求解状态）、iterations（迭代次数）、details（算法特有信息，如分支树深度、切割次数、指派矩阵）。这种一致性让学生无需为每个算法学习一套新接口。

注意：experiment.py 中的统一调度，并非为了隐藏差异，而是为了凸显共性。当你看到 result_bnb = BranchAndBoundSolver().solve(problem) 和 result_hung = HungarianSolver().solve(problem) 调用形式完全一致时，你立刻意识到：算法差异不在接口，而在内部实现。这种设计强迫学生关注“里面怎么动”，而非“外面怎么调”。

3. 核心模块深度解析：代码即教案，注释即讲义

3.1 分支定界法（BranchAndBound）：构建一棵会思考的搜索树

分支定界法的核心，在于将一个难解的整数问题，分解为一系列易解的连续松弛问题，并通过智能剪枝避免穷举。我们的 branch_and_bound.py 实现，将这一思想拆解为四个可触摸的组件：

第一，节点（BNBNode）是算法的细胞。 每个节点代表一个子问题，其状态由 variables（当前变量赋值）、bounds（该节点下变量的新上下界）、objective_value（松弛问题最优值）、is_integer（是否为整数解）和 parent（父节点引用）共同定义。关键在于 bounds 的更新逻辑：当对变量 x_i 进行分支时，左子节点设 x_i <= floor(x_i*)，右子节点设 x_i >= ceil(x_i*)，其中 x_i* 是父节点松弛解中 x_i 的值。BNBNode.__init__() 方法中，self.bounds = parent.bounds.copy() 后紧跟 self.bounds[i] = (parent.bounds[i][0], np.floor(parent.solution[i]))，这行代码就是分支操作的全部数学含义——它没有魔法，只有对实数区间的精确切割。

第二，搜索树（BNBTree）是算法的骨架。 它维护一个待处理节点的优先队列（heapq 实现），按 objective_value（最小化问题）排序，确保优先探索最有希望的分支。BNBTree.add_node() 方法不仅插入节点，还执行剪枝预判：若新节点的 objective_value 已大于当前已知最优整数解的目标值（上界），则直接丢弃，不入队。这就是“定界”的精髓——用连续解的下界，去剪掉整数解的上界无法超越的分支。experiment.py 中的演示会打印 Pruned node at depth X: bound=125.3 > current_best=124.8，让学生亲眼看到剪枝发生的瞬间。

第三，分支策略（branch_variable_selection）是算法的灵魂。 我们实现了三种经典策略供教学对比：
- most_fractional: 选择小数部分最接近 0.5 的变量（平衡分支）；
- largest_coefficient: 选择目标函数中系数绝对值最大的非整数变量（影响目标最显著）；
- smallest_index: 选择索引最小的非整数变量（最简单，用于基准测试）。
在 BranchAndBoundSolver._select_branch_variable() 中，策略选择直接影响搜索树的形状和大小。课堂实验中，让学生切换策略求解同一问题，观察 bnb_Tree.html 中树的宽度与深度变化，比任何理论讲解都更有力。

第四，可视化（bnb_Tree.html）是算法的呼吸。 此HTML文件由 bnb_Tree.py 生成，使用 d3.js 动态渲染。每个节点是一个圆圈，颜色编码其状态：灰色（待处理）、蓝色（正在处理）、绿色（整数可行解）、红色（被剪枝）。连线粗细表示该分支的“潜力”（基于目标值差距计算）。当鼠标悬停，显示该节点的 x 值、目标值、分支变量及约束。这不是炫技，而是把抽象的“搜索空间”变成学生可触摸的图形对象。我曾让学生在树上手动标记“如果这里换一种分支策略，下一个节点会是什么样？”，讨论热烈程度远超公式推导。

实操心得：分支定界最易犯的错是“忘记更新上界”。在 BranchAndBoundSolver._update_best_solution() 中，我们强制要求只有当新解 is_integer 且 objective_value < self.best_objective 时才更新 self.best_solution 和 self.best_objective。很多学生初版代码漏掉 is_integer 判断，导致用非整数解更新了上界，整个剪枝逻辑崩溃。这个坑，必须亲手踩过才记得住。

3.2 割平面法（CuttingPlane）：用刀锋切割可行域的几何艺术

割平面法的魅力，在于它用纯粹的线性代数语言，讲述了一个几何故事：如何用一把“刀”（一个线性不等式），精准地切掉包含非整数最优解的“肉”，却不伤及任何整数可行点的“骨头”？cutting_plane.py 将这个故事讲得清晰无比。

第一步，连续松弛是起点。 CuttingPlaneSolver.solve() 首先调用 scipy.optimize.linprog 求解原始问题的连续松弛，得到最优解 x* 和最优基 B。关键在于获取基变量索引 basic_indices 和非基变量索引 nonbasic_indices，这是后续切割的基石。linprog 的返回结果中 res.x 是解向量，但 res 对象本身不直接提供基信息，因此我们利用 res.conect（约束矩阵）和 res.b_ub，结合单纯形法原理，通过 get_basic_solution_from_basis() 函数反推基矩阵 B 及其逆 B_inv。这一步虽借用了 linprog，但基的识别逻辑完全手写，确保学生明白“什么是基变量”。

第二步，Gomory切割是核心。 当 x* 存在非整数分量时，我们选取一个基变量 x_i*（其值非整数），将其在最优单纯形表中的表达式 x_i = β_i + Σ_j α_ij * x_j（其中 x_j 为非基变量）提取出来。Gomory切割公式为：Σ_j f(α_ij) * x_j >= f(β_i)，其中 f(.) 表示取小数部分。cutting_plane.py 中的 generate_gomory_cut() 函数，正是逐行实现此公式：

# 假设 beta_i = 3.7, alpha_i1 = 0.4, alpha_i2 = 1.8, alpha_i3 = -0.3
# 则 f(beta_i) = 0.7, f(alpha_i1)=0.4, f(alpha_i2)=0.8, f(alpha_i3)=0.7 (负数的小数部分定义为 1 - |f|, 即 0.7)
cut_coeff = np.array([0.4, 0.8, 0.7])  # 切割系数向量
cut_rhs = 0.7                           # 切割右端项

这段代码旁边，注释详细解释了负系数小数部分的数学定义（f(-a) = 1 - f(a) for a>0），并给出数值示例。这不是编程技巧，而是线性规划中一个常被忽略的细节。

第三步，迭代收紧是过程。 新切割被添加为一个额外的不等式约束，形成新的松弛问题，再次求解。CuttingPlaneSolver._add_cut_to_problem() 方法手动将 cut_coeff 插入 A_ub 矩阵末行，将 cut_rhs 插入 b_ub 末位。整个循环 while not is_integer_solution(current_solution): 清晰展示了“逐步逼近”的动态过程。配套的 cutting_plane.html 页面，用动画形式展示每次迭代后可行域多边形的变化：初始松弛可行域（一个大凸多边形）被第一刀切掉一角，第二刀再切一刀……最终收缩为一个仅包含整数点的极小区域。学生能直观看到，算法是如何“雕刻”出整数解的。

注意：Gomory切割的有效性依赖于“不割掉整数点”。generate_gomory_cut() 函数末尾有一段验证代码：对当前问题的所有已知整数可行解（若提供），代入新切割检查是否满足。若不满足，则抛出 ValueError("Generated cut violates integer feasibility!")。这个验证不是必须的，但它是教学利器——它迫使学生思考“为什么这个公式能保证不割掉整数点？”，答案就在切割公式的构造原理中：对任意整数 x_j，Σ_j f(α_ij) * x_j 的整数部分恒为0，故其值必 >= f(β_i)。

3.3 匈牙利算法（HungarianAssignment）：在成本矩阵上跳的四步华尔兹

匈牙利算法是整数规划中少有的、能将组合优化问题转化为纯粹线性代数操作的奇迹。hungarian_assignment.py 的实现，就是一场在 n x n 成本矩阵上精确编排的四步华尔兹。

Step 1 & 2：行约减与列约减——寻找“零”的舞台。 HungarianSolver.step_one() 对每行减去该行最小值，step_two() 对每列减去该列最小值。这两步不改变最优指派，却将矩阵中“零”的数量最大化。关键细节在于：step_one() 返回的是一个 row_reduction 向量，记录每行减去了多少；step_two() 返回 col_reduction 向量。这些向量不仅是中间结果，更是最终重构原始最优值的钥匙——最终最优值 = sum(row_reduction) + sum(col_reduction) + sum(assigned_zeros_in_reduced_matrix)。我们在 solve() 方法末尾，用 original_cost = np.sum(row_red) + np.sum(col_red) + ... 显式计算并返回，让学生看清“约减”与“原问题”的数值纽带。

Step 3：最小覆盖线——探测“零”的布局。 这是最具技巧性的一步。HungarianSolver.step_three() 使用标准的“打标-覆盖-调整”流程：先标记所有未被划去的零所在行，再标记所有被标记行中零所在列，再标记所有被标记列中零所在行……直至无法标记。然后，用最少直线覆盖所有零：未被标记的行 + 被标记的列。cover_lines 函数返回 (covered_rows, covered_cols) 元组。此处的实现难点在于“标记传播”的循环终止条件，我们用 while changed: 循环配合 set 数据结构精确模拟，避免常见的无限循环错误。

Step 4：矩阵调整——为新零开辟空间。 HungarianSolver.step_four() 计算未被覆盖元素的最小值 theta，然后：未被覆盖行的每个元素减 theta，被覆盖列的每个元素加 theta。这一步的几何意义是：在保持已有零不变的前提下，在未被覆盖区域“制造”新的零。adjust_matrix() 方法中，theta = np.min(reduced_matrix[~covered_rows][:, ~covered_cols]) 这行代码，就是整个调整逻辑的浓缩。配套的 hungarian_assignment.html 页面，会逐帧播放这四步，每步高亮显示被操作的行、列、元素，并用箭头指示数值流向，如同一位耐心的教练在手把手指导。

实操心得：匈牙利算法极易因“零的分配冲突”而卡死。assign_zeros() 函数中，我们采用贪心策略：遍历每行，找到第一个未被占用的零，将其分配给该行，并标记该零所在列已被占用。但这可能导致后续行无零可分。真正的鲁棒实现需要回溯或最大匹配算法（如DFS）。我们的教学版故意保留此简化，并在 README.md 的“进阶挑战”中指出：“当前实现假设存在完美匹配。若遇分配失败，请尝试实现基于DFS的匈牙利算法变体。”——这既是留白，也是通往更深层知识的阶梯。

3.4 蒙特卡洛法（MonteCarlo）：在混沌中寻找秩序的工程智慧

当问题规模让分支定界望而却步，或约束结构让割平面难以生成有效切割时，蒙特卡洛法提供了一条务实的出路。monte_carlo.py 不追求理论最优，而专注于“如何在有限时间内，拿到一个足够好的可行解”。

采样策略是效率的关键。 MonteCarloSolver.sample_feasible_point() 支持三种分布：
- uniform: 在变量上下界内均匀采样。简单直接，但对高维稀疏可行域效率低下；
- normal: 以松弛问题最优解为中心，按变量范围设定标准差进行正态采样。利用了“最优解附近更可能有好解”的先验；
- log_uniform: 对取值范围跨越多个数量级的变量（如某些工程参数），在对数空间均匀采样，避免小值被淹没。
每种策略的 if strategy == 'normal': 分支内，都有 sigma = (bounds[i][1] - bounds[i][0]) / 6 这样的经验公式（按6σ原则覆盖99.7%范围），体现的是工程实践中的权衡，而非纯数学推导。

可行性校验是速度的生命线。 对每个采样点，全量检查所有约束 A_ub @ x <= b_ub + tol 和 A_eq @ x == b_eq ± tol 是昂贵的。我们实现两级校验：
1. 快速预筛：先检查变量边界 bounds[i][0] <= x[i] <= bounds[i][1]，这一步 O(n)，几乎零成本；
2. 约束分块：将 A_ub 按行分组（如每100行为一块），对每块计算 A_ub_block @ x，一旦某块的最大值 > b_ub_block.max() + tol，立即返回 False，避免计算剩余块。
check_feasibility() 方法中，for i in range(0, len(A_ub), block_size): 这个循环就是工程优化的典型体现——用少量内存访问换取大幅计算节省。

结果评估是决策的依据。 MonteCarloSolver.solve() 不仅返回最佳采样解，还返回 statistics 字典，包含 feasible_ratio（可行解占比）、best_objective_history（历史最优值变化曲线）、time_per_sample（单次采样平均耗时）。experiment.py 的演示会打印 Feasible ratio: 0.032 (32/1000) — good for sparse domains!，让学生理解：3.2% 的可行率，在某些大规模问题中已是极佳表现。配套的 monte_carlo.html 页面，用折线图展示 best_objective_history，直观呈现“随着采样次数增加，解的质量如何渐进提升”。

提示：蒙特卡洛法的教学重点不是“如何更快”，而是“如何判断够好”。我们在 solve() 方法中加入 target_improvement 参数：若连续 patience 次采样未能将目标值提升超过 target_improvement，则提前终止。这模拟了真实工程场景中的“性价比”决策——继续投入时间，收益已微乎其微。

4. 实操全流程：从环境配置到结果分析的完整闭环

4.1 开箱即用的环境配置与项目结构解读

本包设计为“零配置教学友好型”，但“零配置”不等于“无配置”，而是将配置过程本身变为教学环节。以下是推荐的、符合教学逻辑的部署流程：

第一步：创建隔离环境（教学第一课）。
强烈建议使用 venv 创建独立Python环境，而非全局安装。这本身就是软件工程规范的教学：

# 创建名为 "ip_lab" 的环境
python -m venv ip_lab
# 激活环境（Windows）
ip_lab\Scripts\activate.bat
# 激活环境（macOS/Linux）
source ip_lab/bin/activate
# 升级 pip（确保最新）
pip install --upgrade pip

提示：在课堂上，我会让学生执行 which python（macOS/Linux）或 where python（Windows），观察路径从系统Python变为 ip_lab/...，直观理解“虚拟环境”的物理含义——它就是一个独立的文件夹，里面装着专属的Python解释器和包。

第二步：安装最小依赖（理解依赖即理解算法边界）。
本包仅需两个核心依赖，安装命令简洁明了：

pip install numpy scipy

注意，我们不安装 pulp、ortools 或任何高级优化库。这是刻意为之的教学设计：让学生清晰看到，scipy.optimize.linprog 是我们唯一借用的“外部引擎”，其余一切皆为手写。在 README.md 的“依赖说明”章节，我们明确写道：“scipy.optimize.linprog 仅用于求解连续线性规划松弛问题。你可以将其替换为自研单纯形法，只需确保其接口返回 res.x 和 res.fun。”

第三步：理解项目结构（代码即文档）。
项目根目录下的文件，每一项都有其教学使命：
- *.py 文件（branch_and_bound.py, cutting_plane.py, hungarian_assignment.py, monte_carlo.py）：四大算法的“心脏”，是学生阅读、修改、调试的核心。
- experiment.py：教学“指挥中心”。它定义了多个标准测试问题（如 small_assignment, medium_milp, large_sparse），并依次调用四大求解器。学生可在此文件中，轻松添加自己的问题实例，或注释掉某些求解器，进行对比实验。
- *.html 文件：算法的“可视化教具”。bnb_Tree.html、cutting_plane.html 等并非静态页面，而是由对应Python脚本（如 bnb_Tree.py）在运行时动态生成。experiment.py 的最后一行 generate_visualizations(results) 就是触发它们的开关。
- LICENSE 和 README.md：开源协作与工程规范的启蒙。README.md 不仅包含安装指南，更有“教学实验建议”章节，列出如“对比不同分支策略对搜索树大小的影响”、“观察割平面迭代次数与问题规模的关系”等具体实验题目。

第四步：首次运行与结果解读（建立信心）。
激活环境后，进入项目目录，执行：

python experiment.py

终端将输出类似以下内容：

=== Running Branch and Bound on small_assignment ===
Initial relaxation objective: 124.8
Found integer solution at node 7 (depth 3): [1. 0. 1. 0.] -> obj=125.0
Pruned 12 nodes. Total nodes explored: 19.
Time: 0.042s. Status: Optimal.

=== Running Cutting Plane on small_assignment ===
Iteration 1: relaxation obj=124.8, x=[1.2, 0.0, 0.8, 0.0]
Added Gomory cut: 0.2*x0 + 0.8*x2 >= 0.8
Iteration 2: relaxation obj=125.0, x=[1.0, 0.0, 1.0, 0.0] -> Integer feasible!
Total cuts added: 2. Time: 0.028s.

=== Running Hungarian on assignment_problem ===
Optimal assignment found: [0, 1, 2, 3] (cost matrix diagonal)
Objective value: 45.0. Time: 0.001s.

=== Running Monte Carlo on large_sparse ===
Sampled 1000 points. Feasible ratio: 0.021.
Best objective found: 187.3 (vs LP relaxation: 185.1).
Time: 0.89s.

这份输出，就是算法的“体检报告”。它不只告诉你“解出来了”，更告诉你“怎么解出来的”、“付出了什么代价”、“质量如何”。例如，“Pruned 12 nodes” 直观展示了分支定界的价值；“Added Gomory cut” 展示了割平面的动态过程；“Feasible ratio: 0.021” 则坦诚了蒙特卡洛在稀疏问题中的现实。

4.2 统一调度框架（experiment.py）的深度剖析与定制

experiment.py 是整个实践包的“神经中枢”，其设计体现了教学调度的核心思想：统一接口，分离关注，鼓励对比。

核心数据结构：Problem 类。
所有算法共享同一问题定义，避免学生为不同算法学习不同格式。Problem 类的 __init__ 方法接受标准LP/MILP参数：

problem = Problem(
    c=np.array([3, 5, 2]),  # 目标系数
    A_ub=np.array([[1, 2, 1], [2, 1, 3]]),  # <= 约束矩阵
    b_ub=np.array([4, 7]),                   # <= 约束右端
    A_eq=None,                              # = 约束矩阵（可选）
    b_eq=None,                              # = 约束右端（可选）
    bounds=[(0, None), (0, None), (0, None)], # 变量界
    int_vars=[0, 1, 2]                      # 整数变量索引
)

这个结构，与 scipy.optimize.linprog 的输入高度兼容，降低了学习门槛，同时又通过 int_vars 明确标识了整数约束，为分支定界和割平面提供了必要信息。

调度逻辑：run_all_solvers() 函数。
此函数是 experiment.py 的主干，它按固定顺序调用四大求解器，并捕获异常：

solvers = [
    ("Branch and Bound", BranchAndBoundSolver()),
    ("Cutting Plane", CuttingPlaneSolver()),
    ("Hungarian", HungarianSolver()),
    ("Monte Carlo", MonteCarloSolver(max_samples=500))
]
for name, solver in solvers:
    try:
        print(f"\n=== Running {name} on {problem_name} ===")
        result = solver.solve(problem)
        results[name] = result
        print(f"Status: {result['status']}. Objective: {result['objective_value']:.3f}. Time: {result['time']:.3f}s.")
    except Exception as e:
        print(f"Failed: {str(e)}")
        results[name] = {"status": "Error", "error": str(e)}

这种结构的妙处在于：添加新算法，只需在 solvers 列表中追加一行；禁用某个算法，只需注释掉对应行。 学生可以轻松进行“消融实验”（Ablation Study）：比如，注释掉匈牙利算法，专门研究分支定界在指派问题上的表现，从而深刻理解“专用算法”与“通用算法”的性能鸿沟。

结果聚合与可视化触发。
run_all_solvers() 返回的 results 字典，是后续分析的基础。generate_visualizations(results) 函数会：
- 遍历 results，对每个求解器的结果，调用其对应的可视化生成脚本（如 bnb_Tree.py 接收 results["Branch and Bound"]）；
- 将生成的HTML文件（bnb_Tree.html, cutting_plane.html 等）写入 ./visualizations/ 目录；
- 最终在终端输出 Visualization files generated in ./visualizations/. Open them in your browser!。
这意味着，可视化不是附加功能，而是求解流程的自然产物。学生不必单独运行一个“画图脚本”，只要求解完成，图表就已就绪。

实操心得：experiment.py 中预设的 large_sparse 问题，是一个精心设计的教学陷阱。它的变量数 n=200，但 int_vars 只有 [0, 1, 2]（仅前三个变量需为整数），其余为连续变量。分支定界会因搜索空间过大而超时，割平面因松弛解通常已是整数而几乎不切割，匈牙利算法不适用（非标准指派），唯独蒙特卡洛法能快速给出一个高质量解。这个例子，生动诠释了“没有银弹，只有适配”。

4.3 可视化文档（HTML）的生成逻辑与教学应用

本包的HTML文档，不是静态网页，而是动态生成的算法叙事。它们的存在，是为了将代码中的抽象数据结构，转化为学生可感知的视觉对象。

生成机制：Python驱动，D3.js渲染。
以 bnb_Tree.html 为例，其生成流程如下：
1. bnb_Tree.py 接收 BranchAndBoundSolver 的完整求解日志（包含所有节点的 id, parent_id, solution, objective_value, bounds, status）；
2. bnb_Tree.py 将这些日志转换为一个标准JSON格式的树结构（tree_data.json），每个节点包含 name, parent, value（目标值）, color（状态码）等字段；
3. bnb_Tree.html 内嵌的 d3.js 代码读取 tree_data.json，并调用 d3.tree() 布局算法，自动生成节点坐标与连线；
4. 通过CSS样式和JavaScript事件，实现悬停提示、点击展开/折叠、颜色编码等功能。

这种“Python生成数据，JS渲染视图”的分离架构，本身就是现代Web开发的教学范例。学生可以轻易修改 bnb_Tree.py 中的数据转换逻辑（例如，只显示深度 < 5 的节点），或修改 bnb_Tree.html 中的CSS（例如，将“被剪枝”节点的颜色从红色改为半透明灰色），立刻看到效果变化。

教学应用：从“看图”到“读图”再到“改图”。
在课堂上，我将可视化分为三个教学阶段：
- 阶段一：看图识算法。 让学生观察 bnb_Tree.html，提问：“哪一部分代表‘分支’？哪一部分代表‘定界’？被剪掉的节点，为什么是红色？” 引导他们将视觉元素（连线、颜色、位置）与算法概念（分支操作、上界比较、剪枝决策）一一对应。
- 阶段二：读图析性能。 提供两个不同分支策略（most_fractional vs smallest_index）生成的 bnb_Tree.html，让学生比较：哪棵树更深？哪棵树更宽？哪棵树的红色节点更多？进而讨论“策略如何影响搜索效率”。
- 阶段三：改图促理解。 布置作业：“修改 bnb_Tree.py，使其在每个节点上显示该节点的 bounds（变量界）。修改 bnb_Tree.html，使悬停时显示 bounds 详情。” 这个作业，迫使学生深入理解 BNBNode 类的结构，并掌握JSON数据格式与D3.js数据绑定的原理。

注意：所有HTML文件均使用纯前端技术（HTML/CSS/JS），不依赖任何服务器。学生双击即可在浏览器中打开，完美适配离线教学环境。README.md 中特别强调：“所有可视化均可离线运行，无需网络连接或本地服务器。”

5. 教学实战：常见问题、避坑指南与独家调试技巧

5.1 分支定界法：那些年我们踩过的“剪枝”深坑

分支定界看似逻辑清晰，实操中却布满陷阱。以下是学生在 branch_and_bound.py 上最常遇到的五个问题，及其根源与解决方案：

问题1：搜索树无限增长，程序卡死。
现象： experiment.py 运行后，CPU占用100%，终端无输出，bnb_Tree.html 为空。
根源： BNBTree 的优先队列中，节点 objective_value 相同，导致 heapq 无法比较节点对象，陷入无限循环。heapq 要求可比较对象，而 BNBNode 类未定义 __lt__ 方法。
解决方案： 在 BNBNode 类中，添加 def __lt__(self, other): return self.objective_value < other.objective_value。这是Python中 heapq 的硬性要求，也是教学中强调“数据结构契约”的绝佳案例。我们在 branch_and_bound.py 的 BNBNode 类定义后，用 # NOTE: Required for heapq to compare nodes 注释明确标出。

问题2：找到了解，但不是最优解。
现象： result['objective_value'] 比 scipy.optimize.linprog 的连续松弛解还差，或与匈牙利算法结果不一致。
根源： 忘记在 BranchAndBoundSolver._update_best_solution() 中检查 is_integer。分支定界求解的是松弛问题，其解 x* 可能是非整数，若误将其当作整数解更新了上界，后续所有剪枝都将失效。
解决方案： 严格遵循 if node.is_integer and node.objective_value < self.best_objective: 的双重检查。我们在 README.md 的“调试清单”中，将此列为第一条：“永远检查 node.is_integer！”

问题3：分支变量选择错误，导致树极不平衡。
现象： bnb_Tree.html 显示一棵极其倾斜的树，大部分节点集中在一条长链上。
根源： branch_variable_selection 策略实现有误。例如，在 most_fractional 策略中，错误地计算了 fractional_part = x_i - np.floor(x_i)，而未处理 x_i 为负数的情况（np.floor(-1.3) = -2.0，导致 fractional_part = 0.7，但正确的小数部分应为 0.3）。
解决方案： 使用 fractional_part = x_i - np.floor(x_i) 仅适用于 x_i >= 0；通用解法是 fractional_part = x_i - np.trunc(x_i)，或更稳妥的 fractional_part = np.abs(x_i - np.round(x_i))。我们在 BranchAndBoundSolver._select_branch_variable() 的注释中，用 # For negative numbers, use np.trunc to get correct fractional part 明确警示。

问题4：bounds 更新错误，导致子问题无解。
现象： solve_relaxation() 报错 Optimization failed. Unable to find a feasible starting point.
根源： 在创建子节点时，bounds 更新逻辑错误。例如，对变量 i 分支，左子节点设 x_i <= floor(x_i*)，但 floor(x_i*) 计算错误，或 bounds[i] 被错误地设置为 (lower_bound, floor(x_i*))，而 lower_bound 本身已大于 floor(x_i*)，导致区间为空。
解决方案： 在 BNBNode.__init__() 中，添加 assert self.bounds[i][0] <= self.bounds[i][1], f"Invalid bounds for variable {i}: {self.bounds[i]}"。这个断言会在问题发生时立即报错，并指出具体变量，极大加速调试。

问题5：bnb_Tree.html 不显示或显示空白。
现象： 浏览器打开 bnb_Tree.html，一片空白，或控制台报错 tree_data.json not found。
根源： experiment.py 未成功运行，或 generate_visualizations() 被跳过，导致 tree_data.json 文件未生成。
解决方案： 教学中，我要求学生养成习惯：运行 experiment.py 后，立即检查 ./visualizations/ 目录是否存在 tree_data.json。若不存在，说明求解过程在生成日志前已崩溃。此时，应将 BranchAndBoundSolver.solve() 中的 try...except 块暂时移除，让原始异常信息直接打印到终端，这是最直接的调试路径。

5.2 割平面法：Gomory切割的“几何直觉”培养指南

割平面法的难点，不在于代码实现，而在于建立对“切割有效性”的几何直觉。以下是帮助学生跨越这一障碍的三个独家技巧：

技巧1：用二维图解“切割”的本质。
在讲解 generate_gomory_cut() 前，我必画一个二维图：横轴 x0，纵轴 x1，画出松弛可行域（一个多边形），标出其顶点，其中一个是非整数最优解 x*=(1.2, 0.8)。然后，我现场推导Gomory切割：0.2*x0 + 0.8*x1 >= 0.8，并在图上画出这条直线。学生立刻看到，这条直线恰好穿过 x*，并将 x* 所在的顶点“切掉”，但所有整数点（(0,0), (1,0), (0,1), (1,1)）都位于该直线的“可行侧”。这个图解，胜过千行代码注释。

技巧2：“反向验证”强化公式的可信度。
在 generate_gomory_cut() 函数末尾，我们加入一段“反向验证”代码：

# Verify: All integer points in original feasible set must satisfy the cut
# (This is a teaching aid, not for production)
integer_points_to_test = [(0,0), (1,0), (0,1), (1,1), (2,0), (0,2)]
for pt in integer_points_to_test:
    if np.dot(cut_coeff, pt) < cut_rhs - 1e-8:  # Tolerance for float error
        raise ValueError(f"Cut violates integer point {pt}!")

这段代码在每次生成切割后，暴力检查几个典型整数点。它不提升性能，但极大地增强了学生对公式的信任——“哦，原来这个公式真的能保证不割掉整数点！” 这种“眼见为实”的验证，是建立数学直觉的基石。

技巧3：迭代过程可视化，捕捉“收紧”感。
cutting_plane.html 的动画，不是简单的帧切换，而是带有“可行域收缩”的视觉反馈。我们使用 d3.polygon() 绘制每次迭代后的可行域多边形，并用渐变色填充：初始为浅蓝，每次添加切割后，颜色加深一级。学生看着蓝色区域一步步变小、变紧凑，最终凝聚在一个小点附近，那种“可行域被不断收紧”的直观感受，是任何文字描述都无法替代的。在 README.md 中，我们称之为“几何收敛感训练”。

5.3 匈牙利算法：从“矩阵舞蹈”到“算法自信”的跃迁

匈牙利算法的优雅，常被其步骤的机械性所掩盖。以下是帮助学生跳出“照着步骤做”的三个关键跃迁点：

跃迁点1：理解“约减”为何不改变最优值。
学生常问：“为什么行减、列减后，最优指派不变？” 我的回答是：“想象你给所有工人涨薪100元，给所有任务加价50元，那么‘谁去做什么’的相对成本关系变了么？没有。最优指派依然是那个让总成本最小的组合。” step_one() 和 step_two() 中的 row_reduction 和 col_reduction 向量，就是这些“涨薪”和“加价”的数值。solve() 方法末尾的 original_cost = np.sum(row_red) + np.sum(col_red) + ...，就是把所有“涨薪”和“加价”加回去，还原真实成本。这个生活化类比，瞬间打通任督二脉。

跃迁点2：“覆盖线”是“零的分布密度”的度量。
step_three() 的目标是用最少直线覆盖所有零。我告诉学生：“覆盖线的数量，就是当前矩阵中‘零的稀缺程度’的量化指标。如果最少需要 n 条线（n 是矩阵阶数），说明零已经足够多、足够分散，足以构成一个完美匹配；如果只需要 k < n 条线，说明零还不够，我们需要调整矩阵来‘制造’更多零。” 这个视角，让学生不再把覆盖线当作一个孤立步骤，而是理解为整个算法的“进度条”。

跃迁点3：从“贪心分配”到“最大匹配”的认知升级。
当前 assign_zeros() 是贪心的，这在教学初期足够。但当学生提出“如果贪心失败怎么办？”，这就是引入图论的完美时机。我在 README.md 的“进阶挑战”中写道：“匈牙利算法的本质，是在一个二分图上寻找最大匹配。step_three() 中的标记过程，就是König定理的体现：最小点覆盖数 = 最大匹配数。尝试用DFS实现一个通用的最大二分图匹配算法，并将其集成到 HungarianSolver 中。” 这个挑战，将学生的视野从“矩阵操作”拉升到“图论建模”，完成了从“会做”到“懂为什么”的质变。

5.4 蒙特卡洛法：在“随机”中建立“工程确定性”的思维

蒙特卡洛法常被误解为“随便试试”，其教学价值恰恰在于破除这种误解。以下是培养学生“工程随机思维”的三个核心要点：

要点1：“采样分布”是领域知识的编码。
sample_feasible_point() 中的 strategy 参数，不是编程选项，而是领域专家经验的结晶。normal 策略隐含假设：“最优解附近是‘好解’的富集区”；log_uniform 策略隐含假设：“参数的尺度（orders of magnitude）比其绝对值更重要”。在课堂上，我会展示一个真实工程案例：优化一个化工反应器的温度与压力，其温度范围是 300K-800K，压力是 1atm-100atm。此时，uniform 采样会让 1atm 附近的点被过度采样，而 log_uniform 则能更均衡地覆盖 1, 10, 100 这些关键尺度。这教会学生：随机，不是无知，而是将无知转化为有根据的猜测。

要点2：“可行性校验”的分层，是计算资源的精打细算。
check_feasibility() 中的“快速预筛”和“约束分块”，是典型的工程权衡。我让学生计算：对于一个有 10000 个约束的问题，全量检查需 10000 次浮点乘加；而分块检查，若第一块 100 个约束就发现违规，则只需 100 次计算，效率提升 100 倍。这个计算，让学生明白：一个 if 语句，背后可能是 100 倍的性能差异。README.md 中，我们将此总结为：“在随机算法中，‘快’比‘准’更重要；一次快速的‘否’，胜过一百次缓慢的‘是’。”

要点3：“结果评估”是工程决策的依据。
MonteCarloSolver.solve() 返回的 statistics，是学生学习“如何做工程决策”的教科书。feasible_ratio 告诉你问题的难度；best_objective_history 告诉你收益递减的拐点；time_per_sample 告诉你硬件瓶颈。在期末项目中，我要求学生提交一份《蒙特卡洛求解报告》，必须包含这三项统计的分析，并据此回答：“如果预算只允许再采样 500 次，你预计目标值还能提升多少？理由是什么？” 这个问题，将随机算法从“黑箱”变成了“可预测、可规划”的工程工具。

最后分享一个小技巧：在 experiment.py 中，为蒙特卡洛求解器添加一个 seed 参数，如 MonteCarloSolver(seed=42)。这确保了每次运行结果可重现，是科学实验的基本要求，也是教学中调试与对比的基石。我们在所有 random 相关操作前，都调用 np.random.seed(seed)，并在 README.md 中强调：“可重现性（Reproducibility）是科学计算的第一准则。”

6. 教学延伸与个人体会：从实验包到思维范式的跃迁

这个“Python整数规划四算法实践包”，在我七年的教学实践中，早已超越了一个简单的代码仓库。它是我与学生共同构建的一座桥梁，一头连着教科书上抽象的定理与公式，另一头连着键盘上真实的敲击与屏幕上的动态可视化。每一次 python experiment.py 的运行，都不只是代码的执行，而是一场关于“计算”本质的微型思辨。

我最深刻的体会是：算法教学的终极目标，不是让学生记住“分支定界怎么做”，而是让他们建立起一种“计算思维范式”——一种将复杂问题分解为可计算、可验证、可可视化的子单元的能力。 当学生第一次亲手写出 BNBNode 类，并看到 bnb_Tree.html 中那棵由自己代码驱动的搜索树时，他们理解的不再是“分支”，而是“状态空间的遍历”；当他们手动推导出 generate_gomory_cut() 中的系数，并在 cutting_plane.html 中看到那条精准切割可行域的直线时，他们理解的不再是“割平面”，而是“凸集的几何约束”；当他们为 hungarian_assignment.py 添加一个 DFS 匹配模块，并成功解决一个贪心失败的案例时，他们理解的不再是“匈牙利算法”，而是“图论建模的力量”；当他们调整 monte_carlo.py 中的 seed 和 strategy，并分析 best_objective_history 曲线的拐点时，他们理解的不再是“随机采样”，而是“不确定性下的工程决策”。

这个包的设计哲学，始终围绕着一个朴素信念：最好的教学，是让学生感觉自己是算法的“共同作者”，而非“被动消费者”。 因此，我们拒绝一切黑盒，坚持手写核心；我们拥抱可视化，让抽象变得可触摸；我们鼓励修改，README.md 中的每一个“进阶挑战”，都是为好奇心预留的接口。我见过太多学生，在修改 bnb_Tree.py 以添加新颜色编码后，兴奋地跑来告诉我：“老师，我现在终于明白为什么分支定界比穷举快了——因为树不是满的，是被剪掉的！” 那一刻，我知道，教学的目的达到了。

这个包不会教你如何用 ortools 解决一个万亿级物流优化问题，但它会给你一把锤子，让你能亲手敲开任何整数规划问题的外壳，看看里面齿轮如何咬合，电流如何流动。它不是一个终点，而是一个起点——一个让你敢于质疑“求解器为什么这样设计”、敢于动手重写“某个模块以适应我的特殊需求”、敢于在真实世界的问题面前，说一句“让我试试看”的起点。

所以，如果你正站在讲台上，为如何让学生真正理解整数规划而思索；或者你正坐在电脑前，厌倦了调用黑盒API却不知其所以然；又或者你只是一个对“计算如何思考”充满好奇的探索者——那么，请打开这个包，从 experiment.py 开始运行。不要急于看结果，先读一读 branch_and_bound.py 中 BNBNode 类的注释，点开 bnb_Tree.html，试着拖拽那个红色的被剪枝节点。你会发现，算法不再是纸上的符号，而是一个有呼吸、有脉搏、等待你与之对话的生命体。

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

简介：提供开箱即用的Python整数规划教学实验资源，含四个独立可运行模块：branch_and_bound.py实现带剪枝策略的分支定界法，支持搜索树构建与最优解动态追踪；cutting_plane.py基于单纯形法迭代添加割平面约束，逐步收紧可行域至整数解；hungarian_assignment.py专用于标准指派问题，保证多项式时间复杂度与精确解；monte_carlo.py采用随机采样结合可行性校验的启发式流程，适合大规模或结构不规则问题。所有脚本均附详细注释、明确输入输出格式，并通过experiment.py统一调度演示。配套HTML文档覆盖各算法核心逻辑、关键函数接口及典型调用示例，其中bnb_Tree.html可视化分支过程，cutting_plane.html动态展示约束切割迭代，其余页面分别对应各模块原理说明与代码片段。项目包含完整目录结构、LICENSE声明、README使用指南及基础环境配置提示，适配高校线性规划课程实验、课堂演示与学生自主编程训练。

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