Improved Dual Bounds for Mixed-Integer Programs with Indicator Variables by Partitioning and Lagrangean Decomposition

Björn Morén () and Torbjörn Larsson ()
Additional contact information
Björn Morén: Linköping University
Torbjörn Larsson: Linköping University

Chapter Chapter 10 in Operations Research Proceedings 2023, 2025, pp 73-79 from Springer

Abstract: Abstract We consider mixed-integer programs with non-convex objectives that are modelled with indicator variables. Because this modelling typically requires the use of big-M values, such programs often have weak linear programming relaxations. The dual bound in a branch-and-bound tree therefore improves only slowly, which results in very long solution times. To strengthen the dual bound we partition the problem and then apply Lagrangean decomposition in order to obtain independent subproblems. We show for an application to support vector machines with ramp loss, that the dual bound can be improved compared to the bound obtained from a full mixed-integer programming formulation. Moreover, the subproblems can be efficiently solved in parallel.

Keywords: Mixed-integer programming; Indicator variables; Lagrangean decomposition; Support vector machines with ramp loss (search for similar items in EconPapers)
Date: 2025
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:lnopch:978-3-031-58405-3_10

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

DOI: 10.1007/978-3-031-58405-3_10

Access Statistics for this chapter

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