MATLAB分支定界法实现混合整数线性规划

"MATLAB实现的分支定界算法用于解决混合整数线性规划问题" 在优化领域，分支定界（Branch and Bound）是一种有效的方法，用于解决混合整数线性规划（Mixed Integer Linear Programming, MILP）问题。MILP问题涉及到线性目标函数和线性约束条件，其中一部分决策变量需要取整数值。分支定界通过将问题分解为子问题并逐步缩小解的空间来找到全局最优解。 MATLAB中的`linprogdis`函数是用于执行分支定界算法的自定义实现。这个函数首先检查输入参数，包括整数约束向量`ifint`、目标函数向量`f`、不等式约束系数矩阵`A`和右端值向量`b`、等式约束矩阵`Aeq`和右端值向量`beq`、下界向量`lb`、上界向量`ub`以及初始猜测解`x0`和额外的选项`options`。 在处理数据后，`linprogdis`会调用MATLAB内置的`linprog`函数来解决线性规划问题。如果线性规划求解失败，`linprogdis`也会终止。对于包含整数约束的变量，`linprogdis`使用`find`函数找出整数变量的索引，并通过`checkint`辅助函数检查当前解是否满足整数约束。如果所有整数变量都满足整数约束，那么问题解决，否则，它会在最接近整数解的变量上进行分支，即创建左分支和右分支，分别考虑该变量小于或等于整数部分和大于整数部分的情况。 `checkint`函数的作用是判断一个向量中的元素是否为整数。如果元素与矩阵中的任何一行完全相等（视为整数），则返回1，否则返回0。在2005年10月28日的注释中，提到了可以使用`ismember`函数替换`ifrowinmat`以简化代码，提高效率。 分支定界的核心思想在于通过构造一个搜索树来探索所有可能的解空间，并通过下界和上界估计来剪枝，消除不可能产生最优解的分支。这个过程持续到找到全局最优解或者达到预设的停止条件（如迭代次数或时间限制）。 MATLAB提供的`linprog`函数本身并不直接支持整数变量，因此`linprogdis`是扩展`linprog`以处理MILP问题的一个实例。用户可以通过调用`linprogdis`并提供相应的输入参数来解决具有整数约束的线性规划问题。这个自定义的分支定界实现对于学术研究和工程应用都有很高的价值，特别是在没有商业优化器或者对求解过程有特定需求的情况下。