Continuous Approaches to the Unconstrained Binary Quadratic Problems

Two continuous approaches Continuous approaches to discrete problems over sets inscribed into a sphere are presented. They use an analytic description of the sets and a convex extension of objective functions from the sets onto Euclidean space. The first approach is the Branch and Bound Polyhedral-Spherical Method (B&BPSM) for “two-layer sets”, which utilizes the sets representation as an intersection of a polyhedron Polyhedron with a sphere and the global minimizers on a sphere. The concept of a functional representation of a discrete set Functional representation of a discrete set as an intersection of surfaces is introduced and used, for constructing penalty functions, in the second approach – the Penalty Method based on Functional Representations (FRPM). The methods are applied to the Unconstrained Binary Quadratic Problem Unconstrained binary quadratic problem . For the purpose, the representation of the binary set as a “touching set” of smooth surfaces Touching set of smooth surfaces is derived.