Combinatorics and Geometry of Linear Optimization
Responsable et prÃ©sident:
Antoine Deza (McMaster University)
[
PDF]
 ANTOINE DEZA, McMaster University
Combinatorial, computational, and geometric approaches to the colourful simplicial depth [PDF] [SLIDES]

The colourful simplicial depth conjecture states that any point in the convex hull of each of $d+1$ sets, or colours, of $d+1$ points in general position in dimension $d$ is contained in at least $d^2+1$ simplices with one vertex from each set. We verify the conjecture in dimension 4 and provide a new lower bound in higher dimensions improving earlier results of BÃ¡rÃ¡ny and MatouÅ¡ek (2007), Stephen and Thomas (2008), and Deza, Stephen, and Xie (2011). Based on a joint work with FrÃ©dÃ©ric Meunier (ENPC Paris) and Pauline Sarrabezolles (ENPC Paris).
 NATHAN KRISLOCK, University of British Columbia
BiqCrunch: a semidefinitebased solver for binary quadratic problems [PDF] [SLIDES]

BiqCrunch is a new branchandbound solver for finding exact solutions of any 01 quadratic problem, such as MaxCut, Max$k$cluster, and Maxindependent set. The bounds are based on a regularized semidefinite relaxation and are efficiently computable using eigenvalue decomposition and a quasiNewton optimization method. The resulting semidefinite bounding procedure gives us a competitive branchandbound algorithm for solving many such combinatorial optimization problems to optimality.
 FRAUKE LIERS, FAU ErlangenNuremberg
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 costoptimal 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 preinstalled 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 subformulas.
 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.