liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • 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
Integral Simplex Methods for the Set Partitioning Problem: Globalisation and Anti-Cycling
Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.ORCID iD: 0000-0002-2081-2888
Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.ORCID iD: 0000-0003-2094-7376
2018 (English)In: Open Problems in Optimization and Data Analysis / [ed] Panos M. Pardalos, Athanasios Migdalas, Cham: Springer, 2018, p. 285-303Chapter in book (Refereed)
Abstract [en]

The set partitioning problem is a generic optimisation model with many applications, especially within scheduling and routing. It is common in the context of column generation, and its importance has grown due to the strong developments in this field. The set partitioning problem has the quasi-integrality property, which means that every edge of the convex hull of the integer feasible solutions is also an edge of the polytope of the linear programming relaxation. This property enables, in principle, the use of solution methods that find improved integer solutions through simplex pivots that preserve integrality; pivoting rules with this effect can be designed in a few different ways. Although seemingly promising, the application of these approaches involves inherent challenges. Firstly, they can get be trapped at local optima, with respect to the pivoting options available, so that global optimality can be guaranteed only by resorting to an enumeration principle. Secondly, set partitioning problems are typically massively degenerate and a big hurdle to overcome is therefore to establish anti-cycling rules for the pivoting options available. The purpose of this chapter is to lay a foundation for research on these topics.

Place, publisher, year, edition, pages
Cham: Springer, 2018. p. 285-303
Series
Springer Optimization and Its Applications, ISSN 1931-6828, E-ISSN 1931-6836 ; 141
Keywords [en]
Quasi-integrality, Set partitioning, Integral simplex method, Anti-cycling rules
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-153425DOI: 10.1007/978-3-319-99142-9_15ISBN: 9783319991412 (print)ISBN: 9783319991429 (electronic)OAI: oai:DiVA.org:liu-153425DiVA, id: diva2:1270661
Available from: 2018-12-14 Created: 2018-12-14 Last updated: 2018-12-18Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records BETA

Rönnberg, ElinaLarsson, Torbjörn

Search in DiVA

By author/editor
Rönnberg, ElinaLarsson, Torbjörn
By organisation
Optimization Faculty of Science & Engineering
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 31 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • 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