Yi-Rong Zhu

A Level-3 Reformulation-linearization Technique Based Bound for the Quadratic Assignment Problem

  • Monique Guignard
  • Peter M. Hahn
  • William L. Hightower
  • Yi-Rong Zhu
    • Categories 0-1 Programming, Combinatorial Optimization Tags , , , , ,

    We apply the level-3 Reformulation Linearization Technique (RLT3) to the Quadratic Assignment Problem (QAP). We then present our experience in calculating lower bounds using an essentially new algorithm, based on this RLT3 formulation. This algorithm is not guaranteed to calculate the RLT3 lower bound exactly, but approximates it very closely and reaches it in some … Read more

    An Improved Algorithm for the Generalized Quadratic Assignment Problem

  • Monique Guignard
  • Peter M. Hahn
  • Artur Alves Pessoa
  • Yi-Rong Zhu
    • Categories 0-1 Programming, Combinatorial Optimization Tags , ,

    In the Generalized Quadratic Assignment Problem (GQAP), given M facilities and N locations, one must assign each facility to one location so as to satisfy the given facility space requirements, minimizing the sum of installation and facility interaction costs. In this paper, we propose a new Lagrangean relaxation and a lower bounding procedure for the … Read more