An integer programming column generation principlefor heuristic search methods

Zhao, Yixin (author): Nanjing University of Science and Technology, School of Automation

Larsson, Torbjörn (author): Linköpings universitet,Optimeringslära,Tekniska fakulteten

Rönnberg, Elina, 1981- (author): Linköpings universitet,Optimeringslära,Tekniska fakulteten

(creator_code:org_t)

2018-02-28
2020
English.
In: International Transactions in Operational Research. - : Wiley-Blackwell. - 0969-6016 .- 1475-3995. ; 27:1, s. 665-695

Related links:: https://urn.kb.se/re...; show more...; https://doi.org/10.1...; show less...

Abstract Subject headings

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.

About the subject

NATURAL SCIENCES: NATURAL SCIENCES; and Mathematics; and Computational Ma ...

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.