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
Accelerating convergence of cutting plane algorithms for disjoint bilinear programming
Mid Sweden University, Faculty of Science, Technology and Media, Department of Information Technology and Media. (FSCN - Fibre Science and Communication Network)
Georgia Institute of Technology, United States.
2007 (English)In: Journal of Global Optimization, ISSN 0925-5001, E-ISSN 1573-2916, Vol. 38, no 3, 421-436 p.Article 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.

Place, publisher, year, edition, pages
2007. Vol. 38, no 3, 421-436 p.
Keyword [en]
Bilinear programming, Cutting plane, Linear programming, Lower bounding, Polar cuts
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:miun:diva-8460DOI: 10.1007/s10898-006-9091-3ISI: 000247474300005Scopus ID: 2-s2.0-34249884787OAI: oai:DiVA.org:miun-8460DiVA: diva2:139819
Available from: 2009-01-26 Created: 2009-01-26 Last updated: 2018-01-13Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Authority records BETA

Ding, Xiaosong

Search in DiVA

By author/editor
Ding, Xiaosong
By organisation
Department of Information Technology and Media
In the same journal
Journal of Global Optimization
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 275 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