Pseudo-Boolean optimization

DOI10.1016/S0166-218X(01)00341-9zbMATH Open1076.90032MaRDI QIDQ697569FDOQ697569

Authors: Endre Boros, Peter L. Hammer 

Publication date: 17 September 2002

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Recommendations

• scientific article
• Minimization of a quadratic pseudo-Boolean function
• Pseudo-Boolean optimization with a disjunctive constraint
• scientific article; zbMATH DE number 279605
• A pseudo-Boolean consensus approach to nonlinear 0-1 optimization

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Boolean programming (90C09)

Cites Work

• Quelques utilisations de la STRUCTION. (Some applications of STRUCTION)
• On Some Properties of the Struction of a Graph
• On the equivalence of paved-duality and standard linearization in nonlinear 0-1 optimization
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Cut Approach to the Rectilinear Distance Facility Location Problem
• Title not available (Why is that?)
• Quadratic functions with exponential number of local maxima
• Persistency in quadratic 0-1 optimization
• Optimal cell flipping to minimize channel density in VLSI design and pseudo-Boolean optimization
• Maximum cuts: Improvements and local algorithmic analogues of the Edwards-Erdős inequality
• Boolean query optimization and the 0-1 hyperbolic sum problem
• Covering non-uniform hypergraphs
• Valid inequalities and facets for a hypergraph model of the nonlinear knapsack and the FMS part selection problems
• Maximum renamable Horn sub-CNFs
• Unconstrained 0-1 optimization and Lagrangean relaxation
• Nonlinear 0–1 programming: II. Dominance relations and algorithms
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Ein effektiver Branch and Bound-Algorithmus für Boolesche quadratische Optimierungsprobleme
• Multiple optima in local search
• Title not available (Why is that?)
• Quasimonotone Boolean Functions and Bistellar Graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Pseudo-Boolean Solutions to Multidimensional Location Problems
• Title not available (Why is that?)
• On the integer-valued variables in the linear vertex packing problem
• Optimal Test Generation in Combinational Networks by Pseudo-Boolean Programming
• Title not available (Why is that?)
• Low order polynomial bounds on the expected performance of local improvement algorithms
• Bimatroidal independence systems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Capital Expenditure Programming and Some Alternative Approaches to Risk
• (0, 1) hyperbolic programming problems
• More characterizations of triangulated graphs
• Title not available (Why is that?)
• Optimization by simulated annealing
• Title not available (Why is that?)
• Title not available (Why is that?)
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Title not available (Why is that?)
• Approximation algorithms for combinatorial problems
• Future paths for integer programming and links to artificial intelligence
• Title not available (Why is that?)
• Optimization, approximation, and complexity classes
• Minimization of ordered, symmetric half-products
• New results on the completion time variance minimization
• Minimization of half-products
• Tabu Search—Part I
• Title not available (Why is that?)
• Neural networks and physical systems with emergent collective computational abilities.
• Algorithms for minclique scheduling problems
• The ellipsoid method and its consequences in combinatorial optimization
• Title not available (Why is that?)
• A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Interactive proofs and the hardness of approximating cliques
• Gadgets, Approximation, and Linear Programming
• Technical Note—Converting the 0-1 Polynomial Programming Problem to a 0-1 Linear Program
• The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds
• Exact ground states of Ising spin glasses: new experimental results with a branch-and-cut algorithm
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• Vertex packings: Structural properties and algorithms
• On the cut polytope
• Title not available (Why is that?)
• Quadratic Binary Programming with Application to Capital-Budgeting Problems
• Probabilistic bounds and algorithms for the maximum satisfiability problem
• How easy is local search?
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• An analysis of approximations for maximizing submodular set functions—I
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Set Partitioning: A survey
• Title not available (Why is that?)
• On the Set-Covering Problem
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• Title not available (Why is that?)
• Cluster Analysis and Mathematical Programming
• Solving satisfiability in less than \(2^ n\) steps
• Roof duality, complementation and persistency in quadratic 0–1 optimization
• Roof duality for polynomial 0–1 optimization
• New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Concave extensions for nonlinear 0-1 maximization problems
• The quadratic assignment problem
• L’algebre de Boole et ses applications en recherche operationnelle
• Title not available (Why is that?)
• Facets for the cut cone. I
• Facets for the cut cone. II: Clique-web inequalities
• Title not available (Why is that?)
• The cut polytope and the Boolean quadric polytope
• Some Network Flow Problems Solved with Pseudo-Boolean Programming
• Title not available (Why is that?)
• Minimum cuts and related problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Methods of Nonlinear 0-1 Programming
• A Selection Problem of Shared Fixed Costs and Network Flows
• Complexity of Partial Satisfaction
• On the Approximation of Maximum Satisfiability
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• Facets of the Bipartite Subgraph Polytope
• Cut-Polytopes, Boolean Quadric Polytopes and Nonnegative Quadratic Pseudo-Boolean Functions
• A solvable case of quadratic 0-1 programming
• One-pass heuristics for large-scale unconstrained binary quadratic problems
• Applications of pseudo-Boolean methods to economic problems
• The basic algorithm for pseudo-Boolean programming revisited
• Approximations of pseudo-Boolean functions; applications to game theory
• Further Reduction of Zero-One Polynomial Programming Problems to Zero-One linear Programming Problems
• On the equivalence between roof duality and Lagrangian duality for unconstrained \(0\)-\(1\) quadratic programming problems
• Chvátal Cuts and Odd Cycle Inequalities in Quadratic 0–1 Optimization
• The struction algorithm for the maximum stable set problem revisited
• Modeling Brain Function
• Unimodular functions
• AN ALGORITHM FOR MAXIMUM LIKELIHOOD RANKING AND SLATER'S i FROM PAIRED COMPARISONS
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Vertices Belonging to All or to No Maximum Stable Sets of a Graph
• Maximizing a supermodular pseudoboolean function: A polynomial algorithm for supermodular cubic functions
• On the supermodular knapsack problem
• Strong unimodularity for matrices and hypergraphs
• Recognition problems for special classes of polynomials in 0-1 variables
• The struction of a graph: Application to CN-free graphs
• On the use of Boolean methods for the computation of the stability number
• Polynomially solvable cases for the maximum stable set problem
• Title not available (Why is that?)
• Stability in CAN-free graphs
• Upper-bounds for quadratic 0-1 maximization
• On the Maximization of a Pseudo-Boolean Function
• Hill Climbing with Multiple Local Optima
• Average Performance of Heuristics for Satisfiability

