Roof duality for polynomial 0-1 optimization
The paper deals with the so-called polynomial 0-1 optimization problem \[ \max_{x\in \{0,1\}^ n}\sum^{K}_{k=1}a_ k\prod_{i\in S(k)}x_ i \] where \(x=(x_ 1,...,x_ n)\), S(k)\(\subseteq \{1,...,n\}\), \(q_ 1,...,q_ k\) are fixed reals, S(1),...,S(k) fixed. First, it is shown that with a transformation to complemented variables one can assume \(q_ i>0\) except for the linear term. The paper offers a corresponding continuous LP problem which can be used to fix some variables to their optimal value in the following way: if some solution coordinate is positive for the LP, then the corresponding coordinate x equals 1 in the solution; for negative LP solution coordinates we have 0 in the original problem. The paper describes also the situation when one cannot fix any variable using this method.
- A Selection Problem of Shared Fixed Costs and Network Flows
- A Strongly Convergent Primal Simplex Algorithm for Generalized Networks
- Generalized upper bounding techniques
- scientific article; zbMATH DE number 3848971 (Why is no real title available?)
- scientific article; zbMATH DE number 3791942 (Why is no real title available?)
- 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
- 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 lower bound for a constrained quadratic \(0\)-\(1\) minimization problem
- Unconstrained 0-1 optimization and Lagrangean relaxation
- Distributionally robust mixed integer linear programs: persistency models with applications
- Roof duality, complementation and persistency in quadratic 0-1 optimization
- Generalized roof duality and bisubmodular functions
- scientific article; zbMATH DE number 4114373 (Why is no real title available?)
- Concave extensions for nonlinear 0-1 maximization problems
- Pseudo-Boolean optimization
- Generalized roof duality
- Probabilistic bounds and algorithms for the maximum satisfiability problem
- 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)
This page was built for publication: Roof duality for polynomial 0-1 optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3770279)