Geometric branch-and-bound methods

Some simple examples

One-dimensional example problem

The one-dimensional example problem is the simplest way to explain how to use the geometric branch-and-bound JavaScript tool. Here, the sine-function is minimized on an interval which contains exactly one minimum.

Two-dimensional example problem

Given a set of points, the two-dimensional example problem is a more sophisticated example where we seek for the smallest disc containing all the given points. The problem is formulated as two-dimensional minimization problem which is solved by the use of interval arithmetic.

Facility location problems

The Weber problem

The two-dimensional Weber problem is to find a location for a new facility on the plane which minimizes the weighted sum of Euclidean distances to a given set of demand points. If some weights are positive and others are negative, global optimization techniques lead to helpful solution algorithms.

The median circle problem

The median circle problem is to locate a circle so as to minimize the sum of distances between the circumference and some given demand points on the plane. Since every circle can be defined by its center and radius, we have a three-dimensional problem.

The 2-median problem

The 2-median problem is to find two new facilities on the Euclidean plane taking some given demand points into account. Hence, we are dealing with a four-dimensional problem.

The 3-median problem

The 3-median problem is to find three new facilities on the Euclidean plane taking some given demand points into account. Hence, we are dealing with a six-dimensional problem such the run-times of the geometric branch-and-bound algorithm increases significantly compared to the 2-median problem.

Geometric problems

The circle detection problem

The circle detection problem is to find an imperfect pictured circle in a set of two-dimensional points. This problem is well known in image processing where the set of points is derived from an image applying an edge detection algorithm. Note that in the same manner it is also possible to detect other shapes such as lines or ellipses.

The rigid transformation problem

The two-dimensional rigid transformation problem is to align two sets of points in the Euclidean space for which correspondence is known. The transformation is defined by a rotation matrix and a translation vector such that we obtain a three-dimensional optimization problem.

© 2013-2014. The current website presents additional information and materials on the manuscript An invitation to solve global optimization problems by the use of geometric branch-and-bound methods by Daniel Scholz. Detailed problem descriptions and an extensive documentation of the JavaScript branch-and-bound tool can be found therein. Last updated December 30th, 2013.

Disclaimer