Roof duality for polynomial 0–1 optimization

DOI10.1007/BF02591742zbMath0632.90044OpenAlexW2085099404MaRDI QIDQ3770279

No author found.

Publication date: 1987

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

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

zbMATH Keywords

linearizationdualitydiscrete optimizationpolynomial 0-1 optimization

Mathematics Subject Classification ID

Boolean programming (90C09)

Related Items (12)

Distributionally robust mixed integer linear programs: persistency models with applications ⋮ A lower bound for a constrained quadratic \(0\)-\(1\) minimization problem ⋮ Generalized roof duality and bisubmodular functions ⋮ Probabilistic bounds and algorithms for the maximum satisfiability problem ⋮ 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 ⋮ A network approach for specially structured linear programs arising in 0-1 quadratic optimization ⋮ A Max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO) ⋮ Concave extensions for nonlinear 0-1 maximization problems ⋮ Pseudo-Boolean optimization ⋮ Generalized roof duality ⋮ Unconstrained 0-1 optimization and Lagrangean relaxation

Cites Work

• Unnamed Item
• Unnamed Item
• Generalized upper bounding techniques
• Nonlinear 0–1 programming: I. Linearization techniques
• Nonlinear 0–1 programming: II. Dominance relations and algorithms
• Roof duality, complementation and persistency in quadratic 0–1 optimization
• A Strongly Convergent Primal Simplex Algorithm for Generalized Networks
• A Selection Problem of Shared Fixed Costs and Network Flows

This page was built for publication: Roof duality for polynomial 0–1 optimization