A LAGRANGEAN DUAL ASCENT ALGORITHM FOR SIMPLE PLANT LOCATION-PROBLEMS

被引：35
作者：
GUIGNARD, M
机构：
[1] Univ of Pennsylvania, Philadelphia,, PA, USA, Univ of Pennsylvania, Philadelphia, PA, USA
来源：
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 1988年 / 35卷 / 02期
关键词：
COMPUTER PROGRAMMING - Algorithms - MATHEMATICAL PROGRAMMING;
D O I：
10.1016/0377-2217(88)90029-X
中图分类号：
C93 [管理学];
学科分类号：
12 ; 1201 ; 1202 ; 120202 ;
摘要：
We propose to strengthen the separable Lagrangean relaxation of the Simple Plant Location Problem (SPLP) by using Benders inequalities generated during a Lagrangean dual ascent procedure. These inequalities are expressed in terms of the 0-1 variables only, and they can be used as knapsack constraints in the pure integer part of the Lagrangean relaxation. We show how coupling this technique with a good primal heuristic can substantially reduce integrality gaps.
引用
收藏
页码：193 / 200
页数：8
相关论文
共 10 条
[1]  
Bilde O., 1977, ANN DISCRETE MATH, V1, P79
[2]   LOCATION OF BANK ACCOUNTS TO OPTIMIZE FLOAT - ANALYTIC STUDY OF EXACT AND APPROXIMATE ALGORITHMS [J].
CORNUEJOLS, G ;
FISHER, ML ;
NEMHAUSER, GL .
MANAGEMENT SCIENCE, 1977, 23 (08) :789-810
[3]   DUAL-BASED PROCEDURE FOR UNCAPACITATED FACILITY LOCATION [J].
ERLENKOTTER, D .
OPERATIONS RESEARCH, 1978, 26 (06) :992-1009
[4]   ALGORITHMUS 47 - AN ALGORITHM FOR THE SOLUTION OF THE 0-1 KNAPSACK-PROBLEM [J].
FAYARD, D ;
PLATEAU, G .
COMPUTING, 1982, 28 (03) :269-287
[5]  
Geoffrion A., 1974, MATH PROGRAMMING STU, V2, DOI [10.1007/BFb0120690, DOI 10.1007/BFB0120686]
[6]  
GUIGNARD M, 1984, 57 U PENNS DEP STAT
[7]  
GUIGNARD M, 1983, IN PRESS EJOR
[8]   DIRECT SEARCH ALGORITHMS FOR ZERO-1 AND MIXED-INTEGER PROGRAMMING [J].
LEMKE, CE ;
SPIELBER.K .
OPERATIONS RESEARCH, 1967, 15 (05) :892-+
[9]   PLANT LOCATION WITH GENERALIZED SEARCH ORIGIN [J].
SPIELBERG, K .
MANAGEMENT SCIENCE SERIES A-THEORY, 1969, 16 (03) :165-178
[10]   ALGORITHMS FOR SIMPLE PLANT-LOCATION PROBLEM WITH SOME SIDE CONDITIONS [J].
SPIELBERG, K .
OPERATIONS RESEARCH, 1969, 17 (01) :85-+
1