Decomposition-Based Algorithms for Mixed-Integer Linear Programs with Integer Subproblems

María-I. Restrepo (), Bernard Gendron and Louis-Martin Rousseau ()
Additional contact information
María-I. Restrepo: IMT Atlantique
Bernard Gendron: Université de Montréal
Louis-Martin Rousseau: Polytechnique Montréal

A chapter in Combinatorial Optimization and Applications, 2024, pp 227-257 from Springer

Abstract: Abstract Mathematical decomposition methods have been extensively used in the last decades to solve large scale optimization problems. In this chapter, we study a special class of problems that, once reformulated through Benders decomposition, exhibit mixed-integer variables in the master problem and subproblems. In these problems, some master problem variables are bounded, and cardinality constraints restrict their use. We propose two decomposition-based algorithms to address these problems. The first algorithm generates classical optimality cuts from the linear programming relaxation of the subproblem. When no more of these classical cuts can be added, the algorithm adds a new type of integer Benders optimality cut to ensure the convergence of the method to an optimal solution. The second algorithm adds the relaxation of the Benders subproblem variables in the master problem and includes these variables in the composition of integer Benders optimality cuts. These approaches were tested on two problems: the multi-commodity facility location problem and the multi-activity shift scheduling problem. Computational results are presented on numerous instances with different characteristics to demonstrate the efficacy of these approaches.

Date: 2024
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:isochp:978-3-031-57603-4_11

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

DOI: 10.1007/978-3-031-57603-4_11

Access Statistics for this chapter

More chapters in International Series in Operations Research & Management Science from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().