A nonlinear optimization approach to the covering problem

• Grant number: 19/25258-7
• Support Opportunities: Scholarships in Brazil - Post-Doctoral
• Start date: February 01, 2020
• End date: May 05, 2021
• Field of knowledge: Physical Sciences and Mathematics - Mathematics - Applied Mathematics
• Principal Investigator: Ernesto Julián Goldberg Birgin
• Grantee: Rafael Massambone de Oliveira
• Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil
• Associated research grant: 18/24293-0 - Computational methods in optimization, AP.TEM

Abstract

In this project we intend to address a complementary problem to the packing problem. This is the covering problem. In the covering problem that we want to study, given a region of the n-dimensional space and a fixed amount N of identical and variable sized items, we want to find the minimum dimension that the items must have to cover the object. A concrete example is to find the configuration (position of the centers) and the radius that N identical circles must have to cover a unit-side square. Problems of this kind have been solved geometrically. Another option already studied is to replace the object to be covered by a finite set of points. In this project we intend to study the possibility of formulating the problem as a continuous optimization problem and try to solve it with classical techniques of continuous optimization. (AU)

Scientific publications

(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)

BIRGIN, ERNESTO G.; LAURAIN, ANTOINE; MASSAMBONE, RAFAEL; SANTANA, ARTHUR G.. A SHAPE-NEWTON APPROACH TO THE PROBLEM OF COVERING WITH IDENTICAL BALLS. SIAM JOURNAL ON SCIENTIFIC COMPUTING, v. 44, n. 2, p. 27-pg., 2022-01-01. (16/01860-1, 18/24293-0, 13/07375-0, 19/25258-7)

BIRGIN, ERNESTO G.; GARDENGHI, JOHN L.; LAURAIN, ANTOINE. Bounds on the Optimal Radius When Covering a Set with Minimum Radius Identical Disks. MATHEMATICS OF OPERATIONS RESEARCH, v. N/A, p. 36-pg., 2023-09-12. (18/24293-0, 13/07375-0, 19/25258-7, 16/01860-1)

BIRGIN, E. G.; LAURAIN, A.; MASSAMBONE, R.; SANTANA, A. G.. SHAPE OPTIMIZATION APPROACH TO THE PROBLEM OF COVERING A TWO-DIMENSIONAL REGION WITH MINIMUM-RADIUS IDENTICAL BALLS. SIAM JOURNAL ON SCIENTIFIC COMPUTING, v. 43, n. 3, p. A2047-A2078, 2021. (18/24293-0, 16/01860-1, 13/07375-0, 19/25258-7)