Invited Session Mon.1.H 2038

Monday, 10:30 - 12:00 h, Room: H 2038

Cluster 4: Conic programming [...]

Applications of semidefinite optimization


Chair: Miguel F. Anjos



Monday, 11:00 - 11:25 h, Room: H 2038, Talk 2

Philipp Hungerländer
Semidefinite optimization approaches to some facility layout problems

Coauthors: Miguel F. Anjos, Franz Rendl


Facility layout is concerned with the optimal location of departments inside a plant according to a given objective function reflecting transportation and construction costs of a material-handling system. The Multi-Row Facility Layout Problem is concerned with optimizing the placement of departments along one or several rows. The Directed Circular Facility Layout Problem searches for the optimal arrangement of departments on a circle and contains several layout problems extensively discussed in the literature, namely the Equidistant Unidirectional Cyclic Layout Problem, the Balanced Unidirectional Cyclic Layout Problem and the Directed Circular Arrangement Problem, as special cases. We show that all these layout problems can be modeled as Quadratic Ordering Problems and hence solved to global optimality using a general semidefinite programming approach. We report optimal solutions for several single-row instances from the literature with up to 42 departments that remained unsolved so far. Furthermore we provide high-quality global bounds for double-row instances with up to 16 departments and optimal arrangements for directed circular instances with up to 80 departments.



Monday, 11:30 - 11:55 h, Room: H 2038, Talk 3

Manuel V.c. Vieira
Relationships between minimal unsatisfiable subformulas and semidefinite certificates of infeasibility

Coauthor: Miguel F. Anjos


It is known that if the semidefinite programming (SDP) relaxation of a satistifiability (SAT) instance is infeasible, then the SAT instance is unsatisfiable. Moreover, when the SDP relaxation is infeasible, we can exhibit a proof in the form of an SDP certificate of infeasibility. We can extract information about the SAT instance from the SDP certificate of infeasibility. In particular, we show how the SDP certificate of infeasibility can provide information about minimal unsatisfiable sub-formulas.


  payday loans direct . This pill gives a hand to thousands who suffer from erectile dysfunction. People who take Viagra Super Active can forget about their impotence and have a normal intimate life.