Invited Session Thu.2.MA 041

Thursday, 13:15 - 14:45 h, Room: MA 041

Cluster 14: Mixed-integer nonlinear programming [...]

Convex approaches for quadratic integer programs


Chair: Adam Nicholas Letchford and Samuel Burer



Thursday, 13:15 - 13:40 h, Room: MA 041, Talk 1

Adam Nicholas Letchford
A new separation algorithm for the Boolean quadric and cut polytopes

Coauthor: Michael M. Soerensen


A separation algorithm is a procedure for generating cutting planes. We present new separation algorithms for the Boolean quadric and cut polytopes, which are the polytopes associated with zero-one quadratic programming and the max-cut problem, respectively. Our approach exploits, in a non-trivial way, three known results in the literature: one on the separation of {0,\frac12}-cuts, one on the symmetries of the
polytopes in question, and one on the relationship between the polytopes. We remark that our algorithm for the cut polytope is the first combinatorial polynomial-time algorithm that is capable of separating over a class of valid inequalities that includes all odd bicycle wheel inequalities and all (p,2)-circulant inequalities.



Thursday, 13:45 - 14:10 h, Room: MA 041, Talk 2

Anja Fischer
The asymmetric quadratic traveling salesman problem


In the asymmetric quadratic traveling salesman problem (AQTSP) the costs are associated to any three nodes that are traversed in succession and the task is to find a directed tour of minimal total cost. The problem is motivated by an application in biology and includes the angular-metric TSP and the TSP with reload costs as special cases. We study the polyhedral structure of a linearized integer programming formulation, present several classes of facets and investigate the complexity of the corresponding separation problems. Some facets are related to the Boolean quadric polytope and others forbid conflicting configurations. A general strengthening approach is proposed that allows to lift valid inequalities for the asymmetric TSP to improved inequalities for AQTSP. Applying this for the subtour elimination constraints gives rise to facet defining inequalities for AQTSP. Finally we demonstrate the usefulness of the new cuts. Real world instances from biology can be solved up for to 100 nodes in less than 11 minutes. Random instances turn out to be difficult, but on these semidefinite relaxations improved by the cutting planes help to reduce the gap in the root node significantly.



Thursday, 14:15 - 14:40 h, Room: MA 041, Talk 3

John E. Mitchell
Quadratic programs with complementarity constraints

Coauthors: Lijie Bai, Jong-Shi Pang


We examine the relationship between a quadratic program with complementarity constraints (QPCC) and its completely positive relaxation. We show that the two problems are equivalent under certain conditions, even if the complementary variables are unbounded.
We describe the use of semidefinite programming to tighten up the quadratic relaxation of a QPCC when the quadratic objective function is convex.
When the variables are bounded,
a QPCC can be expressed as a mixed integer nonlinear program.


  payday loans online. On the global pharmaceutical market this medicine was issued in 2003 by two companies - Eli Lilly and ICOS. Initially, permission to sell Cialis was obtained in Europe, Australia, New Zealand.