We propose a heuristic for 0/1 programs based on the recent “joint + marginal” approach of the first author for parametric polynomial optimization. The idea is to first consider the n-variable (x <Subscript>1</Subscript>, . . . , x <Subscript> n </Subscript>) problem as a (n − 1)-variable problem (x <Subscript>2</Subscript>, . . . , x <Subscript> n </Subscript>) with the variable x <Subscript>1</Subscript> being now a parameter taking value in {0, 1}. One then solves a hierarchy of what we call “joint + marginal” semidefinite relaxations whose duals provide a sequence of polynomial approximations <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$${x_1\mapsto J_k(x_1)}$$</EquationSource> </InlineEquation> that converges to the optimal value function J (x <Subscript>1</Subscript>) (as a function of the parameter x <Subscript>1</Subscript>). One considers a fixed index k in the hierarchy and if J <Subscript> k </Subscript> (1) > J <Subscript> k </Subscript> (0) then one decides x <Subscript>1</Subscript> = 1 and x <Subscript>1</Subscript>=0 otherwise. The quality of the approximation depends on how large k can be chosen (in general, for significant size problems, k=1 is the only choice). One iterates the procedure with now a (n − 2)-variable problem with one parameter <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$${x_2 \in \{0, 1\}}$$</EquationSource> </InlineEquation> , etc. Variants are also briefly described as well as some preliminary numerical experiments on the MAXCUT, k-cluster and 0/1 knapsack problems. Copyright Springer Science+Business Media, LLC. 2012
