A. Unzueta, L. Escudero, M. A. Garin Martín
Starting from the binary quadratic formulation of the Cross-Dock door Assignment Problem (CDAP) model, different Linearized mixed Integer Programming (LIP) formulations are proposed, by using the Adams-Sherali RLT-k scheme for k=1 and a new type of binary variables, being all of them mathematically equivalent to the quadratic one. Some of the LIPs are based on tight formulations taken from the literature and one is original to this work. Given the (possibly) high dimensions of the models, a Lagrangean Dualization (LD) and decomposition scheme is used for obtaining a (hopefully) tight lower bound of the optimal solution of the original model. Two new submodels are drawn from the so-named splitting variable formulation of each of the LIPs ones. Additionally, a lazy heuristic scheme is considered for obtaining feasible solutions based on the Lagrangean ones. A broad computational experiment is carried out to perform a benchmark among the different proposed formulations.
Palabras clave: Quadratic combinatorial optimization, Cross-dock allocation of origin-destination, Reformulation Linearization Technique, Lagrangean Dualization, Lazy heuristic
Programado
Optimización Entera y Combinatoria
10 de junio de 2022 16:00
Salón de Grados
