Xiaosong Ding
Department of Information Technology and Media, Mid-Sweden University, Sweden
Faiz Al-Khayyal
School of Industrial and Systems Engineering, Georgia Institute of Technology, USA
Download article
Published in: Nordic MPS 2004. The Ninth Meeting of the Nordic Section of the Mathematical Programming Society
Linköping Electronic Conference Proceedings 14:2, p. 23-36
Published: 2004-12-28
ISBN:
ISSN: 1650-3686 (print), 1650-3740 (online)
Several computational decision analysis approaches have been developed over a number of years for solving decision problems when vague and numerically imprecise information prevails. However; the evaluation phases in the DELTA method and similar methods often give rise to special bilinear programming problems; which are time-consuming to solve in an interactive environment with general nonlinear programming solvers. This paper proposes a linear programming based global optimization algorithm that combines the cutting plane method together with the lower bound information for solving this type of problems. The central theme is to identify the global optimum as early as possible in order to save additional computational efforts.
[1] Al-Khayyal; F.A. and Falk J.E. “Jointly Constrained Biconvex Programming”; Mathematics of Operations Research; 8:273-286; 1983.
[2] Al-Khayyal; F.A. “Jointly Constrained Bilinear Programs and Related Problems: An Overview”; Computers & Mathematics with Application; Vol.19; No.11:53-62; 1990.
[3] Balas; E. “Intersection Cuts - a New Type of Cutting Planes for Integer Programming”; Operations Research 19:19-39; 1971.
[4] Danielson; M. Computational Decision Analysis; Doctoral Thesis; Department of Computer and Systems Sciences; Stockholm University and Royal Institute of Technology; 1997.
[5] Danielson; M. “Generalized Evaluation in Decision Analysis”; in press; to appear in European Journal of Operational Research; 2004.
[6] Danielson; M. and Ekenberg; L. “A Framework for Analysing Decisions under Risk”; European Journal of Operational Research; Vol.104(3):474-484; 1998.
[7] Danielson; M. and Ekenberg; L. “Multi-criteria Evaluation of Decision Trees”; Proceedings of the 5th International Conference of the Decision Sciences Institute; 1999.
[8] Danielson; M. Ekenberg; L. Johansson; J. and Larsson; A. “The DecideIT Decision Tool”; Proceedings of ISIPTA-2003; 2003.
[9] Ding; X.S. Danielson; M. and Ekenberg; L. “Non-linear Programming Solvers for Decision Analysis Support Systems”; Proceedings of International Conference on Operations Research (OR 2003); pp.475-482; Springer-Verlag; 2004.
[10] Ding; X.S. Ekenberg; L. and Danielson; M. “A Fast Bilinear Optimization Algorithm”; submitted; 2003.
[11] Ekenberg; L. Boman; M. and Linneroth-Bayer; J. “General Risk Constraints”; Journal of Risk Research; 4(1):31-47; 2001.
[12] Ekenberg; L. Brouwers; L. Danielson; M. Hansson; K. Johansson; J. Riabacke; A. and Vári A. “Simulation and Analysis of Three Flood Management Strategies”; IIASA Interim Report; IR-03-003; Laxenburg; Austria; 2003.
[13] Gallo; G. and Ülkücü; A. “Bilinear Programming: an Exact Algorithm”; Mathematical Programming 12:173-194; 1977.
[14] Gill; P.E. Murray; W. and Saunders; M.A. “User’s Guide for SQOPT 5.3: A Fortran Package for Large-scale Linear and Quadratic Programming”; Report NA 97-4; Department of Mathematics; University of California; San Diego; USA; 1997.
[15] Horst; R. and Pardalos; P.M. Handbook of Global Optimization; Kluwer; Dordrecht; 1995.
[16] Konno; H. “Bilinear Programming”; Parts I and II; Technical Report No. 71-9 and 71-10; Operations Research House; Stanford University; USA; 1971.
[17] Pardalos; P.M. and Vavasis; S.A. “Quadratic Programming with One Negative Eigenvalue Is NP-hard”; Journal of Global Optimization; 1:15-23; 1991.
[18] Pardalos; P.M. and Romeijn; H.E. Handbook of Global Optimization Volume 2; Kluwer Academic Publishers; the Netherlands; 2002.
[19] Ritter; K. “A Method for Solving Maximum-Problems with a Nonconcave Quadratic Objective Function”; Z.Wahrscheinlichkeitstheorie verw. Geb. 4:340- 351; 1966.
[20] Sherali; H.D. and Adams; W.P. A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems; Kluwer Academic Publishers; Dordrecht/Boston/London; 1999.
[21] Sherali; H.D. and Alameddine; A. “A New Reformulation Linearization Algorithm for Bilinear Programming Problems”; Journal of Global Optimization; Vol.2:379-410; 1992.
[22] Sherali; H.D. and Shetty; C.M. “A Finitely Convergent Algorithm for Bilinear Programming Problems Using Polar Cuts and Disjunctive Face Cuts”; Mathematical Programming; Vol.19:14-31; 1980.
[23] Shetty; C.M. and Sherali; H.D. “Rectilinear Distance Location-Allocation Problem: A Simplex Based Algorithm”; Proceedings of the International Symposium on Extremal Methods and Systems Analyses; Springer-Verlag; Vol.174:442-464; 1980.
[24] http://www.tomlab.biz/
[25] Tuy; H. “Concave Programming under Linear Constraints”; Dokl. Akad. Naul SSR 159:32-35; English translation in Soviet Math. Dokl. 5:1437-1440; 1964.
[26] Vaish; H. and Shetty; C.M. “A Cutting Plane Algorithm for the Bilinear Programming Problem”; Naval Reaearch Logistics Quarterly 24:83-94; 1977.
