Mixed-Integer Linear Optimization: Primal–Dual Relations and Dual Subgradient and Cutting-Plane Methods

Ann-Brith Strömberg (), Torbjörn Larsson () and Michael Patriksson ()
Additional contact information
Ann-Brith Strömberg: Chalmers University of Technology and the University of Gothenburg
Torbjörn Larsson: Linköping University
Michael Patriksson: Chalmers University of Technology and the University of Gothenburg

Chapter Chapter 15 in Numerical Nonsmooth Optimization, 2020, pp 499-547 from Springer

Abstract: Abstract 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.

Keywords: Mixed-binary linear optimization; Convexified problem; Lagrange dual; Non-smooth convex function; Subgradient method; Ergodic sequences; Cutting planes; Column generation; Dantzig–Wolfe decomposition; Core problem (search for similar items in EconPapers)
Date: 2020
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-030-34910-3_15

Ordering information: This item can be ordered from
http://www.springer.com/9783030349103

DOI: 10.1007/978-3-030-34910-3_15

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().