miun.sePublications
Change search
Link to record
Permanent link

Direct link
BETA
Ding, Xiaosong
Alternative names
Publications (10 of 10) Show all publications
Ding, X., Danielson, M. & Ekenberg, L. (2010). Disjoint Programming in Computational Decision Analysis. Journal of Uncertain Systems, 4(1), 4-13
Open this publication in new window or tab >>Disjoint Programming in Computational Decision Analysis
2010 (English)In: Journal of Uncertain Systems, ISSN 1752-8917, Vol. 4, no 1, p. 4-13Article in journal (Refereed) Published
National Category
Computer Sciences
Identifiers
urn:nbn:se:miun:diva-10002 (URN)
Available from: 2009-10-08 Created: 2009-10-08 Last updated: 2018-01-13Bibliographically approved
Ding, X. & Al-Khayyal, F. (2007). Accelerating convergence of cutting plane algorithms for disjoint bilinear programming. Journal of Global Optimization, 38(3), 421-436
Open this publication in new window or tab >>Accelerating convergence of cutting plane algorithms for disjoint bilinear programming
2007 (English)In: Journal of Global Optimization, ISSN 0925-5001, E-ISSN 1573-2916, Vol. 38, no 3, p. 421-436Article in journal (Refereed) Published
Abstract [en]

This paper presents two linear cutting plane algorithms that refine existing methods for solving disjoint bilinear programs. The main idea is to avoid constructing (expensive) disjunctive facial cuts and to accelerate convergence through a tighter bounding scheme. These linear programming based cutting plane methods search the extreme points and cut off each one found until an exhaustive process concludes that the global minimizer is in hand. In this paper, a lower bounding step is proposed that serves to effectively fathom the remaining feasible region as not containing a global solution, thereby accelerating convergence. This is accomplished by minimizing the convex envelope of the bilinear objective over the feasible region remaining after introduction of cuts. Computational experiments demonstrate that augmenting existing methods by this simple linear programming step is surprisingly effective at identifying global solutions early by recognizing that the remaining region cannot contain an optimal solution. Numerical results for test problems from both the literature and an application area are reported.

Keywords
Bilinear programming, Cutting plane, Linear programming, Lower bounding, Polar cuts
National Category
Computer Sciences
Identifiers
urn:nbn:se:miun:diva-8460 (URN)10.1007/s10898-006-9091-3 (DOI)000247474300005 ()2-s2.0-34249884787 (Scopus ID)
Available from: 2009-01-26 Created: 2009-01-26 Last updated: 2018-01-13Bibliographically approved
Ding, X. (2005). Bilinear optimization in computational decision analysis. (Doctoral dissertation). Sundsvall: Mittuniversitetet
Open this publication in new window or tab >>Bilinear optimization in computational decision analysis
2005 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

In real-life decision analysis, significant recognition has been given to theunrealistic expectation of numerically precise information. Many modernapproaches attempting to handle imprecision have focused more on representationand less on evaluation. The DELTA method, as one of the fewleading approaches, challenges this issue by its evaluation framework thatcan accommodate both precision and imprecision. However, computationally,DELTA and similar approaches may incur time-consuming calculationsdue to the introduction of imprecise information concerning probability andutility. In general, those problems are bounded non-convex bilinear optimizationprograms with disjoint linear constraints, which cannot be solvedeffectively by any existing general-purpose global optimization technique.This thesis presents two enhanced cutting plane algorithms for solvingbounded disjoint bilinear programs arising in computational decision analysis.Each algorithm consists of a local phase designed to determine a localoptimizer from an approximate solution, and a global phase designed to systematicallyexplore the feasible region, subset by subset. These two phasesare switched automatically during the global search procedure. The basicframework builds upon previously developed efficient cutting plane methods.By embedding the lower bounding technique in a branch and bound procedure,the improvement of their performances seems encouraging in the lightof computational experience. Even though the motivation to develop thesealgorithms stems from computational decision analysis, the idea can also beextended to the development of optimization approaches for handling generalbounded disjoint bilinear programs, especially for larger sized ones.

