2018 Optimization Days

HEC Montréal, Québec, Canada, May 7 — 9, 2018

Schedule Authors My Schedule
Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402

MA7 Conic optimization and applications

May 7, 2018 10:30 AM – 12:10 PM

Location: Groupe Cholette (35)

Chaired by Miguel F. Anjos

3 Presentations

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    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.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    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
    • Sebastien Le Digabel, 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.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    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.