多约束最短链路不相交路径的启发式算法

为求解多约束最短链路不相交路径(MCSDP(k))问题,提出了一种启发式的整数规划方法:FHABIP,并给出了算法搜索方案。根据问题的整数线性约束集合具有的结构特点,利用拉格朗日乘子把整数线性约束集合中的复杂约束引入到目标函数中,导出具有约束系数矩阵是全幺模矩阵特点的整数线性规划问题,从而使这类问题能用单纯形法容易求解。MCSDP(k)在求解线性规划问题的迭代过程中很容易地被求出。算法实验结果表明该算法快速有效。

密码格中行列式的若干定义及性质比较研究

格密码学近年被认为是抗量子计算攻击的新型公钥密码系统之一.首先在前人工作的基础上,证明"满秩整数格的行列式必为正整数"的较强结果.其次给出"实数格的行列式是一个与基选择无关的格不变量"的完整证明.最后站在集合论、高等代数及抽象代数的交叉视角下指出国内外信息安全专业流行教材及文献中6处相关概念的描述不足之处,并给出具体改进建议.

工件带安装时间的单机排序问题的列生成算法

在求解大规模NP-困难的最优化问题方法中,列生成技术越来越受到重视.本文研究工件带有与加工次序有关的安装时间的单机排序问题,首先构造它的时间标号模型,结合D-W分解技术和分支定界方法,给出它的列生成算法.其中时间标号模型的线性松弛为原问题提供了很好的下界,然后提出一个近似算法.通过实验数据表明,我们的算法对中等规模的排序问题1|t_(ij),r_j|∑w_jC_j是有效的.

一类特殊超图的S-匹配最大值的一种算法

超图的S-匹配是图的匹配的推广,文章利用全幺模矩阵的一些性质,给出了一类特殊超图的S-匹配最大值的一种算法.

求QoS路由的整数线性规划方法

QoS路由的任务是在网络中寻找一条满足多个约束条件的路径使网络资源的利用达到最优.该问题是一个NP-完全问题.提出了一种新的基于整数线性规划模型选择路由的方法.思路是将复杂约束引入到目标函数作为罚项,得到一个松弛整数线性规划问题.因为约束系数矩阵是全幺模矩阵,松弛问题可以通过线性规划很快地求解.拉格朗日乘子的调整用罚函数的方法很容易计算.数值实验表明提出的方法是有效的.

求不相交QoS路由的一种整数线性规划方法

提出求解不相交QoS路由问题的一种整数线性规划方法.首先,利用一个0-1变量集合来表示不相交路由和路由的QoS需求;然后,通过拉格朗日乘子将集合中的复杂约束引入所导出的整数线性规划问题的目标函数中.因为约束系数矩阵是全幺模矩阵,所以这类整数线性规划问题能用单纯形法容易地求解,从而可在求解线性规划问题的迭代过程中求出不相交QoS路由.数值实验结果表明了所提出方法的有效性.