修剪
单纯形算法
线性规划
整数(计算机科学)
整数规划
数学优化
分界
计算机科学
算法
光学(聚焦)
分支和切割
节点(物理)
数学
工程类
物理
光学
生物
农学
程序设计语言
结构工程
出处
期刊:
[Michigan Technological University]
日期:2011-01-01
标识
DOI:10.37099/mtu.dc.etds/549
摘要
Linear programs, or LPs, are often used in optimization problems, such as improving manufacturing efficiency of maximizing the yield from limited resources. The most common method for solving LPs is the Simplex Method, which will yield a solution, if one exists, but over the real numbers. From a purely numerical standpoint, it will be an optimal solution, but quite often we desire an optimal integer solution. A linear program in which the variables are also constrained to be integers is called an integer linear program or ILP. It is the focus of this report to present a parallel algorithm for solving ILPs. We discuss a serial algorithm using a breadth-first branch-and-bound search to check the feasible solution space, and then extend it into a parallel algorithm using a client-server model. In the parallel mode, the search may not be truly breadth-first, depending on the solution time for each node in the solution tree. Our search takes advantage of pruning, often resulting in super-linear improvements in solution time. Finally, we present results from sample ILPs, describe a few modifications to enhance the algorithm and improve solution time, and offer suggestions for future work.
科研通智能强力驱动
Strongly Powered by AbleSci AI