Efficient implicit enumerative search for solution to integer linear programs

doi:10.3778/j.issn.1002-8331.2009.26.007

Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (26): 24-26.DOI: 10.3778/j.issn.1002-8331.2009.26.007

• 博士论坛 • Previous Articles Next Articles

Efficient implicit enumerative search for solution to integer linear programs

GAO Pei-wang

Department of Mathematics and Statistics，Guangxi University of Finance and Economics，Nanning 530003，China

Received:2009-06-03 Revised:2009-07-20 Online:2009-09-11 Published:2009-09-11
Contact: GAO Pei-wang

求解整数线性规划的一种高效隐数搜寻

高培旺

广西财经学院数学与统计系，南宁 530003

通讯作者: 高培旺

Abstract

Abstract: This paper presents a new implicit enumerative algorithm for integer linear programs.First of all，based on the optimality of the linear programming relaxation problem，a linear transformation of the optimal nonbasic variables into new variables is introduced so that the new variables have fewer intervals.Then，an efficient implicit enumerative search is done on the nonbasic variables and new ones on the objective function hyperplane.The algorithm is of interests in theory.

Key words: linear programming, integer programming, linear transformation, implicit enumerative algorithm

摘要： 提出了一种求解整数线性规划的新的隐数算法。首先，该算法引入了一组线性变换，将线性松弛问题的最优非基变量变换到一组新变量，使新变量有更小的取值范围。然后，在目标函数超平面上对非基变量和新变量进行隐数计算，从而大大提高了隐数搜寻的效率。

关键词: 线性规划, 整数规划, 线性变换, 隐数算法

CLC Number:

O221.4

GAO Pei-wang. Efficient implicit enumerative search for solution to integer linear programs[J]. Computer Engineering and Applications, 2009, 45(26): 24-26.

高培旺. 求解整数线性规划的一种高效隐数搜寻[J]. 计算机工程与应用, 2009, 45(26): 24-26.

[1]	ZHANG Huiyu, CHEN Qingxin, MAO Ning. AGV Configuration Optimization of Manufacturing System with Random Batch Material Handling [J]. Computer Engineering and Applications, 2021, 57(4): 245-251.
[2]	ZHU Jiabao, ZHANG Jianxun, CHEN Hongling. Fast Style Transfer Method of Single Model and Multi-style [J]. Computer Engineering and Applications, 2021, 57(12): 201-206.
[3]	YANG Yajie, CHANG Daofang, YU Fang. Multi-Resource Coordinated Scheduling of Automated Terminals Considering AGV Collision Avoidance [J]. Computer Engineering and Applications, 2020, 56(6): 246-253.
[4]	MIN Chaobo. Image Registration via Adaptive Polynomial Mixture Transformation [J]. Computer Engineering and Applications, 2020, 56(23): 194-201.
[5]	GENG Haijun. Intra-Domain Routing Protection Scheme in Segment Routing Architecture [J]. Computer Engineering and Applications, 2019, 55(8): 80-85.
[6]	CHEN Gang, FU Jiangyue. Drone Distribution Center Location Problem Under Military-Civilian Integration Strategy [J]. Computer Engineering and Applications, 2019, 55(8): 226-231.
[7]	SONG Jian, FANG Xianwen, WANG Lili, LIU Xiangwei. Quasi Indirect Dependence Mining Method for Business Process Hide Transition [J]. Computer Engineering and Applications, 2019, 55(22): 265-270.
[8]	TANG Zhen, YIN Zhixiang, CUI Jianzhong, YANG Jing, SUN Xia. DNA Origami for an Application of Special Integer Programming Problem [J]. Computer Engineering and Applications, 2019, 55(16): 49-54.
[9]	LI Haiyan1, WANG Yanping1, ZHOU Jianyong2, LIU Jiufu2. Design of deadlock supervisor of partially controllable Petri nets [J]. Computer Engineering and Applications, 2018, 54(8): 48-54.
[10]	HAN Xiaolong, LI Shang, YANG Quanye. Strategic supply chain integration research based on genetic algorithm [J]. Computer Engineering and Applications, 2018, 54(2): 214-221.
[11]	WANG Xueqin1, JIANG Jianguo1，2, QI Meibin1，2. Application of global hierarchical association network in multi-target tracking [J]. Computer Engineering and Applications, 2018, 54(14): 180-185.
[12]	ZHENG Xingxing, XIE Minghong, ZHANG Yayun. Fast collision detection algorithm based on uniform spatial subdivision and linear programming [J]. Computer Engineering and Applications, 2017, 53(23): 236-240.
[13]	ZHANG Yaqi, YANG Bin, HU Zhihua, TIAN Maojin. Research of AGV charging and job integrated scheduling at automated container terminal [J]. Computer Engineering and Applications, 2017, 53(18): 257-262.
[14]	ZHOU Fei1, JIA Zhenhong1, YANG Jie2, Nikola Kasabov3. Enhancement method of remote sensing image based on NSCT and improved fuzzy contrast [J]. Computer Engineering and Applications, 2017, 53(15): 206-209.
[15]	ZENG Zhaomin1，GUAN Weili2, PAN Weiping3. Algorithm for generating optimal four-block cutting stock patterns of punched strips [J]. Computer Engineering and Applications, 2016, 52(20): 75-79.

Efficient implicit enumerative search for solution to integer linear programs

求解整数线性规划的一种高效隐数搜寻

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics