MATLAB实现的整数线性规划分支定界法求解器

资 源 简 介

本项目提供了一个基于分支定界法的通用整数线性规划求解器，完整实现了预处理、分支策略、定界和剪枝功能。支持全整数与混合整数规划问题，通过线性松弛解高效遍历搜索树，适用于标准形式优化求解。

详 情 说 明

基于分支定界法的通用整数线性规划求解器

项目介绍

本项目实现了一个完整的整数线性规划（ILP）分支定界算法求解器，能够高效求解标准形式的整数线性规划问题。该求解器支持全整数规划和混合整数规划，通过系统地遍历搜索树，利用线性松弛解确定上下界，有效减小搜索空间，最终找到满足整数约束的最优解。

功能特性

• 完整算法实现：包含预处理、分支策略、定界、剪枝等完整功能模块
• 混合整数规划支持：可处理全整数规划和混合整数规划问题
• 深度优先搜索策略：采用高效的节点搜索策略
• 线性规划松弛技术：利用松弛问题确定上下界，优化搜索过程
• 灵活的参数配置：支持最大迭代次数、容差等求解选项设置
• 详细的输出信息：提供迭代次数、节点数、求解时间等统计信息

使用方法

输入参数

• f：目标函数系数向量（n维列向量）
• A：不等式约束矩阵（m×n矩阵）
• b：不等式约束向量（m维列向量）
• Aeq：等式约束矩阵（p×n矩阵，可选）
• beq：等式约束向量（p维列向量，可选）
• lb：变量下界向量（n维向量，可选）
• ub：变量上界向量（n维向量，可选）
• intcon：整数变量索引向量（指定需要取整的变量位置）
• options：求解选项结构体（最大迭代次数、容差等参数）

输出结果

• x：满足整数约束的最优解向量
• fval：最优解对应的目标函数值
• exitflag：算法终止状态（0-收敛，1-超限，-1-无解等）
• output：包含迭代次数、节点数、求解时间等信息的结构体
• lambda：约束对应的拉格朗日乘子（可选）

调用示例

% 定义整数线性规划问题 f = [1; -2; 3]; A = [1 1 1; -1 2 0]; b = [5; 3]; intcon = [1, 3]; % 第1和第3个变量为整数变量

% 调用求解器 [x, fval, exitflag, output] = main(f, A, b, [], [], [], [], intcon);

系统要求

• MATLAB R2018b 或更高版本
• 需要安装 Optimization Toolbox（用于求解线性松弛问题）

文件说明

主程序文件整合了分支定界算法的核心功能，包括问题预处理、线性松弛求解、分支策略选择、边界更新与剪枝操作。该文件负责整体算法流程的控制，协调各个功能模块的协同工作，实现从问题输入到最优解输出的完整求解过程，同时提供详细的求解状态信息和性能统计。