Search: id:"swepub:oai:research.chalmers.se:fa52c04f-7048-4027-a94f-a89faaac211d" >
Mixed-Integer Linea...
-
Strömberg, Ann-Brith,1961Gothenburg University,Göteborgs universitet,Institutionen för matematiska vetenskaper,Department of Mathematical Sciences
(author)
Mixed-Integer Linear Optimization: Primal–Dual Relations and Dual Subgradient and Cutting-Plane Methods
- Article/chapterEnglish2020
Publisher, publication year, extent ...
-
2020-02-29
-
Cham :Springer International Publishing,2020
Numbers
-
LIBRIS-ID:oai:research.chalmers.se:fa52c04f-7048-4027-a94f-a89faaac211d
-
https://research.chalmers.se/publication/521390URI
-
https://research.chalmers.se/publication/515688URI
-
https://doi.org/10.1007/978-3-030-34910-3_15DOI
-
https://gup.ub.gu.se/publication/297523URI
Supplementary language notes
-
Language:English
-
Summary in:English
Part of subdatabase
Classification
-
Subject category:kap swepub-publicationtype
-
Subject category:vet swepub-contenttype
Notes
-
This chapter presents several solution methodologies for mixed-integer linear optimization, stated as mixed-binary optimization problems, by means of Lagrangian duals, subgradient optimization, cutting-planes, and recovery of primal solutions. It covers Lagrangian duality theory for mixed-binary linear optimization, a problem framework for which ultimate success—in most cases—is hard to accomplish, since strong duality cannot be inferred. First, a simple conditional subgradient optimization method for solving the dual problem is presented. Then, we show how ergodic sequences of Lagrangian subproblem solutions can be computed and used to recover mixed-binary primal solutions. We establish that the ergodic sequences accumulate at solutions to a convexified version of the original mixed-binary optimization problem. We also present a cutting-plane approach to the Lagrangian dual, which amounts to solving the convexified problem by Dantzig–Wolfe decomposition, as well as a two-phase method that benefits from the advantages of both subgradient optimization and Dantzig–Wolfe decomposition. Finally, we describe how the Lagrangian dual approach can be used to find near optimal solutions to mixed-binary optimization problems by utilizing the ergodic sequences in a Lagrangian heuristic, to construct a core problem, as well as to guide the branching in a branch-and-bound method. The chapter is concluded with a section comprising notes, references, historical downturns, and reading tips.
Subject headings and genre
Added entries (persons, corporate bodies, meetings, titles ...)
-
Larsson, TorbjörnLinköpings universitet,Linköping University
(author)
-
Patriksson, Michael,1964Gothenburg University,Göteborgs universitet,Institutionen för matematiska vetenskaper,Department of Mathematical Sciences(Swepub:gu)xpatmi
(author)
-
Göteborgs universitetInstitutionen för matematiska vetenskaper
(creator_code:org_t)
Related titles
-
In:Numerical Nonsmooth Optimization: State of the Art AlgorithmsCham : Springer International Publishing, s. 499-547, s. 499-547
-
In:Numerical Nonsmooth OptimizationCham : Springer International Publishing, s. 499-547, s. 499-5479783030349103
Internet link
Find in a library
To the university's database