Picture map of Europe with pins indicating European capital cities

Open Access research with a European policy impact...

The Strathprints institutional repository is a digital archive of University of Strathclyde's Open Access research outputs. Strathprints provides access to thousands of Open Access research papers by Strathclyde researchers, including by researchers from the European Policies Research Centre (EPRC).

EPRC is a leading institute in Europe for comparative research on public policy, with a particular focus on regional development policies. Spanning 30 European countries, EPRC research programmes have a strong emphasis on applied research and knowledge exchange, including the provision of policy advice to EU institutions and national and sub-national government authorities throughout Europe.

Explore research outputs by the European Policies Research Centre...

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.