Strathprints Home | Open Access | Browse | Search | User area | Copyright | Help | Library Home | SUPrimo

On the equivalence of strong formulations for capacitated multi-level lot sizing problems with setup times

Wu, Tao and Shi, Leyuan and Geunes, Joseph and Akartunali, Kerem (2012) On the equivalence of strong formulations for capacitated multi-level lot sizing problems with setup times. Journal of Global Optimization, 53 (4). pp. 615-639. ISSN 0925-5001

[img]
Preview
PDF (Akartunali JOGO preprint version) - Submitted Version
Download (349Kb) | Preview

    Abstract

    Several mixed integer programming formulations have been proposed for modeling capacitated multi-level lot sizing problems with setup times. These formulations include the so-called facility location formulation, the shortest route formulation, and the inventory and lot sizing formulation with (l,S) inequalities. In this paper, we demonstrate the equivalence of these formulations when the integrality requirement is relaxed for any subset of binary setup decision variables. This equivalence has significant implications for decomposition-based methods since same optimal solution values are obtained no matter which formulation is used. In particular, we discuss the relax-and-fix method, a decomposition-based heuristic used for the efficient solution of hard lot sizing problems. Computational tests allow us to compare the effectiveness of different formulations using benchmark problems. The choice of formulation directly affects the required computational effort, and our results therefore provide guidelines on choosing an effective formulation during the development of heuristic-based solution procedures.

    Item type: Article
    ID code: 37400
    Keywords: equivalence, strong formulation, capacitated, multi-level lot, sizing problems, setup times, Management. Industrial Management
    Subjects: Social Sciences > Industries. Land use. Labor > Management. Industrial Management
    Department: Strathclyde Business School > Management Science
    Related URLs:
      Depositing user: Pure Administrator
      Date Deposited: 06 Feb 2012 12:08
      Last modified: 14 Feb 2013 04:33
      URI: http://strathprints.strath.ac.uk/id/eprint/37400

      Actions (login required)

      View Item

      Fulltext Downloads: