A SURROGATE HEURISTIC FOR SET COVERING PROBLEMS

被引:46
作者
LORENA, LAN
LOPES, FB
机构
[1] Laboratório Associado de Computação e Matemática Aplicada (LAC), Instituto Nacional de Pesquisas Espaciais (INPE), 12201 Sao Jose dos Campos, SP
关键词
SET COVERING; OPTIMIZATION; SURROGATE RELAXATION; HEURISTICS;
D O I
10.1016/0377-2217(94)90401-4
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
The purpose of this paper is to present a new heuristic for set covering problems, based upon continuous surrogate relaxations and subgradient optimization. The algorithm combines problem reduction tests, an adequate step size control, and avoid preliminary sorting in solving the continuous surrogate relaxations. Computational tests for large scale set covering problems (up to 1 000 rows and 12 000 columns) indicate better-quality results than algorithms based on Lagrangian relaxations in terms of final solutions and mainly in computer times. Although the solving of a single surrogate optimization problem is slower than a corresponding Lagrangian optimization, the overall performance is almost twice as fast. This is due to the smaller number of iterations which is a result of faster convergence and less oscillation.
引用
收藏
页码:138 / 150
页数:13
相关论文
共 56 条
  • [1] A GENERALIZATION OF POLYAK CONVERGENCE RESULT FOR SUBGRADIENT OPTIMIZATION
    ALLEN, E
    HELGASON, R
    KENNINGTON, J
    SHETTY, B
    [J]. MATHEMATICAL PROGRAMMING, 1987, 37 (03) : 309 - 317
  • [2] EFFICIENT HEURISTIC SOLUTIONS TO AN AIRLINE CREW SCHEDULING PROBLEM
    BAKER, EK
    BODIN, LD
    FINNEGAN, WF
    PONDER, RJ
    [J]. AIIE TRANSACTIONS, 1979, 11 (02): : 79 - 85
  • [3] AN ALGORITHM FOR LARGE ZERO-ONE KNAPSACK-PROBLEMS
    BALAS, E
    ZEMEL, E
    [J]. OPERATIONS RESEARCH, 1980, 28 (05) : 1130 - 1154
  • [4] BALAS E, 1980, MATH PROGRAM STUD, V12, P37, DOI 10.1007/BFb0120886
  • [5] BALAS E, 1979, COMBINATORIAL OPTIMI
  • [6] ON THE CHOICE OF STEP SIZE IN SUBGRADIENT OPTIMIZATION
    BAZARAA, MS
    SHERALI, HD
    [J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1981, 7 (04) : 380 - 388
  • [7] BEASLEY JE, 1990, NAV RES LOG, V37, P151, DOI 10.1002/1520-6750(199002)37:1<151::AID-NAV3220370110>3.0.CO
  • [8] 2-2
  • [9] AN ALGORITHM FOR SET COVERING PROBLEM
    BEASLEY, JE
    [J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1987, 31 (01) : 85 - 93
  • [10] BOWERS J, 1985, J OPER RES SOC, V36, P609