Cited In (only showing first 100 items - show all)

• A Semi-Tensor Product Approach to Pseudo-Boolean Functions with Application to Boolean Control Networks
• On the strength of recursive McCormick relaxations for binary polynomial optimization
• Optimal testing and repairing a failed series system
• A Lagrangian decomposition approach to computing feasible solutions for quadratic binary programs
• A framework for certified Boolean branch-and-bound optimization
• Quadratization of symmetric pseudo-Boolean functions
• Efficient branch-and-bound algorithms for weighted MAX-2-SAT
• Exact and approximate discrete optimization algorithms for finding useful disjunctions of categorical predicates in data analysis
• New approaches for optimizing over the semimetric polytope
• A new separation algorithm for the Boolean quadric and cut polytopes
• Generalized roof duality and bisubmodular functions
• An exact solution method for unconstrained quadratic 0--1 programming: a geometric approach
• Optimizing adiabatic quantum program compilation using a graph-theoretic framework
• Quadratic reformulations of nonlinear binary optimization problems
• Minor-embedding in adiabatic quantum computation. II: Minor-universal graph design
• Exact solution approaches for bilevel assignment problems
• An unconstrained quadratic binary programming approach to the vertex coloring problem
• A linearization framework for unconstrained quadratic (0-1) problems
• The unconstrained binary quadratic programming problem: a survey
• On finite potential games
• Minor-embedding in adiabatic quantum computation. I: The parameter setting problem
• Hypercontractive inequality for pseudo-Boolean functions of bounded Fourier width
• PBLib – A Library for Encoding Pseudo-Boolean Constraints into CNF
• Global optimality conditions for quadratic \(0-1\) optimization problems
• The complexity of approximating conservative counting CSPs
• Boolean-controlled systems via receding horizon and linear programing
• The expressive power of binary submodular functions
• A global continuation algorithm for solving binary quadratic programming problems
• Minimizing a linear fractional function subject to a system of sup-\(T\) equations with a continuous Archimedean triangular norm
• Differential approximation schemes for half-product related functions and their scheduling applications
• Approximability issues for unconstrained and constrained maximization of half-product related functions
• From matchings to independent sets
• Branch-and-mincut: global optimization for image segmentation with high-level priors
• Facet-inducing web and antiweb inequalities for the graph coloring polytope
• Stability preserving transformations of graphs
• Improved compact linearizations for the unconstrained quadratic 0-1 minimization problem
• Multi-period maintenance scheduling of tree networks with minimum flow disruption
• Exact solution approach for a class of nonlinear bilevel knapsack problems
• Quadratic convex reformulations for quadratic 0-1 programming
• Cuts in undirected graphs. I
• Fast approximate energy minimization with label costs
• Adiabatic quantum programming: minor embedding with hard faults
• A polyhedral study of lifted multicuts
• Using \(xQx\) to model and solve the uncapacitated task allocation problem
• Satisfying more than half of a system of linear equations over GF(2): a multivariate approach
• A heuristic for Boolean optimization problems
• Genetic algorithm-based multi-criteria project portfolio selection
• The complexity of soft constraint satisfaction
• On complexity of unconstrained hyperbolic 0--1 programming problems
• A case study in programming a quantum annealer for hard operational planning problems
• Modularity-based decompositions for valued CSP
• Using a mixed integer quadratic programming solver for the unconstrained quadratic \(0-1\) problem
• A Max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO)
• Soft arc consistency revisited
• Data aggregation for \(p\)-median problems
• Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications
• On total variation minimization and surface evolution using parametric maximum flows
• Norm bounds and underestimators for unconstrained polynomial integer minimization
• On characterization of maximal independent sets via quadratic optimization
• The potential of quantum annealing for rapid solution structure identification
• Solving Multi-objective Pseudo-Boolean Problems
• New algorithms for convex cost tension problem with application to computer vision
• Efficient minimization of higher order submodular functions using monotonic Boolean functions
• A new approach for modeling and solving set packing problems
• Multiagent resource allocation in \(k\)-additive domains: preference representation and complexity
• Classes of submodular constraints expressible by graph cuts
• Estimating arrival rate of nonhomogeneous Poisson processes with semidefinite programming
• Resource efficient gadgets for compiling adiabatic quantum optimization problems
• Mathematical optimization ideas for biodiversity conservation
• The bipartite unconstrained 0-1 quadratic programming problem: polynomially solvable cases
• Generalized roof duality
• Minimization of locally defined submodular functions by optimal soft arc consistency
• Combinatorial structure and randomized subexponential algorithms for infinite games
• The Power of Sherali--Adams Relaxations for General-Valued CSPs
• A pseudo-Boolean consensus approach to nonlinear 0-1 optimization
• A note on representations of linear inequalities in non-convex mixed-integer quadratic programs
• Quadratic and higher-order unconstrained binary optimization of railway rescheduling for quantum computing
• Hard combinatorial problems and minor embeddings on lattice graphs
• The expressive power of valued constraints: Hierarchies and collapses
• Solving larger maximum clique problems using parallel quantum annealing
• The bipartite Boolean quadric polytope
• Uniqueness in quadratic and hyperbolic \(0-1\) programming problems
• Optimal quadratic reformulations of fourth degree pseudo-Boolean functions
• The Multilinear Polytope for Acyclic Hypergraphs
• The effects of the problem Hamiltonian parameters on the minimum spectral gap in adiabatic quantum optimization
• Solving a cut problem in bipartite graphs by linear programming: application to a forest management problem
• Quantum bridge analytics. I: A tutorial on formulating and using QUBO models
• Subset-conjunctive rules for breast cancer diagnosis
• The fundamental theorem of linear programming: extensions and applications
• On the complexity of binary polynomial optimization over acyclic hypergraphs
• On some variants of the merging variables based \((1+1)\)-evolutionary algorithm with application to MaxSAT problem
• Weighted model counting without parameter variables
• Minimizing energies with hierarchical costs
• Fractional 0-1 programs: links between mixed-integer linear and conic quadratic formulations
• Fractional 0-1 programming: applications and algorithms
• Quantum bridge analytics. I: A tutorial on formulating and using QUBO models
• A tight lower bound for a special case of quadratic 0-1 programming
• Efficient linear reformulations for binary polynomial optimization problems
• Finding Effective SAT Partitionings Via Black-Box Optimization
• On the complexity and approximation of the maximum expected value all-or-nothing subset

This page was built for publication: Pseudo-Boolean optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q697569)