NATHAN KRISLOCK, University of British Columbia BiqCrunch: a semidefinite-based solver for binary quadratic problems [PDF] [SLIDES]
BiqCrunch is a new branch-and-bound solver for finding exact solutions of any 0-1 quadratic problem, such as Max-Cut, Max-$k$-cluster, and Max-independent set. The bounds are based on a regularized semidefinite relaxation and are efficiently computable using eigenvalue decomposition and a quasi-Newton optimization method. The resulting semidefinite bounding procedure gives us a competitive branch-and-bound algorithm for solving many such combinatorial optimization problems to optimality.
FRAUKE LIERS, FAU Erlangen-Nuremberg Geometry of Network Design with Certain and Uncertain Demands [PDF] [SLIDES]
Polyhedral insights are presented for a network design problem. The
task consists of determining a cost-optimal dimensioning of the arc
capacities such that a specified list of demand patterns can be routed
through the network. An exact approach using these insights is
developed and evaluated. For some applications,
the instances already contain pre-installed capacities that allow for a
relatively high percentage of the demand to be routed. This makes an
exact approach via iterative graph aggregation feasible.
MANUEL VIEIRA, Universidade Nova de Lisboa Extracting information of unsatisfiable formulas using Semidefinite certificates of infeasibility [PDF]
It is known that if a 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 illustrate how the SDP certificate of infeasibility
can provide information about minimal unsatisfiable sub-formulas.
HENRY WOLKOWICZ, University of Waterloo Taking advantage of Degeneracy and Special Structure in Linear Cone Optimization [PDF] [SLIDES]
The elegant theoretical results for strong duality and strict
complementarity for LP lie behind the success of
current algorithms. However, the theory and preprocessing
for LP can fail for cone programming over
nonpolyhedral cones. Surprisingly, many instances of
SDP problems that arise from relaxations of hard combinatorial problems are
degenerate. Rather than being
a disadvantage, we show that this degeneracy can be exploited if the
problem has some special structure. In
particular, several huge instances of SDP completion problems can be
solved quickly and to extremely high accuracy. In particular, we
illustrate this on the sensor network localization problem.