The basic algorithm for pseudo-Boolean programming revisited
From MaRDI portal
Publication:2277139
DOI10.1016/0166-218X(90)90142-YzbMath0724.90040MaRDI QIDQ2277139
Brigitte Jaumard, Pierre Hansen, Yves Cramer
Publication date: 1990
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Abstract computational complexity for mathematical programming problems (90C60) Nonlinear programming (90C30) Boolean programming (90C09) Computational methods for problems pertaining to operations research and mathematical programming (90-08)
Related Items
The struction algorithm for the maximum stable set problem revisited, Generalization of Barahona's algorithm for cases of integer non-linear programming with box constraints, Polynomially solvable cases of the constant rank unconstrained quadratic 0-1 programming problem, Complexity and Polynomially Solvable Special Cases of QUBO, A lower bound for a constrained quadratic \(0\)-\(1\) minimization problem, Cluster analysis and mathematical programming, On optimization problems in acyclic hypergraphs, Efficient linear reformulations for binary polynomial optimization problems, On the complexity of binary polynomial optimization over acyclic hypergraphs, An exact solution method for unconstrained quadratic 0--1 programming: a geometric approach, Struction revisited, Optimization and probabilistic satisfiability on nested and co-nested formulas, A Clustering Approach to Constrained Binary Matrix Factorization, The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds, Nonsmooth cryptanalysis, with an application to the stream cipher MICKEY, Concave extensions for nonlinear 0-1 maximization problems, Pseudo-Boolean optimization, Computational complexity of norm-maximization, Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method, Simulated annealing for the unconstrained quadratic pseudo-Boolean function, Mixed-integer column generation algorithms and the probabilistic maximum satisfiability problem, Probabilistic satisfiability with imprecise probabilities
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
- Unimodular functions
- A solvable case of quadratic 0-1 programming
- Probabilistic satisfiability
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Nonlinear 0–1 programming: I. Linearization techniques
- Nonlinear 0–1 programming: II. Dominance relations and algorithms
- Graph minors. II. Algorithmic aspects of tree-width
- Complexity of Finding Embeddings in a k-Tree
- Technical Note—Generalized Covering Relaxation for 0-1 Programs
- A Balasian-Based Algorithm for Zero-One Polynomial Programming
- Further Improvements in the Polynomial Zero-One Algorithm
