  


Higher Order Maximum Persistency and Comparison Theorems
Alexander Shekhovtsov (shekhovtsovicg.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, pseudoBoolean optimization, 01 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 (01 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 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  