A hybrid algorithm for solving network flow problems with side constraints

被引：10
|
作者：
Mathies, S [1 ]
Mevert, P [1 ]
机构：
[1] Free Univ Berlin, D-14195 Berlin, Germany
来源：
COMPUTERS & OPERATIONS RESEARCH | 1998年 / 25卷 / 09期
关键词：
network optimization; side constraints; basis partitioning;
D O I：
10.1016/S0305-0548(98)00001-X
中图分类号：
TP39 [计算机的应用];
学科分类号：
081203 ; 0835 ;
摘要：
We consider network flow problems with few additional linear side constraints. Three approaches for solving such problems are presented. The first method is a specialized Simplex Algorithm with primal partitioning of the basis. Secondly, Lagrangean relaxation is used, solving the dual problem by subgradient optimization. Finally, good starting solutions are generated by relaxing the side constraints, solving the resulting pure network problem, and using the solution of the pure network problem as an advanced start for a general LP-optimizer. Numerical tests show that a hybrid combination of Lagrangean relaxation and subsequent optimization by primal partitioning is most efficient. (C) 1998 Elsevier Science Ltd. All rights reserved.
引用
收藏
页码：745 / 756
页数：12
相关论文
共 50 条
  • [1] SOLVING NETWORK MANPOWER PROBLEMS WITH SIDE CONSTRAINTS
    PRICE, WL
    GRAVEL, M
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1984, 15 (02) : 196 - 202
  • [2] AN ALGORITHM FOR SOLVING QUADRATIC NETWORK FLOW PROBLEMS
    BOLAND, N
    GOH, CJ
    MEES, AI
    APPLIED MATHEMATICS LETTERS, 1991, 4 (04) : 61 - 64
  • [3] A FORWARD NETWORK SIMPLEX ALGORITHM FOR SOLVING MULTIPERIOD NETWORK FLOW PROBLEMS
    ARONSON, JE
    CHEN, BD
    NAVAL RESEARCH LOGISTICS, 1986, 33 (03) : 445 - 467
  • [4] Hybrid multi-strategy firefly algorithm for solving optimization problems with constraints
    Lv, Li
    Pan, Ning-Kang
    Xiao, Ren-Bin
    Wang, Hui
    Tan, De-Kun
    Kongzhi yu Juece/Control and Decision, 2024, 39 (08): : 2551 - 2559
  • [5] A high performance neural network for solving nonlinear programming problems with hybrid constraints
    Tao, Q
    Cao, JD
    Xue, MS
    Qiao, H
    PHYSICS LETTERS A, 2001, 288 (02) : 88 - 94
  • [6] A parallel solving algorithm for quantified constraints problems
    Vautard, Jeremie
    Lallouet, Arnaud
    Hamadi, Youssef
    22ND INTERNATIONAL CONFERENCE ON TOOLS WITH ARTIFICIAL INTELLIGENCE (ICTAI 2010), PROCEEDINGS, VOL 1, 2010,
  • [7] PRIMAL ALGORITHM FOR SOLVING A CAPACITATED NETWORK FLOW PROBLEM WITH ADDITIONAL LINEAR CONSTRAINTS
    CHEN, S
    SAIGAL, R
    NETWORKS, 1977, 7 (01) : 59 - 79
  • [8] A hybrid algorithm for solving clustering problems
    Dominguez, Enrique
    Munoz, Jose
    INNOVATIONS IN HYBRID INTELLIGENT SYSTEMS, 2007, 44 : 128 - 135
  • [9] A discrete-time neural network for solving nonlinear convex problems with hybrid constraints
    Yashtini, M.
    Malek, A.
    APPLIED MATHEMATICS AND COMPUTATION, 2008, 195 (02) : 576 - 584
  • [10] A new hybrid matheuristic optimization algorithm for solving design and network engineering problems
    Chagwiza, G.
    Jones, B. C.
    Hove-Musekwa, S. D.
    Mtisi, S.
    INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE AND ENGINEERING MANAGEMENT, 2018, 13 (01) : 11 - 19
12345