Variable exponential neighborhood search for the long chain design problem

Yuli Zhang, Shiji Song*, Cheng Wu, Wenjun Yin

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

Although the long chain flexibility strategy is an effective way to match supplies with uncertain demands, few studies on how to implement an optimal strategy with minimum link costs have been conducted. In this paper, the optimal long chain design problem is formulated as a mixed 0-1 linear programming. Since it is proved to be NP-complete, an approximation algorithm is proposed to obtain a suboptimal solution, which is a 2-approximation algorithm under a quadrangle inequality condition. To further improve this solution, a variable exponential neighborhood search method is proposed. In this method, based on an equivalent quadratic reformulation, new neighborhoods are introduced, which contain exponential sizes of feasible solutions and also can be optimized efficiently. Experiments show that for most instances the proposed algorithms are superior to the CPLEX solver and other construction & improvement algorithms in both solution preciseness and computation time.

Original languageEnglish
Pages (from-to)269-277
Number of pages9
JournalNeurocomputing
Volume148
DOIs
Publication statusPublished - 19 Jan 2015
Externally publishedYes

Keywords

  • 2-Approximation
  • Long chain design
  • Variable neighborhood search

Fingerprint

Dive into the research topics of 'Variable exponential neighborhood search for the long chain design problem'. Together they form a unique fingerprint.

Cite this