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

Area of Science:

• Optimization Theory
• Operations Research

Background:

• Existing methods for multiple-follower bilevel problems are inadequate for a newly defined class of problems.
• This new class features nonlinear followers with partitioned variables and weak constraints, allowing leader variables to be distributed among followers.

Purpose of the Study:

• To introduce a novel class of multiple-follower bilevel problems.
• To propose an effective heuristic decomposition approach for solving these problems.
• To demonstrate the approach's efficacy on a real-world cutting stock problem.

Main Methods:

• Developed an analytics-based heuristic decomposition approach.
• Utilized Monte Carlo simulation and k-medoids clustering to simplify bilevel problems.
• Integrated self-organising maps for enhanced performance on large-scale problems.
• Applied integer programming techniques to solve the reduced single-level problem.

Main Results:

• The proposed heuristic approach yields superior solutions compared to existing literature methods.
• Demonstrated significantly improved scalability for larger problem instances.
• Achieved substantial reductions in clustering times for large problems by using self-organising maps.
• Successfully applied the method to a practical forest harvesting cutting stock problem.

Conclusions:

• The novel heuristic decomposition approach effectively addresses the newly defined class of multiple-follower bilevel problems.
• The method offers a scalable and efficient alternative to existing techniques.
• The successful application to a cutting stock problem highlights its real-world applicability in operations research.