Roof duality, complementation and persistency in quadratic 0–1 optimization

DOI10.1007/BF02612354zbMath0574.90066OpenAlexW2006293258MaRDI QIDQ3693267

Pierre Hansen, Peter L. Hammer, Bruno Simeone

Publication date: 1984

Published in: Mathematical Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02612354

zbMATH Keywords

linearization duality graphs discrete optimization bipartite maximum flow problem quadratic pseudoboolean function weighted stability problem

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Nonlinear programming (90C30) Boolean programming (90C09)

Related Items

A solvable case of quadratic 0-1 programming, Quadratic functions with exponential number of local maxima, Persistency of Linear Programming Relaxations for the Stable Set Problem, Distributionally robust mixed integer linear programs: persistency models with applications, Minimization of a quadratic pseudo-Boolean function, Introduction to QUBO, Autarkies and Persistencies for QUBO, Mathematical Programming Models and Exact Algorithms, Penalty formulation for zero-one nonlinear programming, A simultaneous lifting strategy for identifying new classes of facets for the Boolean quadric polytope, A linear programming approach to reasoning about probabilities, A lower bound for a constrained quadratic \(0\)-\(1\) minimization problem, Computational aspects of a branch and bound algorithm for quadratic zero- one programming, An extension of the König-Egerváry property to node-weighted bidirected graphs, A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming, Cluster analysis and mathematical programming, Approximations of pseudo-Boolean functions; applications to game theory, Using a mixed integer quadratic programming solver for the unconstrained quadratic \(0-1\) problem, The Boolean quadratic polytope: Some characteristics, facets and relatives, Experiments in quadratic 0-1 programming, Boosting quantum annealer performance via sample persistence, Some thoughts on combinatorial optimisation, Thermostatistical persistency: A powerful improving concept for simulated annealing algorithms, Efficient joint object matching via linear programming, Faster exact solution of sparse maxcut and QUBO problems, Roof duality for polynomial 0–1 optimization, Generalized roof duality and bisubmodular functions, A polyhedral study of lifted multicuts, A framework for certified Boolean branch-and-bound optimization, An exact solution method for unconstrained quadratic 0--1 programming: a geometric approach, Upper-bounds for quadratic 0-1 maximization, Probabilistic bounds and algorithms for the maximum satisfiability problem, Locating a discrete subtree of minimum variance on trees: new strategies to tackle a very hard problem, Quadratic 0–1 programming: Tightening linear or quadratic convex reformulation by use of relaxations, On the equivalence of paved-duality and standard linearization in nonlinear 0-1 optimization, The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds, MaxSolver: An efficient exact algorithm for (weighted) maximum satisfiability, A polynomial case of convex integer quadratic programming problems with box integer constraints, A network approach for specially structured linear programs arising in 0-1 quadratic optimization, Persistency in quadratic 0-1 optimization, Constrained 0-1 quadratic programming: basic approaches and extensions, A solvable class of quadratic 0-1 programming, A Max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO), Quadratic reformulations of nonlinear binary optimization problems, A pseudo-Boolean consensus approach to nonlinear 0-1 optimization, Concave extensions for nonlinear 0-1 maximization problems, Optimal design of a distributed network with a two-level hierarchical structure, Combinatorial optimization of the discretized multiphase Mumford-Shah functional, Efficient branch-and-bound algorithms for weighted MAX-2-SAT, Best reduction of the quadratic semi-assignment problem, Analyzing quadratic unconstrained binary optimization problems via multicommodity flows, Pseudo-Boolean optimization, A branch and bound algorithm for the maximum clique problem, Soft arc consistency revisited, Persistency in combinatorial optimization problems on matroids, Block linear majorants in quadratic 0--1 optimization, Upper bounds and exact algorithms for \(p\)-dispersion problems, Generalized roof duality, Unconstrained 0-1 optimization and Lagrangean relaxation, Multi-target tracking by online learning a CRF model of appearance and motion patterns, An evolutionary heuristic for quadratic 0-1 programming, Linear programming for the \(0-1\) quadratic knapsack problem, Algorithms for the maximum satisfiability problem, Improved compact linearizations for the unconstrained quadratic 0-1 minimization problem, Optimal cell flipping to minimize channel density in VLSI design and pseudo-Boolean optimization, Ranking in quadratic integer programming problems, Persistency and matroid intersection, Solving quadratic (0,1)-problems by semidefinite programs and cutting planes, An approximate dynamic programming approach to convex quadratic knapsack problems, Simulated annealing for the unconstrained quadratic pseudo-Boolean function, On the equivalence between roof duality and Lagrangian duality for unconstrained \(0\)-\(1\) quadratic programming problems, Maximizing a supermodular pseudoboolean function: A polynomial algorithm for supermodular cubic functions, Efficient global minimization methods for image segmentation models with four regions, Persistency of linear programming relaxations for the stable set problem

Cites Work