# Smallest circle¶

## Principles learned¶

• Define the float bounds from the data
• Define the actual set of decision variables
• Create a non-linear expression with operators “sqrt” and “pow”

## Problem¶

Given a set of points in the plane, find the circle with minimal radius which contains all of them.

For more details, see : problem.html.

## Data¶

Each data file contains:

• number of points
• x and y coordinates of each point

## Program¶

The decision variables in the model are x and y, respectively equal to the abscissa and the ordinate of the origin of the circle. The radius to minimize is deduced as the maximum distance between the origin and each point.

Execution:
localsolver smallest_circle.lsp inFileName=instances/10points.txt [lsTimeLimit=] [solFileName=]
```/********** smallest_circle.lsp **********/

use io;

function input(){
usage = "\nUsage: localsolver smallest_circle.lsp "
+ "inFileName=inputFile [solFileName=outputFile] [lsTimeLimit=timeLimit]\n";

if (inFileName == nil) throw usage;

for [i in 1..nbPoints]{
}

minX = min[i in 1..nbPoints](coordX[i]);
minY = min[i in 1..nbPoints](coordY[i]);
maxX = max[i in 1..nbPoints](coordX[i]);
maxY = max[i in 1..nbPoints](coordY[i]);
}

/* Declares the optimization model. */
function model() {

// x, y are respectively the abscissa and the ordinate of the origin of the circle
x <- float(minX,maxX);
y <- float(minY,maxY);

r <- sqrt(max[i in 1..nbPoints](pow(x - coordX[i], 2) + pow(y - coordY[i], 2)));
minimize r;
}

/* Parameterizes the solver. */
function param() {
if(lsTimeLimit == nil) lsTimeLimit = 6;
}

/* Writes the solution in a file */
function output() {
if (solFileName != nil) // write solution file if needed
{
println("Write solution into file '" + solFileName + "'");
local solFile = io.openWrite(solFileName);
solFile.println("x=", x.value);
solFile.println("y=", y.value);
solFile.println("r=", r.value);
}
}
```
Execution (Windows)
set PYTHONPATH=%LS_HOME%\bin\python27\
python smallest_circle.py instances\10points.txt
Execution (Linux)
export PYTHONPATH=/opt/localsolver_XXX/bin/python27/
python smallest_circle.py instances/10points.txt
```########## smallest_circle.py ##########

import localsolver
import sys

if len(sys.argv) < 2:
print ("Usage: python smallest_circle.py inputFile [outputFile] [timeLimit]")
sys.exit(1)

with open(filename) as f:
return [int(elem) for elem in f.read().split()]

with localsolver.LocalSolver() as ls:

#
#

# Number of points
nb_points = file_it.next()

# Point coordinates
coord_x = [None]*nb_points
coord_y = [None]*nb_points

coord_x[0] = file_it.next()
coord_y[0] = file_it.next()

# Minimum and maximum value of the coordinates of the points
min_x = coord_x[0]
max_x = coord_x[0]
min_y = coord_y[0]
max_y = coord_y[0]

for i in range(1,nb_points):
coord_x[i] = file_it.next()
coord_y[i] = file_it.next()
if (coord_x[i] < min_x):
min_x = coord_x[i]
else:
if (coord_x[i] > max_x):
max_x = coord_x[i]
if (coord_y[i] < min_y):
min_y = coord_y[i]
else:
if (coord_y[i] > max_y):
max_y = coord_y[i]

#
# Declares the optimization model
#
model = ls.model

# Numerical decisions
x = model.float(min_x, max_x)
y = model.float(min_y, max_y)

# Distance between the origin and the point i
radius = [(x - coord_x[i])**2 + (y - coord_y[i])**2 for i in range(nb_points)]

model.minimize(r)

model.close()

#
# Parameterizes the solver
#
if len(sys.argv) >= 4: ls.create_phase().time_limit = int(sys.argv[3])
else: ls.create_phase().time_limit = 6

ls.solve()

#
# Writes the solution in a file
#
if len(sys.argv) >= 3:
with open(sys.argv[2], 'w') as f:
f.write("x=%f\n" % x.value)
f.write("y=%f\n" % y.value)
f.write("r=%f\n" % r.value)
```
Compilation / Execution (Windows)
cl /EHsc smallest_circle.cpp -I%LS_HOME%\include /link %LS_HOME%\bin\localsolver.dll.lib
smallest_circle instances\10points.txt
Compilation / Execution (Linux)
g++ smallest_circle.cpp -I/opt/localsolver_XXX/include -llocalsolver -lpthread -o smallest_circle
./smallest_circle instances/10points.txt
```//********* smallest_circle.cpp *********

#include <iostream>
#include <sstream>
#include <fstream>
#include <vector>
#include "localsolver.h"

using namespace localsolver;
using namespace std;

class SmallestCircle {
public:
// Number of points
int nbPoints;

// Point coordinates
vector<lsint> coordX;
vector<lsint> coordY;

// Minimum and maximum value of the coordinates of the points
lsdouble minX;
lsdouble minY;
lsdouble maxX;
lsdouble maxY;

// Solver.
LocalSolver localsolver;

// LS Program variables
LSExpression x;
LSExpression y;

// Objective
LSExpression r;

ifstream infile;
infile.open(fileName.c_str());

infile >> nbPoints;

coordX.resize(nbPoints);
coordY.resize(nbPoints);
infile >> coordX[0];
infile >> coordY[0];

minX = coordX[0];
maxX = coordX[0];
minY = coordY[0];
maxY = coordY[0];

for (int i = 1; i < nbPoints; i++){
infile >> coordX[i];
infile >> coordY[i];
if (coordX[i] < minX) minX = coordX[i];
else if (coordX[i] > maxX) maxX = coordX[i];
if (coordY[i] < minY) minY = coordY[i];
else if (coordY[i] > maxY) maxY = coordY[i];
}
}

void solve(int limit) {
// Declares the optimization model.
LSModel model = localsolver.getModel();

// Numerical decisions
x = model.floatVar(minX, maxX);
y = model.floatVar(minY, maxY);

// Distance between the origin and the point i
for (int i = 0; i < nbPoints; i++){
radius[i] = model.pow(x - coordX[i], 2) + model.pow(y - coordY[i], 2);
}

model.minimize(r);
model.close();

// Parameterizes the solver.
LSPhase phase = localsolver.createPhase();
phase.setTimeLimit(limit);
localsolver.solve();
}

// Writes the solution in a file
void writeSolution(const string& fileName) {
ofstream outfile;
outfile.open(fileName.c_str());

outfile << "x=" << x.getDoubleValue() << endl;
outfile << "y=" << y.getDoubleValue() << endl;
outfile << "r=" << r.getDoubleValue() << endl;
}
};

int main(int argc, char** argv) {
if (argc < 2) {
cerr << "Usage: smallest_circle inputFile [outputFile] [timeLimit]" << endl;
return 1;
}

const char* instanceFile = argv[1];
const char* solFile = argc > 2 ? argv[2] : NULL;
const char* strTimeLimit = argc > 3 ? argv[3] : "6";

try {
SmallestCircle model;
model.solve(atoi(strTimeLimit));
if(solFile != NULL) model.writeSolution(solFile);
return 0;
} catch (const exception& e){
cerr << "Error occurred: " << e.what() << endl;
return 1;
}
}
```
Compilation/Execution (Windows)
copy %LS_HOME%\bin\*net.dll .
csc SmallestCircle.cs /reference:localsolvernet.dll
SmallestCircle instances\10points.txt
```/********** SmallestCircle.cs **********/

using System;
using System.IO;
using localsolver;

public class SmallestCircle : IDisposable
{
// Number of points
int nbPoints;

// Point coordinates
double[] coordX;
double[] coordY;

// Minimum and maximum value of the coordinates of the points
double minX;
double minY;
double maxX;
double maxY;

// Solver
LocalSolver localsolver;

// LS Program variables
LSExpression x;
LSExpression y;

// Objective
LSExpression r;

public SmallestCircle()
{
localsolver = new LocalSolver();
}

{
{
coordX = new double[nbPoints];
coordY = new double[nbPoints];

coordX[0] = int.Parse(splittedCoord[0]);
coordY[0] = int.Parse(splittedCoord[1]);

minX = coordX[0];
maxX = coordX[0];
minY = coordY[0];
maxY = coordY[0];

for (int i = 1; i < nbPoints; i++)
{
coordX[i] = int.Parse(splittedCoord[0]);
coordY[i] = int.Parse(splittedCoord[1]);

minX = Math.Min(coordX[i], minX);
maxX = Math.Max(coordX[i], maxX);
minY = Math.Min(coordY[i], minY);
maxY = Math.Max(coordY[i], maxY);
}
}
}

public void Dispose()
{
if (localsolver != null)
localsolver.Dispose();
}

public void Solve(int limit)
{
// Declares the optimization model.
LSModel model = localsolver.GetModel();

// Numerical decisions
x = model.Float(minX, maxX);
y = model.Float(minY, maxY);

// Distance between the origin and the point i
for (int i = 0; i < nbPoints; i++)
{
radius[i] = model.Pow(x - coordX[i], 2) + model.Pow(y - coordY[i], 2);
}

model.Minimize(r);
model.Close();

// Parameterizes the solver.
LSPhase phase = localsolver.CreatePhase();
phase.SetTimeLimit(limit);

localsolver.Solve();
}

// Writes the solution in a file
public void WriteSolution(string fileName)
{
using (StreamWriter output = new StreamWriter(fileName))
{
output.WriteLine("x=" + x.GetDoubleValue());
output.WriteLine("y=" + y.GetDoubleValue());
output.WriteLine("r=" + r.GetDoubleValue());
}
}

public static void Main(string[] args)
{
if (args.Length < 1)
{
Console.WriteLine("Usage: SmallestCircle inputFile [outputFile] [timeLimit]");
Environment.Exit(1);
}

string instanceFile = args[0];
string outputFile = args.Length > 1 ? args[1] : null;
string strTimeLimit = args.Length > 2 ? args[2] : "6";

using (SmallestCircle model = new SmallestCircle())
{
model.Solve(int.Parse(strTimeLimit));
if (outputFile != null)
model.WriteSolution(outputFile);
}
}
}
```
Compilation / Execution (Windows)
javac SmallestCircle.java -cp %LS_HOME%\bin\localsolver.jar
java -cp %LS_HOME%\bin\localsolver.jar;. SmallestCircle instances\10points.txt
Compilation/Execution (Linux)
javac SmallestCircle.java -cp /opt/localsolver_XXX/bin/localsolver.jar
java -cp /opt/localsolver_XXX/bin/localsolver.jar:. SmallestCircle instances/10points.txt
```/********** SmallesrCircle.java **********/

import java.util.*;
import java.io.*;
import localsolver.*;

public class SmallestCircle {
// Number of points
private int nbPoints;

// Point coordinates
private int[] coordX;
private int[] coordY;

// Minimum and maximum value of the coordinates of the points
private int minX;
private int minY;
private int maxX;
private int maxY;

// Solver.
private LocalSolver localsolver;

// LS Program variables
private LSExpression x;
private LSExpression y;

// Objective i
private LSExpression r;

private void readInstance(String fileName) throws IOException {
try(Scanner input = new Scanner(new File(fileName))) {
nbPoints = input.nextInt();

coordX = new int[nbPoints];
coordY = new int[nbPoints];

coordX[0] = input.nextInt();
coordY[0] = input.nextInt();
minX = coordX[0];
maxX = coordX[0];
minY = coordY[0];
maxY = coordY[0];

for (int i = 1; i < nbPoints; i++) {
coordX[i] = input.nextInt();
coordY[i] = input.nextInt();
minX = Math.min(coordX[i], minX);
maxX = Math.max(coordX[i], maxX);
minY = Math.min(coordY[i], minY);
maxY = Math.max(coordY[i], maxY);
}
}
}

private void solve(int limit) {
localsolver = new LocalSolver();

// Declares the optimization model.
LSModel model = localsolver.getModel();

// Numerical decisions
x = model.floatVar(minX, maxX);
y = model.floatVar(minY, maxY);

// Distance between the origin and the point i
for (int i = 0; i < nbPoints; i++) {
}

model.minimize(r);
model.close();

// Parameterizes the solver.
LSPhase phase = localsolver.createPhase();
phase.setTimeLimit(limit);

localsolver.solve();
}

// Writes the solution in a file
private void writeSolution(String fileName) throws IOException {
try(PrintWriter output = new PrintWriter(fileName)) {
output.println("x=" + x.getDoubleValue());
output.println("y=" + y.getDoubleValue());
output.println("r=" + r.getDoubleValue());
}
}

public static void main(String[] args) {
if (args.length < 1) {
System.err.println("Usage: java SmallestCircle inputFile [outputFile] [timeLimit]");
System.exit(1);
}

String instanceFile = args[0];
String outputFile = args.length > 1 ? args[1] : null;
String strTimeLimit = args.length > 2 ? args[2] : "6";
try {
SmallestCircle model = new SmallestCircle();