Roof duality for polynomial 0-1 optimization

From MaRDI portal





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.











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)