Journées de l'optimisation 2018
HEC Montréal, Québec, Canada, 7 — 9 mai 2018
MA7 Conic optimization and applications
7 mai 2018 10h30 – 12h10
Salle: Groupe Cholette (35)
Présidée par Miguel F. Anjos
3 présentations

10h30  10h55
Two stage architecture optimization for differentially private Kalman filtering
The problem of Kalman filtering under privacy constraints is addressed. This problem occurs in scenarios where a data aggregator aims at releasing publicly, in realtime, a combination of privacysensitive signals that originate from a linear Gaussian model. An optimum differentially private mechanism that is computed using semidefinite programming is proposed.

10h55  11h20
Improving the linear relaxation of maximum kcut with semidefinitebased constraints
We consider the maximum kcut 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 interiorpoint 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 facetdefining inequalities as well as SDPbased constraints. Our computational results suggest that the LP approach, especially with the addition of SDPbased constraints, outperforms the SDP relaxations for graphs with positive weights edges and k larger or equal to 7.

11h20  11h45
Bounding procedure improvements for BiqCrunch, a semidefinitebased solver for binary quadratic optimization
BiqCrunch is a branchandbound solver using semidefinite optimization to compute highquality bounds for combinatorial optimization problems that can be modeled as binary quadratic problems, such as MaxCut, MaxkCluster, MaximumIndependentSet, Exact Quadratic Knapsack, and the Quadratic Assignment Problem. BiqCrunch does not use an interiorpoint method for computing its bounds. Instead, an eigenvalue solver and a gradientbased method are used to compute tight bounds. We will discuss new improvements to the bounding procedure of BiqCrunch.