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 optimality condition for column generation on zero-one linear programs
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
2019 (English)In: Discrete Optimization, ISSN 1572-5286, E-ISSN 1873-636X, Vol. 31, p. 79-92Article in journal (Refereed) Published
Abstract [en]

Column generation is a linear programming method that, when combined with appropriate integer programming techniques, has been successfully used for solving huge integer programs. The method alternates between a restricted master problem and a column generation subproblem. The latter step is founded on dual information from the former one; often an optimal dual solution to the linear programming relaxation of the restricted master problem is used.

We consider a zero–one linear programming problem that is approached by column generation and present a generic sufficient optimality condition for the restricted master problem to contain the columns required to find an integer optimal solution to the complete problem. The condition is based on dual information, but not necessarily on an optimal dual solution. It is however most natural to apply the condition in a situation when an optimal or near-optimal dual solution is at hand.

We relate our result to a few special cases from the literature, and make some suggestions regarding possible exploitation of the optimality condition in the construction of column generation methods for integer programs.

Place, publisher, year, edition, pages
Elsevier, 2019. Vol. 31, p. 79-92
Keywords [en]
Zero–one linear programming, Integer linear programming, Discrete optimisation, Column generation, Optimality conditions
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-151698DOI: 10.1016/j.disopt.2018.09.001ISI: 000461538300006Scopus ID: 2-s2.0-85053921680OAI: oai:DiVA.org:liu-151698DiVA, id: diva2:1252559
Funder
Swedish Research Council, 621- 2005-2874
Note

Funding agencies Swedish Research Council [621-2005-2874]

Available from: 2018-10-02 Created: 2018-10-02 Last updated: 2019-04-01Bibliographically approved

Open Access in DiVA

The full text will be freely available from 2020-09-27 15:07
Available from 2020-09-27 15:07

Other links

Publisher's full textScopus

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
In the same journal
Discrete Optimization
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

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