Rectangle covering
Kristóf Kovács, Boglárka G.-Tóth · AIP conference proceedings · 2019
The problem we discuss was proposed by an industrial partner. The aim is to locate light sources around a rectangular field so that the whole field is covered. We assume these lighted areas to be rectangular as well, parallel to the field. Covering an area with multiple light sources is allowed. There are multiple types of light sources, priced differently with different attributes. Our aim is to minimize the cost of the cover.We propose two solution approaches for solving this covering problem. In the first direct approach, we formulate the problem by a single MIP model, using constraints that force every rectangle to have proper neighbors. In the second constraint generation approach, we formulate a MIP model to locate the light sources such that a finite number of predetermined points of the field have to be covered. If the result solves the original problem, since it covers the whole field, then we stop. Otherwise, a constraint generation model calculates a non-covered point such that the first model has to improve its previous solution to cover this new point as well.