Variable exponential neighborhood search for the long chain design problem

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.