Optimization Online


Higher Order Maximum Persistency and Comparison Theorems

Alexander Shekhovtsov (shekhovtsov***at***icg.tugraz.at)

Abstract: 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 the optimal discrete solution. Those which do are called persistent. Such persistent variables define a part of a globally optimal solution. Once identified, they can be excluded from the problem, reducing its size. To any polyhedral relaxation we associate a sufficient condition proving persistency of a subset of variables. We set up a specially constructed linear program which determines the set of persistent variables maximal with respect to the relaxation. The condition improves as the relaxation is tightened and possesses all its invariances. The proposed framework explains a variety of existing methods originating from different areas of research and based on different principles. A theoretical comparison is established that relates these methods to the standard linear relaxation and proves that the proposed technique identifies same or larger set of persistent variables.

Keywords: Persistency, partial optimality, LP relaxation, discrete optimization, WCSP, graphical models

Category 1: Integer Programming (0-1 Programming )

Category 2: Global Optimization (Theory )

Category 3: Combinatorial Optimization (Polyhedra )

Citation: preprint, submitted to CVIU SI:Inference &Learning of GM, developed at Institute for Computer Graphics and Vision, Graz Univeristy of Technology, Oct. 2014

Download: [PDF]

Entry Submitted: 10/15/2014
Entry Accepted: 10/16/2014
Entry Last Modified: 05/05/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society