Groupe d’études et de recherche en analyse des décisions

G-2009-46

Locating Objects in the Plane Using Global Optimization Techniques

, et

We address the problem of locating in the plane objects such as segments, arcs of circumferences, arbitrary convex sets, their complements or their boundaries. Given a set of points, we seek the rotation and translation for such an object optimizing a very general performance measure, which includes as a particular case the classical objectives in semi-obnoxious facility location. In general, the above mentioned model yields a Global Optimization problem, whose resolution is dealt with using DC (Difference of Convex) techniques such as Outer Approximation or Branch and Bound.

, 31 pages