Picture water droplets

Developing mathematical theories of the physical world: Open Access research on fluid dynamics from Strathclyde

Strathprints makes available Open Access scholarly outputs by Strathclyde's Department of Mathematics & Statistics, where continuum mechanics and industrial mathematics is a specialism. Such research seeks to understand fluid dynamics, among many other related areas such as liquid crystals and droplet evaporation.

The Department of Mathematics & Statistics also demonstrates expertise in population modelling & epidemiology, stochastic analysis, applied analysis and scientific computing. Access world leading mathematical and statistical Open Access research!

Explore all Strathclyde Open Access research...

Local cuts and two-period convex hull closures for big-bucket lot-sizing problems

Akartunali, Kerem and Fragkos, Ioannis and Miller, Andrew J. and Wu, Tao (2016) Local cuts and two-period convex hull closures for big-bucket lot-sizing problems. INFORMS Journal on Computing, 28 (4). pp. 766-780. ISSN 1526-5528

[img]
Preview
Text (Akartunah-etal-INFORMS-JOC-2016-Local-cuts-and-two-period-convex-hull-closures-for-big-bucket)
Akartunah_etal_INFORMS_JOC_2016_Local_cuts_and_two_period_convex_hull_closures_for_big_bucket.pdf
Final Published Version
License: Creative Commons Attribution 4.0 logo

Download (315kB) | Preview

Abstract

Despite the significant attention they have drawn, big bucket lot-sizing problems remain notoriously difficult to solve. Previous work of Akartunali and Miller (2012) presented results (computational and theoretical) indicating that what makes these problems difficult are the embedded single-machine, single-level, multi-period submodels. We therefore consider the simplest such submodel, a multi-item, two-period capacitated relaxation. We propose a methodology that can approximate the convex hulls of all such possible relaxations by generating violated valid inequalities. To generate such inequalities, we separate two-period projections of fractional LP solutions from the convex hulls of the two-period closure we study. The convex hull representation of the two-period closure is generated dynamically using column generation. Contrary to regular column generation, our method is an outer approximation, and therefore can be used efficiently in a regular branch-and-bound procedure. We present computational results that illustrate how these two-period models could be effective in solving complicated problems.