A new quadratic relaxation for binary variables applied to the distance geometry problem
- PDF / 212,934 Bytes
- 5 Pages / 595.224 x 790.955 pts Page_size
- 57 Downloads / 192 Views
BRIEF NOTE
A new quadratic relaxation for binary variables applied to the distance geometry problem Petra M. Bartmeyer1
· Christiano Lyra1
Received: 30 October 2019 / Revised: 20 February 2020 / Accepted: 3 March 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract 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 relaxation. Keywords Binary relaxation · Combinatorial optimization · Unassigned distance geometry problem · Nonlinear optimization
1 Introduction Problems in the optimization of structures frequently require the use of binary decision variables. Examples include a nonlinear 0 − 1 formulation to minimize the mass of load-carrying structures (Stolpe and Sandal 2018) and the optimal design of frame structures (Van Mellaert et al. 2018). Exact solutions to these problems require high computational efforts, precluding the solution of large-scale problems. A strategy to tackle the computational burden is to relax the binary variables and devise constraints that should induce the value of the relaxed variables to a binary domain. An ideal relaxation technique would be able to obtain binary solutions with easy handling constraints that allow reducing the overall computation effort. The quest for such an ideal relaxation technique has been the research core in binary optimization. Responsible Editor: Mehmet Polat Saka Petra M. Bartmeyer
[email protected] Christiano Lyra [email protected] 1
School of Electrical and Computer Engineering – University of Campinas (UNICAMP), Campinas, Brazil
For instance, binary variables xi ∈ {−1, 1} can be relaxed to the interval [−1, 1] by adding a set of constraints xi2 = 1 (Kochenberger et al. 2014). Another procedure relaxes the binary variables xi ∈ {0, 1} as xi ∈ [0, 1], with the addition of the constraints xi (xi − 1) = 0 (Kochenberger et al. 2014). A third technique is the solid isotropic material with penalization (SIMP) method (Bendsøe 1989), for problems with xi ∈ {0, 1} variables. Because the SIMP may fail to obtain binary solutions in some simple counterexamples, Mart´ınez (2005) proposed a set of conditions to overcome this issue, including the n xi ≤ V , V ∈ {1, . . . , n}. addition of the constraint i=1
However, the requirement of the upper bound V restrains the domain of applications of this SIMP ap
Data Loading...
