DROPS

Document

DOI: 10.4230/OASIcs.ATMOS.2023.16

Subproblem Separation in Logic-Based Benders' Decomposition for the Vehicle Routing Problem with Local Congestion

Authors: Aigerim Saken and Stephen J. Maher

Published in: OASIcs, Volume 115, 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)

Abstract

Subproblem separation is a common strategy for the acceleration of the logic-based Benders' decomposition (LBBD). However, it has only been applied to problems with an inherently separable subproblem structure. This paper proposes a new method to separate the subproblem using the connected components algorithm. The subproblem separation is applied to the vehicle routing problem with local congestion (VRPLC). Accordingly, new Benders' cuts are derived for the new subproblem formulation. The computational experiments evaluate the effectiveness of subproblem separation for different methods applying new cuts. It is shown that subproblem separation significantly benefits the LBBD scheme.

Cite as

Aigerim Saken and Stephen J. Maher. Subproblem Separation in Logic-Based Benders' Decomposition for the Vehicle Routing Problem with Local Congestion. In 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023). Open Access Series in Informatics (OASIcs), Volume 115, pp. 16:1-16:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{saken_et_al:OASIcs.ATMOS.2023.16,
  author =	{Saken, Aigerim and Maher, Stephen J.},
  title =	{{Subproblem Separation in Logic-Based Benders' Decomposition for the Vehicle Routing Problem with Local Congestion}},
  booktitle =	{23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)},
  pages =	{16:1--16:12},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-302-7},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{115},
  editor =	{Frigioni, Daniele and Schiewe, Philine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2023.16},
  URN =		{urn:nbn:de:0030-drops-187771},
  doi =		{10.4230/OASIcs.ATMOS.2023.16},
  annote =	{Keywords: logic-based Benders' decomposition, vehicle routing, subproblem separation, connected components}
}

Document

DOI: 10.4230/LIPIcs.SEA.2017.6

Distributed Domain Propagation

Authors: Robert Lion Gottwald, Stephen J. Maher, and Yuji Shinano

Published in: LIPIcs, Volume 75, 16th International Symposium on Experimental Algorithms (SEA 2017)

Abstract

Portfolio parallelization is an approach that runs several solver instances in parallel and terminates when one of them succeeds in solving the problem. Despite its simplicity, portfolio parallelization has been shown to perform well for modern mixed-integer programming (MIP) and boolean satisfiability problem (SAT) solvers. Domain propagation has also been shown to be a simple technique in modern MIP and SAT solvers that effectively finds additional domain reductions after the domain of a variable has been reduced. In this paper we introduce distributed domain propagation, a technique that shares bound tightenings across solvers to trigger further domain propagations. We investigate its impact in modern MIP solvers that employ portfolio parallelization. Computational experiments were conducted for two implementations of this parallelization approach. While both share global variable bounds and solutions, they communicate differently. In one implementation the communication is performed only at designated points in the solving process and in the other it is performed completely asynchronously. Computational experiments show a positive performance impact of communicating global variable bounds and provide valuable insights in communication strategies for parallel solvers.

Cite as

Robert Lion Gottwald, Stephen J. Maher, and Yuji Shinano. Distributed Domain Propagation. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 6:1-6:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{gottwald_et_al:LIPIcs.SEA.2017.6,
  author =	{Gottwald, Robert Lion and Maher, Stephen J. and Shinano, Yuji},
  title =	{{Distributed Domain Propagation}},
  booktitle =	{16th International Symposium on Experimental Algorithms (SEA 2017)},
  pages =	{6:1--6:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-036-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{75},
  editor =	{Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.6},
  URN =		{urn:nbn:de:0030-drops-76236},
  doi =		{10.4230/LIPIcs.SEA.2017.6},
  annote =	{Keywords: mixed integer programming, parallelization, domain propagation, portfolio solvers}
}

Search Results

Documents authored by Maher, Stephen J.

Subproblem Separation in Logic-Based Benders' Decomposition for the Vehicle Routing Problem with Local Congestion

Abstract

Cite as

Distributed Domain Propagation

Abstract

Cite as

Thanks for your feedback!

Could not send message