-------------------------------------------------------------------------------------------------------------------

 

 

                   Department of Systems Engineering and Engineering Management

                             The Chinese University of Hong Kong

 

-------------------------------------------------------------------------------------------------------------------

 

Title:  New formulations and relaxations for mixed-binary quadratic optimization

 

 

Speaker:  Prof. Abdel LISSER from University of Paris - Sud

 

 

Abstract:

Since Burer's seminal paper on the copositive reformulation of mixed-binary QPs, many alternative formulations have been discussed. Moreover, most of them can be used as proper relaxations, if the intractable co(mpletely )positive cones are replaced by tractable approximations. While most of the approximation hierarchies have the disadvantage to use psd matrices of orders which rapidly increase with the level of approximation, alternatives focus on the problem of keeping psd matrix orders small, with the aim to avoid memory problems in the interior point algorithms.

To the best of our knowledge, this study is the first to treat the various variants from a common theoretical perspective (for the exact formulations), using concise arguments. Moreover, a small study of the notoriously hard quadratic assignement problem adds some empirical evidence on performance differences among them.

 

 

Bio:

Abdel Lisser graduated in Applied Mathematics and Econometrics at the University of Paris 1 jointly with University of Paris 7 in 1984. He got his PhD degree in 1987 at the University of Paris Dauphine (Paris  9) on Interior Point Methods (IPM). After a Postdoc at the research center of France Telecom on IPM for solving multicommodity flow Problems, he joined France Telecom Research Center as Research Engineer in 1990. He had been working on network design problems, survivability optimization problems, and semidefinite programming problems applied to clustering problems. He headed a research group from 1996 up to 2000 on Transmission and Infrastructure Network Optimization Problems. He got his Habilitation Thesis at the University of Paris 13 in 2000 on Multicommodity Flow Problems. He joined the University of Paris 11 as a full Professor in 2001 at the Faculty of Sciences, Department of Computer Science (LRI). From 2006 to 2013, he was heading the Graph Theory and Combinatorial Optimization group composed of 20 members (professors, researchers, PhD students). His main research topic is Combinatorial and stochastic optimization problems with applications to network design problems and recently to energy management problems.

 

 

This seminar is hosted by Prof. Janny Leung.

 

 

Venue: Room 513,

      William M.W. Mong Engineering Building (ERB),

      (Engineering Building Complex Phase 2)

      The Chinese University of Hong Kong.