Hypersphere Mapper: a nonlinear programming approach to the hypercube embedding problem

A nonlinear programming approach is introduced for solving the hypercube embedding problem. The basic idea of the proposed approach is to approximate the discrete space of an n-dimensional hypercube, i.e. {z:z∈{0,1}ⁿ}, with the continuous space of an n-dimensional hypersphere, i.e. {x:x∈Rⁿ and ||x||²=1}. The mapping problem is initially solved in the continuous domain by employing the gradient projection technique to a continuously differentiable objective function. The optimal process `locations´ from the solution of the continuous hypersphere mapping problem are then discretized onto the n-dimensional hypercube. The proposed approach can solve, directly, the problem of mapping P processes onto N nodes for the general case where P>N. In contrast, competing embedding heuristics from the literature can produce only one-to-one mappings and cannot, therefore, be directly applied when P>N