位置：立项数据库 > 立项详情页
大规模整数线性规划直接搜索算法
  • 项目名称：大规模整数线性规划直接搜索算法
  • 项目类别：面上项目
  • 批准号：70971136
  • 申请代码：G010301
  • 项目来源：国家自然科学基金
  • 研究期限：2010-01-01-2012-12-31
  • 项目负责人：倪明放
  • 负责人职称：教授
  • 依托单位：中国人民解放军理工大学
  • 批准年度：2009
中文摘要：

管理，计划等人类活动中产生的大量实际问题都涉及整数线性规划问题的求解.全球化趋势更凸显大规模问题求解的重要，而现有算法在处理这类问题时常显得效不从心。本项目力图另辟奇径，将近年来发展的线性规划算法中对偶投影搜索、最钝角原理和松弛方法，特别是非标准单纯形算法技术巧妙地整合应用，推出大规模整数线性规划的直接搜索算法。与传统算法相比, 新算法极具创新性。 它将节省求解松弛线性规划子问题所耗费的繁复计算，大大提高计算效率。 众所周知，实践中所需要的常常是问题的近似解而非精确解；新算法特别适合于这类情形的快速有效处理。

中文主题词： 线性规划；整数规划；松弛方法；直接搜索；
英文摘要：

Linear Programming；Integer programming；Relaxation；Direct search；

英文主题词： Linear Programming；Integer programming；Relaxation；Direct search；
结论摘要：

本研究项目对于混合整数线性规划问题的预处理、整数线性规划的分支定界算法、线性规划的单纯形方法快速计算、整数线性规划问题的松弛方法、整数线性规划问题遗传算法的研究取得了重要成果。特别是在线性规划的仿射尺度主元算法和组合算法、整数线性规划问题的松弛子问题的构造和计算等研究中取得了突破性的进展。

成果综合统计
成果类型
数量
  • 期刊论文
  • 会议论文
  • 专利
  • 获奖
  • 著作
  • 22
  • 3
  • 0
  • 0
  • 2
期刊论文
A two-phase method for multidimensional number partitioning problem
求解武器目标分配问题的一个近似最优方法
改进遗传算法在城市交通诱导策略中的应用
A Lagrange Relaxation Method for Solving Weapon-Target Assignment Problem
多约束最优路由选择和不相交路由选择问题
A FAST SIMPLEX ALGORITHM FOR LINEAR PROGRAMMING
混合整数线性规划问题中的预处理
军队人力资源培训问题的整数线性规划模型
整数线性规划的改进分支定界算法
求最大数目不相交多约束QoS路由的一种新方法
用直接比较策略的组合混沌遗传算法求解武器-目标分配问题
求QoS路由的一种整数线性规划方法
Dynamic Route Guidance Using Improved Genetic Algorithms
多约束最短链路不相交路径的启发式算法
一种求解ＷＴＡ问题的二次松弛方法
An affine-scaling pivot algorithm for linear programming
求不相交QoS路由的一种整数线性规划方法
关于Kallio—Porteus的一类线性规划算法的推广
会议论文
A Method Based on Penalty Function and Integer Programming for QoS Routing Problem
Heuristic Algorithm for K-disjoint QoS Routing Problem
A Simple and Fast Algorithm for Restricted Shortest Path Problem
著作
线性规划计算（上）
线性规划计算（下）
相关项目
整数规划问题的DNA计算模型研究与探索
期刊论文 53 会议论文 36
线性规划在空间目标与碎片观测中的应用
期刊论文 4
基于碳排放的多级供应链优化问题的理论与算法研究
期刊论文 42
批量订货下联合库存定价问题的研究
期刊论文 5 著作 1
非凸二次优化的一些理论与应用
期刊论文 14
正广义系统的能控性、能观性分析及若干综合问题研究
期刊论文 7 会议论文 3 获奖 1
基于KKT条件的优化递归神经网络簇设计
期刊论文 6 会议论文 7 获奖 1
线性规划对偶投影最钝角松弛算法的研究
期刊论文 3
离散事件系统的监督控制重构及其优化方法的研究
期刊论文 14 会议论文 7 专利 1
倪明放的项目