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

(The scientific publications listed on this page originate from the Web of Science or SciELO databases. Their authors have cited FAPESP grant or fellowship project numbers awarded to Principal Investigators or Fellowship Recipients, whether or not they are among the authors. This information is collected automatically and retrieved directly from those bibliometric databases.)

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)