3 Presentations

• 
  10:30 AM - 10:55 AM

  Two stage architecture optimization for differentially private Kalman filtering

  • Kwassi Holali Degue, presenter, Ecole Polytechnique de Montreal
  • Jérôme Le Ny, GERAD - Polytechnique Montréal

  The problem of Kalman filtering under privacy constraints is addressed. This problem occurs in scenarios where a data aggregator aims at releasing publicly, in real-time, a combination of privacy-sensitive signals that originate from a linear Gaussian model. An optimum differentially private mechanism that is computed using semidefinite programming is proposed.

• 
  10:55 AM - 11:20 AM

  Improving the linear relaxation of maximum k-cut with semidefinite-based constraints

  • Vilmar Jefte Rodrigues De Sousa, presenter, Polytechnique Montréal
  • Miguel F. Anjos, GERAD, Polytechnique Montréal
  • Sébastien Le Digabel, GERAD, Polytechnique Montréal

  We consider the maximum k-cut problem that consists in partitioning the vertex set of a graph into k subsets such that the sum of the weights of edges joining vertices in different subsets is maximized. The associated semidefinite programming (SDP) relaxation is known to give strong bounds but it suffers from high CPU times. We deploy a cutting plane algorithm that exploits the early termination of an interior-point method, and we study the performance of SDP and linear programming (LP) relaxations for a variety of values of k and of types of instances. The LP relaxation is strengthened using combinatorial facet-defining inequalities as well as SDP-based constraints. Our computational results suggest that the LP approach, especially with the addition of SDP-based constraints, outperforms the SDP relaxations for graphs with positive weights edges and k larger or equal to 7.

• 
  11:20 AM - 11:45 AM

  Bounding procedure improvements for BiqCrunch, a semidefinite-based solver for binary quadratic optimization

  • Nathan Krislock, presenter, Northern Illinois University
  • Ahmed Al-Jilawi, Northern Illinois University

  BiqCrunch is a branch-and-bound solver using semidefinite optimization to compute high-quality bounds for combinatorial optimization problems that can be modeled as binary quadratic problems, such as MaxCut, Max-k-Cluster, Maximum-Independent-Set, Exact Quadratic Knapsack, and the Quadratic Assignment Problem. BiqCrunch does not use an interior-point method for computing its bounds. Instead, an eigenvalue solver and a gradient-based method are used to compute tight bounds. We will discuss new improvements to the bounding procedure of BiqCrunch.