Covering with ellipses using nonlinear programming

• Grant number: 10/18980-3
• Support Opportunities: Regular Research Grants
• Start date: February 01, 2011
• End date: January 31, 2013
• Field of knowledge: Physical Sciences and Mathematics - Mathematics - Applied Mathematics
• Principal Investigator: Marina Andretta
• Grantee: Marina Andretta
• Host Institution: Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brazil

Abstract

Maximal Covering Location Problems (MCLP) appear when there are not enough resources to cover all demand points. They also appear when a company wants to maximize its profit for the selected covering. Any point within the covering distance is covered and the others are not. The problem involves implementing different types of coverings that have specific associated costs. The goal is to cover the demand points that maximize the profit.We are interested in the problem of planar covering of points with ellipses: we have a set of n demand points in the plane (with weights associated to them), a set of m ellipses (with costs associated to their allocation) and we want to allocate at most k of these ellipses and cover some demand points to get the maximum profit. The profit is measured by summing the weight of the covered demand points and subtracting the costs of the allocated ellipses.There are some methods that can be used to solve this problem, several of which use heuristics and approximations of the solution. We are interested in exact algorithms to solve the problem. In this case, we enumerate the subsets of the m ellipses with at most k elements. For each one of these subsets, we analise which demand points can be covered by these ellipses and find the best solution. To find out where to position an ellipse in the plane to cover a given set of demand points (and if it is possible), we use ALGENCAN, a method to solve nonlinear programming problems.We are also interested in developing a method to solve the generalized problem that consider the case where the ellipses have variable sizes. In this case, the cost of allocating an ellipse would be a function of its area. A method to solve this problem should be essentially different from the enumeration method mentioned above. (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)

ANDRETTA, M.; BIRGIN, E. G.. Deterministic and stochastic global optimization techniques for planar covering with ellipses problems. European Journal of Operational Research, v. 224, n. 1, p. 23-40, JAN 1 2013. (10/18980-3, 10/10133-0, 06/53768-0, 09/10241-0)