CanaDAM 2013 Memorial University of Newfoundland, June 10 - 13, 2013 www.cms.math.ca//2013

Combinatorics and Geometry of Linear Optimization
Organizer and Chair: Antoine Deza (McMaster University)
[PDF]

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 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.