liu.seSök publikationer i DiVA
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
An integer programming column generation principlefor heuristic search methods
Nanjing University of Science and Technology, School of Automation.
Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.ORCID-id: 0000-0003-2094-7376
Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.ORCID-id: 0000-0002-2081-2888
2019 (Engelska)Ingår i: International Transactions in Operational Research, ISSN 0969-6016, E-ISSN 1475-3995, Vol. 27, nr 1, s. 665-695Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

There is an increasing interest in integrating column generation and heuristic approaches to efficiently solve large-scale discrete optimisation problems. We contribute in this direction. Based on the insights from Lagrangian duality theory, we present an auxiliary problem that can be used for finding near-optimal solutions to a discrete column-oriented model. The structure of this auxiliary problem makes it suitable for being addressed with a heuristic search method involving column generation. To this end, we suggest a large neighbourhood search strategy where the repair step is to solve a column generation type subproblem. The suggested search strategy and mathematical models involved need to be tailored to the problem structure. To illustrate important design options and computational behaviour, four applications are studied: bin packing, generalised assignment, a resource allocation problem and the fixed-charge transportation problem.

Ort, förlag, år, upplaga, sidor
Wiley-Blackwell, 2019. Vol. 27, nr 1, s. 665-695
Nyckelord [en]
integer programming; column generation; metaheuristics; matheuristics; large neighbourhood search
Nationell ämneskategori
Beräkningsmatematik
Identifikatorer
URN: urn:nbn:se:liu:diva-148910DOI: 10.1111/itor.12521ISI: 000478733800029OAI: oai:DiVA.org:liu-148910DiVA, id: diva2:1222521
Anmärkning

Funding agencies:  Research School in Interdisciplinary Mathematics at Linkoping University; 1035 Equipment Pre-Research Field Foundation of China [61403120401]; Center for Industrial Information Technology (CENIIT) at Linkoping University [16.05]

Tillgänglig från: 2018-06-21 Skapad: 2018-06-21 Senast uppdaterad: 2019-09-09

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltext

Sök vidare i DiVA

Av författaren/redaktören
Larsson, TorbjörnRönnberg, Elina
Av organisationen
OptimeringsläraTekniska fakulteten
I samma tidskrift
International Transactions in Operational Research
Beräkningsmatematik

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 96 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf