Search: id:"swepub:oai:research.chalmers.se:fa52c04f-7048-4027-a94f-a89faaac211d" >
Mixed-Integer Linea...
Mixed-Integer Linear Optimization: Primal–Dual Relations and Dual Subgradient and Cutting-Plane Methods
-
- Strömberg, Ann-Brith, 1961 (author)
- Gothenburg University,Göteborgs universitet,Institutionen för matematiska vetenskaper,Department of Mathematical Sciences
-
- Larsson, Torbjörn (author)
- Linköpings universitet,Linköping University
-
- Patriksson, Michael, 1964 (author)
- Gothenburg University,Göteborgs universitet,Institutionen för matematiska vetenskaper,Department of Mathematical Sciences
-
(creator_code:org_t)
- 2020-02-29
- 2020
- English.
-
In: Numerical Nonsmooth Optimization: State of the Art Algorithms. - Cham : Springer International Publishing. ; , s. 499-547, s. 499-547
- Related links:
-
https://research.cha...
-
show more...
-
https://research.cha...
-
https://doi.org/10.1...
-
https://gup.ub.gu.se...
-
show less...
Abstract
Subject headings
Close
- 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
- NATURVETENSKAP -- Matematik -- Beräkningsmatematik (hsv//swe)
- NATURAL SCIENCES -- Mathematics -- Computational Mathematics (hsv//eng)
- NATURVETENSKAP -- Matematik -- Annan matematik (hsv//swe)
- NATURAL SCIENCES -- Mathematics -- Other Mathematics (hsv//eng)
- NATURVETENSKAP -- Matematik -- Diskret matematik (hsv//swe)
- NATURAL SCIENCES -- Mathematics -- Discrete Mathematics (hsv//eng)
- NATURVETENSKAP -- Matematik -- Matematisk analys (hsv//swe)
- NATURAL SCIENCES -- Mathematics -- Mathematical Analysis (hsv//eng)
- NATURVETENSKAP -- Matematik (hsv//swe)
- NATURAL SCIENCES -- Mathematics (hsv//eng)
Keyword
- Non-smooth convex function
- Mixed-binary linear optimization
- Column generation
- Core problem
- Cutting planes
- Ergodic sequences
- Convexified problem
- Subgradient method
- Dantzig-wolfe decomposition
- Lagrange dual
- Column generation
- Convexified problem
- Core problem
- Cutting planes
- Dantzig-wolfe decomposition
- Ergodic sequences
- Lagrange dual
- Mixed-binary linear optimization
- Non-smooth convex function
- Subgradient method
Publication and Content Type
- kap (subject category)
- vet (subject category)
Find in a library
To the university's database