A HYBRID ALGORITHM FOR SOLVING NETWORK FLOW PROBLEMS WITH SIDE CONSTRAINTS

Authors
MATHIES S MEVERT P
Citation
S. Mathies et P. Mevert, A HYBRID ALGORITHM FOR SOLVING NETWORK FLOW PROBLEMS WITH SIDE CONSTRAINTS, Computers & operations research, 25(9), 1998, pp. 745-756
Citations number
22
Categorie Soggetti
Operatione Research & Management Science","Computer Science Interdisciplinary Applications","Operatione Research & Management Science","Computer Science Interdisciplinary Applications","Engineering, Industrial
Journal title
Computers & operations research → ACNP
ISSN journal
03050548
Volume
25
Issue
9
Year of publication
1998
Pages
745 - 756
Database
ISI
SICI code
0305-0548(1998)25:9<745:AHAFSN>2.0.ZU;2-V
Abstract
We consider network flow problems with few additional linear side cons traints. Three approaches for solving such problems are presented. The first method is a specialized Simplex Algorithm with primal partition ing of the basis. Secondly, Lagrangean relaxation is used, solving the dual problem by subgradient optimization. Finally, good starting solu tions are generated by relaxing the side constraints, solving the resu lting pure network problem, and using the solution of the pure network problem as an advanced start for a general LP-optimizer. Numerical te sts show that a hybrid combination of Lagrangean relaxation and subseq uent optimization by primal partitioning is most efficient. (C) 1998 E lsevier Science Ltd. All rights reserved.