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

Journées de l'optimisation 2011

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

Horaire Auteurs Mon horaire

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

2 mai 2011 15h30 – 17h10

Salle: Béton Grilli

Présidée par Miguel F. Anjos

4 présentations

  • 15h30 - 15h55

    Nonconvex Quadratic Programming With Box Constraints

    • Samuel Burer, prés., 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.

  • 15h55 - 16h20

    Direct Representation of the Resolution Rule Via Semi-Definite Programming

    • Miguel F. Anjos, GERAD, Polytechnique Montréal
    • Manuel Vieira, prés., 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.

  • 16h20 - 16h45

    Convex Relaxation for the Clique and Clustering Problems

    • Brendan Ames, prés., 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.

  • 16h45 - 17h10

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

    • Miguel F. Anjos, prés., 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.