Place, publisher, year, edition, pages
Sundsvall: Mittuniversitetet, 2005
Series
Mid Sweden University doctoral thesis, ISSN 1652-893X ; 2
National Category
Information Systems
Identifiers
urn:nbn:se:miun:diva-8856 (URN)
Public defence
2005-05-27, O102, Åkroken, Sundsvall, 13:15 (English)
Opponent
Supervisors
Available from: 2009-05-06 Created: 2009-05-06 Last updated: 2018-01-13Bibliographically approved
Ding, X., Ekenberg, L. & Danielsson, M. (2004). A Fast Bilinear Optimization Algorithm. In: Proceedings of the Third International Conference on Nonlinear Analysis and Convex Analysis 2003 (NACA 2003). Yokohama: Yokohama Publishers
Open this publication in new window or tab >>A Fast Bilinear Optimization Algorithm
2004 (English)In: Proceedings of the Third International Conference on Nonlinear Analysis and Convex Analysis 2003 (NACA 2003), Yokohama: Yokohama Publishers , 2004Conference paper, Published paper (Refereed)
Abstract [en]

Computational decision analysis methods (such as DELTA) have been developed and implemented over a number of years for solving decision problems when vague and numerically imprecise information prevails. However, the evaluation phases in those methods often give rise to bilinear programming problems, which are time-consuming to solve in an interactive environment with general nonlinear programming solvers such as SNOPT. This paper proposes a linear programming based algorithm for solving this type of problems, thus enabling interactive use of such methods.

Place, publisher, year, edition, pages
Yokohama: Yokohama Publishers, 2004
Keywords
linear program, bilinear program, interval probability, utility theory, decision analysis
National Category
Computer Sciences
Identifiers
urn:nbn:se:miun:diva-1707 (URN)356 (Local ID)4-946552-15-4 (ISBN)356 (Archive number)356 (OAI)
Available from: 2008-09-30 Created: 2008-09-30 Last updated: 2018-01-12Bibliographically approved
Ding, X. & Al-Khayya, F. (2004). Cutting plane method in decision analysis. In: Proceedings of the Ninth Meeting of the Nordic Section of the Mathematical Programming Society, October 22–23, 2004, Linköpings universitet, Norrköping, Sweden.
Open this publication in new window or tab >>Cutting plane method in decision analysis
2004 (English)In: Proceedings of the Ninth Meeting of the Nordic Section of the Mathematical Programming Society, October 22–23, 2004, Linköpings universitet, Norrköping, Sweden, 2004Conference paper, Published paper (Other academic)
Abstract [en]

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.

Series
Linköping Electronic Conference Proceedings, ISSN 1650-3740
Keywords
cutting plane, lower bound, global optimization
National Category
Computer Sciences
Identifiers
urn:nbn:se:miun:diva-5688 (URN)2199 (Local ID)2199 (Archive number)2199 (OAI)
Available from: 2008-09-30 Created: 2008-09-30 Last updated: 2018-01-12Bibliographically approved
Ding, X. (2004). Fast local optimization in decision analytic software. (Licentiate dissertation). Sundsvall: Mittuniversitetet
Open this publication in new window or tab >>Fast local optimization in decision analytic software
2004 (English)Licentiate thesis, monograph (Other academic)
Abstract [en]

In decision analysis, significant recognition has been given to the fact that requiring numerically precise information seems unrealistic for real-life decision situations, Despite the emergence of many modern apporaches, which attempt to handle imprecise estimates, concentration has focused more on representation and less on evaluation. Methods such as the DELTA method  challenged this issue by its evaluation framework that can accommodate both precision an imprecision, and thus pushes forward the disign of advanced dicision analysis systems. However, computationally, DELTA may incur time-consuming calculations due to the introduction of imprecise information into the probability space as well as the value space. Although two fast linear programming based bilinear optimazation algorithms were suggested, which were supporsed to satisfy certain presumed conditions, they are found to be too restrictive.

This thesis presents a fast potimization approach that can be viewed as a generalized version of the two fast algorithms. The motivation stems from the attempts to discard those presumed conditions. This approach combines ideas from both matrix computations and linear programming, and is, in fact, an iterative method. Since the DELTA method inteds to compute the difference of two expected utilities, this bilinear optimization issue is non-convex, and thus will certainly touch upon the global optimization area. As previously suggested, actually all methods for global optimization consist of two phases: a global phose to thoroughly explore subsets of the feasible region where it is known the blobal optimum will be found, an a local phase to improve the approximation to some local optima, Basically, this fast algorithm is devoted to the local optimization phase.

