Friday, 15:45 - 16:10 h, Room: H 2038


Marianna Eisenberg-Nagy
Symmetry in RLT cuts for the quadratic assignment and standard quadratic optimization problems

Coauthors: Etienne De Klerk, Renata Sotirov, Uwe Truetsch


The reformulation-linearization technique (RLT), introduced in [W.,P. Adams, H.,D. Sherali, A tight linearization and an algorithm for zero-one quadratic programming problems, Management Science, 32(10): 1274-1290, 1986], provides a way to compute linear programming bounds on the optimal values of NP-hard combinatorial optimization problems. This type of method has become known as a lift-and-project strategy: the "lifting'' refers to the addition of new variables, and the "projection'' to projecting the optimal values of the new variables to a feasible point of the original problem.
We study the RLT technique for two specific problems, namely the standard quadratic program and the quadratic assignment problem (QAP). We show how one may solve the second level RLT relaxation with additional semidefinite programming constraints in the presence of suitable algebraic symmetry in the problem data. As a result we are able to compute the best known bounds for certain graph partitioning problems involving strongly regular graphs. These graph partitioning problems have QAP reformulations.


Talk 2 of the invited session Fri.3.H 2038
"Algebraic symmetry in semidefinite programming" [...]
Cluster 4
"Conic programming" [...]


  unsecured loans . Therefore, we can say that the active substances in its composition are more perfectly mixed. Vardenafil is not only present in the original Levitra Online, but also as part of its analogs.