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
An integer programming column generation principlefor heuristic search methods
Nanjing University of Science and Technology, School of Automation.
Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.ORCID iD: 0000-0003-2094-7376
Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.ORCID iD: 0000-0002-2081-2888
2019 (English)In: International Transactions in Operational Research, ISSN 0969-6016, E-ISSN 1475-3995, Vol. 27, no 1, p. 665-695Article in journal (Refereed) 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.

Place, publisher, year, edition, pages
Wiley-Blackwell, 2019. Vol. 27, no 1, p. 665-695
Keywords [en]
integer programming; column generation; metaheuristics; matheuristics; large neighbourhood search
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-148910DOI: 10.1111/itor.12521ISI: 000478733800029OAI: oai:DiVA.org:liu-148910DiVA, id: diva2:1222521
Note

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]

Available from: 2018-06-21 Created: 2018-06-21 Last updated: 2019-09-09

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Search in DiVA

By author/editor
Larsson, TorbjörnRönnberg, Elina
By organisation
Optimization Faculty of Science & Engineering
In the same journal
International Transactions in Operational Research
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

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