A new quadratic relaxation for binary variables applied to the distance geometry problem

Problems in structural optimization typically involve decisions modeled as binary variables that lead to difficult combinatorial optimization problems. The literature presents different techniques to relax the binary variables in order to avoid the high computational costs required by the solution of combinatorial problems. This note develops a novel relaxation strategy to map a problem with binary variables into an equivalent problem with continuous variables. A set of theoretical results prove the equivalence of the proposed approach and the original binary optimization problem. The strategy is applied to the unassigned distance geometry problem, relying on the design of a new formulation for the problem. Computational studies illustrate the benefits of the proposed relaxationCONSELHO NACIONAL DE DESENVOLVIMENTO CIENTÍFICO E TECNOLÓGICO - CNPQ148.400/2016-7; 312.647/2017-