Linearization Techniques for unconstrained 0/1 Quadratic problems

We address the problem of optimizing a polynomial with real coefficients over binary variables. We show that a complete polyhedral description of the linearization of such a problem can be derived in a simple way from the polyhedral description of the linearization of some quadratic optimization problem. The number of variables in the latter linearization is only slightly larger than in the former. If polynomial constraints are present in the original problem, then their linearized counterparts carry over to the linearized quadratic problem unchanged. If the original problem formulation does not contain any constraints, we obtain a reduction to unconstrained quadratic zero-one optimization, which is equivalent to the well-studied max-cut problem. The separation problem for general unconstrained polynomial zero-one optimization thus reduces to the separation problem for the cut polytope. This allows us to transfer the entire knowledge gained for the latter polytope by intensive research and, in particular, the sophisticated separation techniques that have been developed. We report preliminary experimental results obtained with a straightforward implementation of this approach.We address the problem of optimizing a polynomial with real coefficients over binary variables. We show that a complete polyhedral description of the linearization of such a problem can be derived in a simple way from the polyhedral description of the linearization of some quadratic optimization problem. The number of variables in the latter linearization is only slightly larger than in the former. If polynomial constraints are present in the original problem, then their linearized counterparts carry over to the linearized quadratic problem unchanged. If the original problem formulation does not contain any constraints, we obtain a reduction to unconstrained quadratic zero-one optimization, which is equivalent to the well-studied max-cut problem. The separation problem for general unconstrained polynomial zero-one optimization thus reduces to the separation problem for the cut polytope. This allows us to transfer the entire knowledge gained for the latter polytope by intensive research and, in particular, the sophisticated separation techniques that have been developed. We report preliminary experimental results obtained with a straightforward implementation of this approach.

SIAM Journal on OptimizationDec 21, 200747 citations

A polynomial case of unconstrained zero-one quadratic optimization

Kim Allemand, Komei Fukuda, Thomas M. Liebling +1 more

Mathematical ProgrammingOct 1, 200176 citations

On the Effects of Smoothing Rugged Landscape by Different Toy Problems: A Case Study on UBQP

Wei Wang, Jialong Shi, Jianyong Sun +3 more

The hardness of the Unconstrained Binary Quadratic Program (UBQP) problem is due its rugged landscape. Various algorithms have been proposed for UBQP, including the Landscape Smoothing Iterated Local Search (LSILS). Different from other UBQP algorithms, LSILS tries to smooth the rugged landscape by building a convex combination of the original UBQP and a toy UBQP. In this paper, our study further investigates the impact of smoothing rugged landscapes using different toy UBQP problems, including a toy UBQP with matrix $\hat{\boldsymbol{Q}}^{1}$ (construct by “ $+/-1$ ‘), a toy UBQP with matrix $\hat{\boldsymbol{Q}}^{2}$ (construct by “ $+/-\mathrm{i}$ ’) and a toy UBQP with matrix $\hat{\boldsymbol{Q}}^{3}$ (construct randomly). We first assess the landscape flatness of the three toy UBQPs. Subsequently, we test the efficiency of LSILS with different toy UBQPs. Results reveal that the toy UBQP with $\hat{\boldsymbol{Q}}^{1}$ (construct by “ $+/-1$ ”) exhibits the flattest landscape among the three, while the toy UBQP with $\hat{Q}^{3}$ (construct randomly) presents the most non-flat landscape. Notably, LSILS using the toy UBQP with $\hat{\boldsymbol{Q}}^{2}$ (construct by “ $+/\cdot \mathbf{i})$ emerges as the most effective, while $\hat{\boldsymbol{Q}}^{3}$ (construct randomly) has the poorest result. These findings contribute to a detailed understanding of landscape smoothing techniques in optimizing UBQP.The hardness of the Unconstrained Binary Quadratic Program (UBQP) problem is due its rugged landscape. Various algorithms have been proposed for UBQP, including the Landscape Smoothing Iterated Local Search (LSILS). Different from other UBQP algorithms, LSILS tries to smooth the rugged landscape by building a convex combination of the original UBQP and a toy UBQP. In this paper, our study further investigates the impact of smoothing rugged landscapes using different toy UBQP problems, including a toy UBQP with matrix$\hat{\boldsymbol{Q}}^{1}$(construct by “$+/-1$‘), a toy UBQP with matrix$\hat{\boldsymbol{Q}}^{2}$(construct by “$+/-\mathrm{i}$’) and a toy UBQP with matrix$\hat{\boldsymbol{Q}}^{3}$(construct randomly). We first assess the landscape flatness of the three toy UBQPs. Subsequently, we test the efficiency of LSILS with different toy UBQPs. Results reveal that the toy UBQP with$\hat{\boldsymbol{Q}}^{1}$(construct by “$+/-1$”) exhibits the flattest landscape among the three, while the toy UBQP with$\hat{Q}^{3}$(construct randomly) presents the most non-flat landscape. Notably, LSILS using the toy UBQP with$\hat{\boldsymbol{Q}}^{2}$(construct by “$+/\cdot \mathbf{i})$emerges as the most effective, while$\hat{\boldsymbol{Q}}^{3}$(construct randomly) has the poorest result. These findings contribute to a detailed understanding of landscape smoothing techniques in optimizing UBQP.

arXiv:2407.19676IEEE Congress on Evolutionary Computation (CEC)Jun 30, 20240 citations

\hat{\boldsymbol{Q}}^{1}

(construct by “

+/-1

‘), a toy UBQP with matrix

\hat{\boldsymbol{Q}}^{2}

(construct by “

+/-\mathrm{i}

’) and a toy UBQP with matrix

\hat{\boldsymbol{Q}}^{3}

(construct randomly). We first assess the landscape flatness of the three toy UBQPs. Subsequently, we test the efficiency of LSILS with different toy UBQPs. Results reveal that the toy UBQP with

\hat{\boldsymbol{Q}}^{1}

(construct by “

+/-1

”) exhibits the flattest landscape among the three, while the toy UBQP with

\hat{Q}^{3}

(construct randomly) presents the most non-flat landscape. Notably, LSILS using the toy UBQP with

\hat{\boldsymbol{Q}}^{2}

(construct by “

+/\cdot \mathbf{i})

emerges as the most effective, while

\hat{\boldsymbol{Q}}^{3}

(construct randomly) has the poorest result. These findings contribute to a detailed understanding of landscape smoothing techniques in optimizing UBQP.