\(\)
A class of strong lower bounds on the solution value of a Linearized Integer Programming (LIP) reformulation is introduced for the binary quadratic optimization model to assign origin and destination nodes to strip and stack doors, resp., in a cross-dock infrastructure, whose goal is to minimize the transportation cost of the commodities to be handled at the cross-dock. Strip- and stack-related decomposition submodels are developed by taking benefit of the Integer Linearization Property that appears in enlarged Generalized Assignment Problems (GAPs) as embedded in the original model. It is proved that their further tightening defines two new equivalent reformulations of the LIP model. Additionally, a linear search heuristic is provided for obtaining feasible solutions by exploiting the GAP structures. We present an extensive computational study on a broad set of instances that shows that the proposed joint scheme for lower bounding and feasible solution providing is very efficient. The scheme obtains an optimal solution for small and middle size instances taken from the literature, although straightforward use of a state-of-the-art MILP optimizer requires less computing time for the small ones. Moreover, the proposal outperforms the optimizer when solving the largest instances.
Article
View On solving the Cross-dock Door Assignment Problem, CDAP