Place, publisher, year, edition, pages
Sundsvall: Mittuniversitetet, 2004. p. 83
Series
Mid Sweden University licentiate thesis, ISSN 1652-8948 ; 2
Keywords
bilinear programming, decision analysis, optimization, linear progamming, decision support systems, iterative method
National Category
Computer Sciences
Identifiers
urn:nbn:se:miun:diva-9338 (URN)91-87908-79-4 (ISBN)
Presentation
(English)
Supervisors
Available from: 2009-07-10 Created: 2009-07-10 Last updated: 2018-01-13Bibliographically approved
Ding, X., Danielsson, M. & Ekenberg, L. (2004). Non-Linear Programming Solvers for Decision Analysis. In: Operations Research Proceedings 2003: Selected Papers of the International Conference on Operations Research (OR 2003) Heidelberg, September 3-5, 2003 (pp. 475). Springer
Open this publication in new window or tab >>Non-Linear Programming Solvers for Decision Analysis
2004 (English)In: Operations Research Proceedings 2003: Selected Papers of the International Conference on Operations Research (OR 2003) Heidelberg, September 3-5, 2003, Springer , 2004, p. 475-Conference paper, Published paper (Other academic)
Abstract [en]

Several methods have been developed over a number of years for solving decision problems when vague and numerically imprecise information prevails. However, the DELTA method and similar methods give rise to particular bilinear programming problems that are time consuming to solve in a real-time environment. This paper presents a set of benchmark tests for non-linear programming solvers for solving this special type of problems. With two existing linear programming based algorithms, it also investigates the performance of linear programming solvers for special decision situations in decision support systems.

Place, publisher, year, edition, pages
Springer, 2004
Keywords
decision analysis, nonlinear programming, linear programming, quadratic programming
National Category
Computer Sciences
Identifiers
urn:nbn:se:miun:diva-1708 (URN)355 (Local ID)3-540-21445-3 (ISBN)355 (Archive number)355 (OAI)
Available from: 2008-09-30 Created: 2008-09-30 Last updated: 2018-01-12Bibliographically approved
Ding, X., Danielson, M. & Ekenberg, L.Generalized Bilinear Decision Analysis.
Open this publication in new window or tab >>Generalized Bilinear Decision Analysis
(English)Manuscript (preprint) (Other academic)
National Category
Computer Sciences
Identifiers
urn:nbn:se:miun:diva-9369 (URN)
Available from: 2009-07-13 Created: 2009-07-13 Last updated: 2018-01-13Bibliographically approved
Ding, X. & Al-Khayyal, F. A. Global Optimization in Decision Analysis.
Open this publication in new window or tab >>Global Optimization in Decision Analysis
(English)Manuscript (preprint) (Other academic)
Abstract [en]

Computational decision analysis methods, such as the DELTA method, have been developed and implemented over a number of years for solving decision problems where vague and numerically imprecise information prevails. However, the evaluation phases in those methods often give rise to 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 algorithm that combines a cutting plane method with the lower bounding technique for solving this type of problem. The central theme is to identify the global optimum as early as possible in order to avoid generating unnecessary cuts in the convergent cutting plane procedure.

Keywords
decision analysis, noncovex program, global optimization
National Category
Computer Sciences
Identifiers
urn:nbn:se:miun:diva-6215 (URN)2200 (Local ID)2200 (Archive number)2200 (OAI)
Note
Submitted to Optimization 1029-4945 Available from: 2009-02-18 Created: 2009-02-18 Last updated: 2018-01-12Bibliographically approved
Ding, X. & Al-Khayyal, F. Improved Cutting Plane Methods for Disjoint Bilinear Programming.
Open this publication in new window or tab >>Improved Cutting Plane Methods for Disjoint Bilinear Programming
(English)Manuscript (preprint) (Other academic)
Keywords
linear programming, bilinear programming, non-convex programming, cutting plane, branch and bound, underestimation, global optimization
National Category
Computer Sciences
Identifiers
urn:nbn:se:miun:diva-6268 (URN)3061 (Local ID)3061 (Archive number)3061 (OAI)
Available from: 2009-02-18 Created: 2009-02-18 Last updated: 2018-01-12Bibliographically approved
Organisations

Search in DiVA

Show all publications