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.