BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Date iCal//NONSGML kigkonsult.se iCalcreator 2.20.2//
METHOD:PUBLISH
X-WR-CALNAME;VALUE=TEXT:Eventi DIAG
BEGIN:VTIMEZONE
TZID:Europe/Paris
BEGIN:STANDARD
DTSTART:20221030T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
END:STANDARD
BEGIN:DAYLIGHT
DTSTART:20230326T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:calendar.24976.field_data.0@www.diag.uniroma1.it
DTSTAMP:20231001T091945Z
CREATED:20230123T085438Z
DESCRIPTION:AbstractEfficient solution approaches for quadratic unconstrain
ed binary optimization (QUBO) problems are of great interest for several r
easons. Firstly\, the well-known maximum-cut problem admits a natural form
ulation as a QUBO problem. Secondly\, other optimization problems like the
graph bisection problem\, the maximum independent set problem\, linearly
constrained binary quadratic problems\, and many more can be reformulated
as an instance of QUBO. Since linear programming based approaches perform
poorly on dense problem instances\, all state-of-the-art approaches involv
e semidefinite relaxations in this case. In this talk\, we present an exac
t solver for QUBO problems based on semidefinite programming. It uses the
so-called mixing method\, a low-rank coordinate descent method\, as its ma
in tool to tackle the occurring semidefinite programs. We discuss some new
ideas implemented in the solver and provide numerical results showing tha
t it outperforms the other existing semidefinite approaches for medium-siz
ed instances. Moreover\, it was a paradigm in recent years to tighten semi
definite relaxations by considering more and more valid inequalities. In c
ontrast to this\, we demonstrate that weaker relaxations can still be comp
etitive when used in a branch-and-bound approach.
DTSTART;TZID=Europe/Paris:20230126T103000
DTEND;TZID=Europe/Paris:20230126T103000
LAST-MODIFIED:20230123T092500Z
LOCATION:Aula A4 Diag
SUMMARY:An Exact Solver for QUBO Problems using the Mixing Method - Jan Sch
widessen
URL;TYPE=URI:https://www.diag.uniroma1.it/node/24976
END:VEVENT
END:VCALENDAR