HEC Montréal, Canada, May 2 - 4, 2011

2011 Optimization Days

HEC Montréal, Canada, 2 — 4 May 2011

Schedule Authors My Schedule

MB2 Relaxations semi-définies et convexes pour l'optimisation discrète / Semidefinite and Convex Relaxations for Discrete Optimization Problems

May 2, 2011 03:30 PM – 05:10 PM

Location: Béton Grilli

Chaired by Miguel F. Anjos

4 Presentations

  • 03:30 PM - 03:55 PM

    Nonconvex Quadratic Programming With Box Constraints

    • Samuel Burer, presenter, University of Iowa
    • Adam Letchford, University of Lancaster

    Nonconvex quadratic programming with box constraints is a fundamental continuous global optimization problem, which also appears as a substructure within many other problems. We study a certain non-polyhedral convexification of this problem, detail some fundamental results, and describe several classes of strong cuts. We also show a close relationship to the Boolean quadric polytope, an important polytope in the field of polyhedral combinatorics.

  • 03:55 PM - 04:20 PM

    Direct Representation of the Resolution Rule Via Semi-Definite Programming

    • Miguel F. Anjos, GERAD, Polytechnique Montréal
    • Manuel Vieira, presenter, Universidade Nova de Lisboa

    We use the language of semidefinite programming (SDP) relaxations to describe the resolution rule process for determining whether a satisfiability (SAT) formula is satisfiable. More specifically, we represent one step of resolution using SDP. We also comment on how this may lead to new insights on the relationships between SDP relaxations and SAT.

  • 04:20 PM - 04:45 PM

    Convex Relaxation for the Clique and Clustering Problems

    • Brendan Ames, presenter, University of Waterloo
    • Stephen Vavasis, University of Waterloo

    Given a data set with known pairwise similarities, partitioning the data into disjoint clusters is equivalent to partitioning a particular graph into disjoint cliques. We consider the related problem of identifying the maximum subgraph comprised of k disjoint cliques of a given graph. This problem can be formulated as a semidefinite program with an additional rank constraint. This problem is NP-hard yet we show that it can be solved exactly for certain input graphs by relaxing to a convex optimization problem by replacing rank with the nuclear norm. Specifically, the convex relaxation is exact in the case that the input graph consists of a collection of k disjoint cliques and a moderate amount of additional edges and nodes.

  • 04:45 PM - 05:10 PM

    An Iterative Scheme for Valid Polynomial Inequality Generation in Binary Polynomial Programming

    • Miguel F. Anjos, presenter, GERAD, Polytechnique Montréal
    • Bissan Ghaddar, University of Waterloo
    • Juan C. Vera, Tilburg University

    We propose an iterative scheme that improves the semidefinite relaxations without incurring exponential growth in their size by generating valid polynomial inequalities. For binary polynomial programs, we prove under mild conditions that the proposed scheme converges to the global optimal solution. We also present computational comparisons to other methods in the literature.