miun.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Bilinear optimization in computational decision analysis
Mid Sweden University, Faculty of Science, Technology and Media, Department of Information Technology and Media. (FSCN - Fibre Science and Communication Network)
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: urn:nbn:se:miun:diva-8856OAI: oai:DiVA.org:miun-8856DiVA, id: diva2:214778
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
List of papers
1. Non-Linear Programming Solvers for Decision Analysis
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
2. A Fast Bilinear Optimization Algorithm
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
3. Cutting plane method in decision analysis
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
4. 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
5. 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
6. 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

Open Access in DiVA

No full text in DiVA

Authority records BETA

Ding, Xiaosong

Search in DiVA

By author/editor
Ding, Xiaosong
By organisation
Department of Information Technology and Media
Information Systems

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 1308 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf