Cargando…

An analytics-based heuristic decomposition of a bilevel multiple-follower cutting stock problem

This paper presents a new class of multiple-follower bilevel problems and a heuristic approach to solving them. In this new class of problems, the followers may be nonlinear, do not share constraints or variables, and are at most weakly constrained. This allows the leader variables to be partitioned...

Descripción completa

Detalles Bibliográficos
Autores principales: Fajemisin, Adejuyigbe O., Climent, Laura, Prestwich, Steven D.
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Springer Berlin Heidelberg 2021
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8550664/
https://www.ncbi.nlm.nih.gov/pubmed/34776568
http://dx.doi.org/10.1007/s00291-021-00638-9
_version_ 1784591003284406272
author Fajemisin, Adejuyigbe O.
Climent, Laura
Prestwich, Steven D.
author_facet Fajemisin, Adejuyigbe O.
Climent, Laura
Prestwich, Steven D.
author_sort Fajemisin, Adejuyigbe O.
collection PubMed
description This paper presents a new class of multiple-follower bilevel problems and a heuristic approach to solving them. In this new class of problems, the followers may be nonlinear, do not share constraints or variables, and are at most weakly constrained. This allows the leader variables to be partitioned among the followers. We show that current approaches for solving multiple-follower problems are unsuitable for our new class of problems and instead we propose a novel analytics-based heuristic decomposition approach. This approach uses Monte Carlo simulation and k-medoids clustering to reduce the bilevel problem to a single level, which can then be solved using integer programming techniques. The examples presented show that our approach produces better solutions and scales up better than the other approaches in the literature. Furthermore, for large problems, we combine our approach with the use of self-organising maps in place of k-medoids clustering, which significantly reduces the clustering times. Finally, we apply our approach to a real-life cutting stock problem. Here a forest harvesting problem is reformulated as a multiple-follower bilevel problem and solved using our approach.
format Online
Article
Text
id pubmed-8550664
institution National Center for Biotechnology Information
language English
publishDate 2021
publisher Springer Berlin Heidelberg
record_format MEDLINE/PubMed
spelling pubmed-85506642021-11-10 An analytics-based heuristic decomposition of a bilevel multiple-follower cutting stock problem Fajemisin, Adejuyigbe O. Climent, Laura Prestwich, Steven D. OR Spectr Original Article This paper presents a new class of multiple-follower bilevel problems and a heuristic approach to solving them. In this new class of problems, the followers may be nonlinear, do not share constraints or variables, and are at most weakly constrained. This allows the leader variables to be partitioned among the followers. We show that current approaches for solving multiple-follower problems are unsuitable for our new class of problems and instead we propose a novel analytics-based heuristic decomposition approach. This approach uses Monte Carlo simulation and k-medoids clustering to reduce the bilevel problem to a single level, which can then be solved using integer programming techniques. The examples presented show that our approach produces better solutions and scales up better than the other approaches in the literature. Furthermore, for large problems, we combine our approach with the use of self-organising maps in place of k-medoids clustering, which significantly reduces the clustering times. Finally, we apply our approach to a real-life cutting stock problem. Here a forest harvesting problem is reformulated as a multiple-follower bilevel problem and solved using our approach. Springer Berlin Heidelberg 2021-05-28 2021 /pmc/articles/PMC8550664/ /pubmed/34776568 http://dx.doi.org/10.1007/s00291-021-00638-9 Text en © The Author(s) 2021 https://creativecommons.org/licenses/by/4.0/Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/ (https://creativecommons.org/licenses/by/4.0/) .
spellingShingle Original Article
Fajemisin, Adejuyigbe O.
Climent, Laura
Prestwich, Steven D.
An analytics-based heuristic decomposition of a bilevel multiple-follower cutting stock problem
title An analytics-based heuristic decomposition of a bilevel multiple-follower cutting stock problem
title_full An analytics-based heuristic decomposition of a bilevel multiple-follower cutting stock problem
title_fullStr An analytics-based heuristic decomposition of a bilevel multiple-follower cutting stock problem
title_full_unstemmed An analytics-based heuristic decomposition of a bilevel multiple-follower cutting stock problem
title_short An analytics-based heuristic decomposition of a bilevel multiple-follower cutting stock problem
title_sort analytics-based heuristic decomposition of a bilevel multiple-follower cutting stock problem
topic Original Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8550664/
https://www.ncbi.nlm.nih.gov/pubmed/34776568
http://dx.doi.org/10.1007/s00291-021-00638-9
work_keys_str_mv AT fajemisinadejuyigbeo ananalyticsbasedheuristicdecompositionofabilevelmultiplefollowercuttingstockproblem
AT climentlaura ananalyticsbasedheuristicdecompositionofabilevelmultiplefollowercuttingstockproblem
AT prestwichstevend ananalyticsbasedheuristicdecompositionofabilevelmultiplefollowercuttingstockproblem
AT fajemisinadejuyigbeo analyticsbasedheuristicdecompositionofabilevelmultiplefollowercuttingstockproblem
AT climentlaura analyticsbasedheuristicdecompositionofabilevelmultiplefollowercuttingstockproblem
AT prestwichstevend analyticsbasedheuristicdecompositionofabilevelmultiplefollowercuttingstockproblem