Higher Order Maximum Persistency and Comparison Theorems

We address combinatorial problems that can be formulated as minimization of a partially separable function of discrete variables (energy minimization in graphical models, weighted constraint satisfaction, pseudo-Boolean optimization, 0-1 polynomial programming). For polyhedral relaxations of such problems it is generally not true that variables integer in the relaxed solution will retain the same values in … Read more

Playing with Duality: An Overview of Recent Primal-Dual Approaches for Solving Large-Scale Optimization Problems

Optimization methods are at the core of many problems in signal/image processing, computer vision, and machine learning. For a long time, it has been recognized that looking at the dual of an optimization problem may drastically simplify its solution. Deriving efficient strategies which jointly brings into play the primal and the dual problems is however … Read more

Orbital shrinking

Symmetry plays an important role in optimization. The usual approach to cope with symmetry in discrete optimization is to try to eliminate it by introducing artificial symmetry-breaking conditions into the problem, and/or by using an ad-hoc search strategy. In this paper we argue that symmetry is instead a beneficial feature that we should preserve and … Read more

An Explicit Semidefinite Characterization of Satisfiability for Tseitin Instances

This paper is concerned with the application of semidefinite programming to the satisfiability problem, and in particular with using semidefinite liftings to efficiently obtain proofs of unsatisfiability. We focus on the Tseitin satisfiability instances which are known to be hard for many proof systems. We present an explicit semidefinite programming problem with dimension linear in … Read more

An Improved Algorithm for Biobjective Integer Programs

A parametric algorithm for identifying the Pareto set of a biobjective integer program is proposed. The algorithm is based on the weighted Chebyshev (Tchebycheff) scalarization, and its running time is asymptotically optimal. A number of extensions are described, including: a technique for handling weakly dominated outcomes, a Pareto set approximation scheme, and an interactive version … Read more

An Improved Semidefinite Programming Relaxation for the Satisfiability Problem

The satisfiability (SAT) problem is a central problem in mathematical logic, computing theory, and artificial intelligence. An instance of SAT is specified by a set of boolean variables and a propositional formula in conjunctive normal form. Given such an instance, the SAT problem asks whether there is a truth assignment to the variables such that … Read more

Geometry of Semidefinite Max-Cut Relaxations via Ranks

Semidefinite programming (SDP) relaxations are proving to be a powerful tool for finding tight bounds for hard discrete optimization problems. This is especially true for one of the easier NP-hard problems, the Max-Cut problem (MC). The well-known SDP relaxation for Max-Cut, here denoted SDP1, can be derived by a first lifting into matrix space and … Read more