circle.gms : Circle Enclosing Points - SNOPT Example

Description

This is an example from the GAMS/SNOPT manual. Find the smallest circle
that contains a number of given points.

<a href="http://en.wikipedia.org/wiki/Smallest_circle_problem">http://en.wikipedia.org/wiki/Smallest_circle_problem</a>

Reference

  • Gill, P E, Murray, W, Saunders, M A, Drud, A S, and Kalvelagen, E, GAMS/SNOPT: An SQP Algorithm for Large-Scale Constrained Optimization, 2002.

Small Model of Type : NLP


Category : GAMS Model library


Main file : circle.gms

$title Circle Enclosing Points - SNOPT Example (CIRCLE,SEQ=201)
$ontext

This is an example from the GAMS/SNOPT manual. Find the smallest circle
that contains a number of given points.

http://en.wikipedia.org/wiki/Smallest_circle_problem


Gill, P E, Murray, W, and Saunders, M A, GAMS/SNOPT: An SQP Algorithm
for Large-Scale Constrained Optimization, 1988.

$offtext

$if not set size $set size 10
set i points /p1*p%size%/;

parameters
   x(i)    x coordinates,
   y(i)    y coordinates;

* fill with random data
x(i) = uniform(1,10);
y(i) = uniform(1,10);

variables
   a       x coordinate of center of circle
   b       y coordinate of center of circle
   r       radius;

equations
   e(i)    points must be inside circle;


e(i)..  sqr(x(i)-a) + sqr(y(i)-b) =l= sqr(r);

r.lo = 0;

parameters xmin,ymin,xmax,ymax;
xmin = smin(i, x(i));
ymin = smin(i, y(i));
xmax = smax(i, x(i));
ymax = smax(i, y(i));

* set starting point
a.l = (xmin+xmax)/2;
b.l = (ymin+ymax)/2;
r.l = sqrt( sqr(a.l-xmin) + sqr(b.l-ymin) );


model m /all/;
solve m using nlp minimizing r;

if (m.modelstat <> %modelstat.Optimal% and
    m.modelstat <> %modelstat.LocallyOptimal% and
    m.modelstat <> %modelstat.FeasibleSolution%,
    abort "stop");