混合整数规划中的几个启发式方法的研究

发布时间：2018-03-27 09:06

本文选题：混合整数规划　切入点：圆整启发式方法　出处：《北京交通大学》2017年硕士论文

【摘要】：混合整数规划在运输业、电力调度、天然气分配、石油混流等各个方面有着广泛的应用.研究表明,80%的工业问题都是混合整数规划问题,因此求解混合整数规划问题具有非常高的学术研究价值和实际应用价值.然而,混合整数规划是NP-hard问题,但线性规划可以在多项式时间内求解,因此在实际中通过求解混合整数规划的线性松弛问题来求解混合整数规划.随着计算机技术的发展,以线性规划求解器为工具,基于分支定界算法和割平面算法的混合整数规划求解器也随之出现,混合整数规划求解器包括预处理、节点选择、线性规划求解、启发式方法等模块.在求解混合整数规划问题中,启发式方法能够快速有效地根据问题本身提供的信息找到问题的可行解.本文主要研究混合整数规划中的几种启发式方法,首先介绍了几种常用的启发式方法,包括圆整启发式方法、潜水启发式方法和OCTANE启发式方法;之后通过数值实验来分析启发式方法找到解的效率.实验表明,不同的启发式方法找到解的效率不同,且同时调用多种启发式方法找到解的效率与单独调用一种启发式方法找到解的效率也有所不同,合理设置启发式方法的调用位置和调用频率才能更快更有效地找到混合整数规划的可行解.
[Abstract]:Mixed integer programming is widely used in transportation, electric power dispatching, natural gas distribution, oil mixed flow, etc. The research shows that 80% of industrial problems are mixed integer programming problems. Therefore, solving mixed integer programming problems has high academic value and practical application value. However, mixed integer programming is a NP-hard problem, but linear programming can be solved in polynomial time. Therefore, in practice, the mixed integer programming is solved by solving the linear relaxation problem of mixed integer programming. With the development of computer technology, the linear programming solver is used as a tool. The mixed integer programming solver based on branch and bound algorithm and cut plane algorithm also appears. The mixed integer programming solver includes preprocessing, node selection and linear programming solution. In solving mixed integer programming problems, the heuristic method can quickly and effectively find the feasible solution of the problem according to the information provided by the problem itself. In this paper, several heuristic methods in mixed integer programming are studied. This paper first introduces several common heuristic methods, including round heuristic method, diving heuristic method and OCTANE heuristic method, then analyzes the efficiency of the heuristic method by numerical experiments. The efficiency of different heuristic methods in finding solutions is different, and the efficiency of finding solutions by calling multiple heuristic methods at the same time is different from that of using one heuristic method alone. In order to find the feasible solution of mixed integer programming more quickly and more effectively, we can set the call position and frequency of heuristic method reasonably.
【学位授予单位】：北京交通大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O221.4

【相似文献】